Friday, January 8, 2016

Relation between join, fmap and bind

Recognizing the equivalence:

join (fmap f ma) = ma >>= f

Proof:


  join (fmap f ma)
  fmap f ma >>= id         -- join x = x >>= id                 (definition)
  (ma >>= return . f) >>= id
                           -- fmap f xs = xs >>= return . f              (1)
  ma >>= (\x -> (return . f) x >>= id)
                           -- m >>= (\x -> k x >>= h) = (m >>= k) >>= h  (2)
  ma >>= (\x -> return (f x) >>= id)
                           -- (f . g) x = f (g x)               (definition)
  ma >>= (\x -> id (f x))  -- return a >>= k = k a                       (3)
  ma >>= (\x -> f x)       -- id x = x                          (definition)
  ma >>= f                 --                                (eta reduction)

  (1) implied by monad laws
  (2) associativity monad law
  (3) left identity monad law
  

Credit to verement.

0 comments: