[Haskell-cafe] Functors [Comments from OCaml Hacker Brian Hurt]

[Ryan Ingram]

On Sun, Jan 18, 2009 at 3:23 AM, Andrew Coppin
<andrewcoppin at btinternet.com> wrote:
> Given that liftM exists, why is having an identical implementation for fmap
> useful?

For many structures, it's easier to define (>>=) in terms of fmap and
join.  For these objects, often the "generic" implementation of liftM
is far less efficient than fmap.

That is to say, given a monad T and these functions:

returnT :: a -> T a
fmapT :: (a -> b) -> T a -> T b
joinT :: T (T a) -> T a

We can create Haskell instances as follows

instance Functor T where fmap = fmapT
instance Monad T where
   return = returnT
   m >>= f = joinT (fmap f m)

Then,

liftM f m
 = m >>= \x -> return (f x)
 = joinT (fmapT (\x -> return (f x)) m)

Now, we know (by the monad & functor laws) that this is equivalent to
(fmap f m), but it's a lot harder for the compiler to spot that.

The list monad is a great example; I'd expect that using fmap (== map)
in the list monad is significantly more efficient than liftM which
constructs a singleton list for each element of the input and
concatenates them all together.

  -- ryan