haskellfunctorapplicativehackage

Haskell: Flaw in the description of applicative functor laws in the hackage Control.Applicative article?: it says Applicative determines Functor

I think I found a flaw in the hackage article for Control.Applicative. As a description of the applicative functor laws, it says:

class Functor f => Applicative f where

A functor with application, providing operations to embed pure expressions (pure), and sequence computations and combine their results (<*>).

A minimal complete definition must include implementations of these functions satisfying the following laws:

identity

pure id <*> v = v

composition

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

homomorphism

pure f <*> pure x = pure (f x)

interchange

u <*> pure y = pure ($ y) <*> u

(note that this does not say anything about fmap) and it states that these laws determine the Functor instance:

As a consequence of these laws, the Functor instance for f will satisfy

fmap f x = pure f <*> x

I thought at first this was obviously wrong. That is, I guessed there must exist a type constructor t satisfying the following two conditions:

  1. t is an instance of Applicative fulfilling the rules above, and
  2. There are two different implementations of instance (Functor t) (i.e. there are two distinct functions fmap1, fmap2 :: (a->b) -> (t a->t b), satisfying the functor laws).

If (and only if) the above is correct, the above statement must be rewritten to

The Functor instance for f must satisfy

fmap f x = pure f <*> x

As a consequence of these laws, this satisfies the Functor laws.

which is clearly correct, no matter whether my guess is right or not.

My question is: is my guess correct? Is there a t with the desired conditions?

What follows is the explanation of what I thought during trying to answer this question by myself.

If we were mere mathematicians uninterested in actual Haskell programming, we could easily answer this question affirmatively. In fact,

t = Identity
newtype Identity a = Identity {runIdentity :: a}

meets the requirements 1 and 2 above (in fact, almost anything will do). Indeed, Identity is trivially an instance of Functor and Applicative, as defined in Data.Functor.Identity. (This satisfies fmap f = (pure f <*>).) To define another "implementation" of instance (Functor f), Take, for each type a, two functions

transf_a, tinv_a :: a -> a

such that

tinv_a . transf_a = id

(This is, set-theoretically, easy). Now define

instance (Functor Identity) where
 fmap (f :: a->b) = Identity . transf_b . f . tinv_a . runIdentity

This satisfies the Functor laws and is a different implementation from the trivial one if there are

x :: a
f :: a -> b

such that

f x /= transf_b $ f $ tinv_a x

But it is not at all obvious whether we can do it in Haskell. Is something like: 

class (Isom a) where
 transf, tinv :: a -> a

instance (Isom a) where
 transf = id
 tinv = id

specialized instance (Isom Bool) where
 transf = not
 tinv = not

possible in Haskell?

Edit

I forgot to write something very important. I recognize Control.Applicative as part of GHC base package, so I am also interested in whether the answer to my question changes with any GHC language extensions, such as FlexibleInstances or OverlappingInstances, which I don't understand yet.

Solution

  • Any type in Haskell can have at most one instance of Functor, so your guess is not correct: For no type t (whether or not it's an instance of Applicative) can there exist two different implementations of instance (Functor t). See: http://article.gmane.org/gmane.comp.lang.haskell.libraries/15384