Can someone explain the traverse function in Haskell?

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.

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]]

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.