[Haskell-beginners] fmap versus bind

[Felipe Almeida Lessa]

On Tue, May 3, 2011 at 12:32 PM, Patrick LeBoutillier
<patrick.leboutillier at gmail.com> wrote:
> I'm trying to understand this example and I can't get the types to line up.
> Can you provide the "real" types for ds and (applyOp op x y)?
>
> This is what I'm working out:
>
>     fmap ((:) ds) (applyOp op x y)
> == fmap (ds :) (applyOp op x y)
> == fmap (\dss -> ds : dss) (applyOp op x y)
>
>      (applyOp op x y) >>= (flip (:) ds)
> == (applyOp op x y) >>= (: ds)
> == (applyOp op x y) >>= (\d -> d : ds)
>
> To my untrained eyes is doesn't even look like the code is doing the
> same thing...
> What am I missing here (or more probably where is my mistake)?

I think that OP forgot a return, i.e., he meant 'applyOp op x y >>=
return . flip (:) ds'.

Regardless, there's a trick that you may use whenever you want to know
the types of something.  Just make a function where everything you
don't know is an argument, and ask GHCi to give you its type.
Supposing it's Haskell 98, GHCi will always give you the most general
type.  With this example:

Prelude> :t \ds applyOp op x y -> applyOp op x y >>= flip (:) ds
\ds applyOp op x y -> applyOp op x y >>= flip (:) ds
  :: [a] -> (t -> t1 -> t2 -> [a]) -> t -> t1 -> t2 -> [a]

So we see that

  ds :: [a]
  applyOp :: t -> u -> v -> [a]
  op :: t
  x :: u
  y :: v
  applyOp op x y >>= flip (:) ds :: [a]

works.  In other words, it's an expression in the list monad.  Whether
it is useful or not, I don't know =).  Adding the 'return':

Prelude> :t \ds applyOp op x y -> applyOp op x y >>= return . flip (:) ds
\ds applyOp op x y -> applyOp op x y >>= return . flip (:) ds
  :: (Monad m) =>
     [a] -> (t -> t1 -> t2 -> m a) -> t -> t1 -> t2 -> m [a]

So now we get:

  Monad m =>
  ds :: [a]
  applyOp :: t -> u -> v -> m a
  op :: t
  x :: u
  y :: v
  applyOp op x y >>= return . flip (:) ds :: m [a]

Seems much more useful!  So 'applyOp op x y :: m a' and the result of
everything is 'm [a]'.

Note that if there is a type mismatch (even with the general
arguments!), GHCi will tell you right away.  For example,

Prelude> :t \ds applyOp op x y -> applyOp op x y >>= fmap . flip (:) ds

<interactive>:1:48:
    Couldn't match expected type `a -> b' against inferred type `[a1]'
    In the second argument of `(.)', namely `flip (:) ds'
    In the second argument of `(>>=)', namely `fmap . flip (:) ds'
    In the expression: applyOp op x y >>= fmap . flip (:) ds

This means that no matter what ds, applyOp, op, x and y you choose,
'applyOp op x y >>= fmap . flip (:) ds' will always be ill-typed.

Cheers,

-- 
Felipe.