`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.