[Haskell-cafe] Functors [Comments from OCaml Hacker Brian Hurt]
Ryan Ingram
ryani.spam at gmail.com
Sun Jan 18 07:10:08 EST 2009
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
More information about the Haskell-Cafe
mailing list