Can someone explain the traverse function in Haskell?

Question

I am trying and failing to grok the traverse function from Data.Traversable. I am unable to see its point. Since I come from an imperative background, can someone please explain it to me in terms of an imperative loop? Pseudo-code would be much appreciated. Thanks.

Answer 1

traverse is the same as fmap, except that it also allows you to run effects while you're rebuilding the data structure.

Take a look at the example from the Data.Traversable documentation.

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

The Functor instance of Tree would be:

instance Functor Tree where
  fmap f Empty        = Empty
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r)

It rebuilds the entire tree, applying f to every value.

instance Traversable Tree where
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

The Traversable instance is almost the same, except the constructors are called in applicative style. This means that we can have (side-)effects while rebuilding the tree. Applicative is almost the same as monads, except that effects cannot depend on previous results. In this example it means that you could not do something different to the right branch of a node depending on the results of rebuilding the left branch for example.

For historical reasons, the Traversable class also contains a monadic version of traverse called mapM. For all intents and purposes mapM is the same as traverse - it exists as a separate method because Applicative only later became a superclass of Monad.

If you would implement this in an impure language, fmap would be the same as traverse, as there is no way to prevent side-effects. You can't implement it as a loop, as you have to traverse your data structure recursively. Here's a small example how I would do it in Javascript:

Node.prototype.traverse = function (f) {
  return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}

Implementing it like this limits you to the effects that the language allows though. If you f.e. want non-determinism (which the list instance of Applicative models) and your language doesn't have it built-in, you're out of luck.

Answer 2

traverse turns things inside a Traversable into a Traversable of things "inside" an Applicative, given a function that makes Applicatives out of things.

Let's use Maybe as Applicative and list as Traversable. First we need the transformation function:

half x = if even x then Just (x `div` 2) else Nothing

So if a number is even, we get half of it (inside a Just), else we get Nothing. If everything goes "well", it looks like this:

traverse half [2,4..10]
--Just [1,2,3,4,5]

But...

traverse half [1..10]
-- Nothing

The reason is that the <*> function is used to build the result, and when one of the arguments is Nothing, we get Nothing back.

Another example:

rep x = replicate x x

This function generates a list of length x with the content x, e.g. rep 3 = [3,3,3]. What is the result of traverse rep [1..3]?

We get the partial results of [1], [2,2] and [3,3,3] using rep. Now the semantics of lists as Applicatives is "take all combinations", e.g. (+) <$> [10,20] <*> [3,4] is [13,14,23,24].

"All combinations" of [1] and [2,2] are two times [1,2]. All combinations of two times [1,2] and [3,3,3] are six times [1,2,3]. So we have:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

Answer 3

I think it's easiest to understand in terms of sequenceA, as traverse can be defined as follows.

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

sequenceA sequences together the elements of a structure from left to right, returning a structure with the same shape containing the results.

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

You can also think of sequenceA as reversing the order of two functors, e.g. going from a list of actions into an action returning a list of results.

So traverse takes some structure, and applies f to transform every element in the structure into some applicative, it then sequences up the effects of those applicatives from left to right, returning a structure with the same shape containing the results.

You can also compare it to Foldable, which defines the related function traverse_.

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

So you can see that the key difference between Foldable and Traversable is that the latter allows you to preserve the shape of the structure, whereas the former requires you to fold the result up into some other value.

---

A simple example of its usage is using a list as the traversable structure, and IO as the applicative:

λ> import Data.Traversable
λ> let qs = ["name", "quest", "favorite color"]
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs
What is your name?
Sir Lancelot
What is your quest?
to seek the holy grail
What is your favorite color?
blue
["Sir Lancelot","to seek the holy grail","blue"]

While this example is rather unexciting, things get more interesting when traverse is used on other types of containers, or using other applicatives.

Answer 4

It's kind of like fmap, except that you can run effects inside the mapper function, which also changes the result type.

Imagine a list of integers representing user IDs in a database: [1, 2, 3]. If you want to fmap these user IDs to usernames, you can't use a traditional fmap, because inside the function you need to access the database to read the usernames (which requires an effect -- in this case, using the IO monad).

The signature of traverse is:

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

With traverse, you can do effects, therefore, your code for mapping user IDs to usernames looks like:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String]
mapUserIDsToUsernames fn ids = traverse fn ids

---

There's also a function called mapM:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Any use of mapM can be replaced with traverse, but not the other way around. mapM only works for monads, whereas traverse is more generic.

If you just want to achieve an effect and not return any useful value, there are traverse_ and mapM_ versions of these functions, both of which ignore the return value from the function and are slightly faster.

Answer 5

traverse is the loop. Its implementation depends on the data structure to be traversed. That might be a list, tree, Maybe, Seq(uence), or anything that has a generic way of being traversed via something like a for-loop or recursive function. An array would have a for-loop, a list a while-loop, a tree either something recursive or the combination of a stack with a while-loop; but in functional languages you do not need these cumbersome loop commands: you combine the inner part of the loop (in the shape of a function) with the data structure in a more directly manner and less verbose.

With the Traversable typeclass, you could probably write your algorithms more independent and versatile. But my experience says, that Traversable is usually only used to simply glue algorithms to existing data structures. It is quite nice not to need to write similar functions for different datatypes qualified, too.