Search code examples
haskelltype-signature

Understanding signature of function traverse in haskell

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Hi,
There are a lot of functions that I can't understand signature. Of course I understan that traverse get two arguments, that first is function. However,
what does mean (a -> f b) ? I can understand (a -> b).
Similary, t a, f (t b)

Could you explain it me ?

Solution

  • traverse is a type class-ed function so sadly the behaviour of this function depends on what exactly we choose t to be. This is not dis-similar to >>= or fmap. However there are rules for it's behaviour, just like in those cases. The rules are supposed to capture the idea that traverse takes a function a -> f b, which is an effectful transformation from a to b and lifts it to work on a whole "container" of as, collecting the effects of each of the local transformations.

    For example, if we have Maybe a the implementation of traverse would be

     traverse f (Just a) = Just <$> f a
 traverse f Nothing = pure Nothing

    For lists

     traverse f [a1, a2, ...] = (:) <$> f a1 <*> ((:) <$> f a2 <*> ...))

    Notice how we're taking advantage of the fact that the "effect" f is not only a functor, but applicative so we can take two f-ful computations, f a and f b and smash them together to get f (a, b). Now we want to come up with a few laws explaining that all traverse can do is apply f to the elements and build the original t a back up while collecting the effects on the outside. We say that

     traverse Identity = Identity -- We don't lose elements
 t . traverse f = traverse (t . f) -- For nicely composing t
 traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

    Now this looks quite complicated but all it's doing is clarifying the meaning of "Basically walks around and applies the local transformation". All this boils down to is that while you cannot just read the signature to understand what traverse does, an OK intuition for the signature is

    • We get a local, effectful function f :: a -> f b
    • A functor full of as
    • We get back a functor full of b gotten by repeatedly applying f, ala fmap
    • All the effects of f are accumulated so we get f (t b), not just t b.

    Remember though, traverse can get used in some weird ways. For example, the lens package is chock-full of using traverse with very strange functors to great effect.

    As a quick test, can you figure out how to use a legal traverse to implement fmap for t? That is

    fmapOverkill :: Traversable f => (a -> b) -> (f a -> f b)

    Or headMay

    headMay :: Traversable t => t a -> Maybe a

    Both of these are results of the fact that traversable instances also satisfy Functor and Foldable!