Haskell Traversables

A Type Class for generalising the notation of mapping a function over each element in a data structure in a Foldables-way from left to right.

In other words traversables show how to apply Functors to Foldables.

Declaration

Built-in class deceleration from Data.Traversable:

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Other Primitives

The Traversable class also includes the primitive function

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

which transforms a data structure with elements that are applicative actions into a single such action that returns a data structure.

The class declaration also includes a default definition for traverse using sequenceA, so it suffices for the user to define only one of them as the other can then be derived:

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

The class also provides special names for the special case that the effects are monadic rather than applicative

mapM :: Monad m => (a -> m b) -> t a -> m (t b)
mapM = traverse
 
sequence :: Monad m => t (m a) -> m (t a)
sequence = sequenceA

Examples

Lists as Traversable

instance Traversable [] where
  -- traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
  traverse g []     = pure []
  traverse g (x:xs) = pure (:) <*> g x <*> traverse g xs

traverse can now be used to map a function that may fail on lists:

dec :: Int -> Maybe Int
dec n = if n > 0 then Just (n-1) else Nothing
 
> traverse dec [1,2,3]
Just [0,1,2]
> traverse dec [2,1,0]
Nothing

Binary Tree as Traversable

instance Traversable Tree where
-- traverse :: Applicative f =>
-- (a -> f b) -> Tree a -> f (Tree b)
traverse g (Leaf x) = pure Leaf <*> g x
traverse g (Node l r) = pure Node <*> traverse g l <*> traverse g r

traverse can now be used to map a function that may fail on lists:

dec :: Int -> Maybe Int
dec n = if n > 0 then Just (n-1) else Nothing
 
> traverse dec (Node (Leaf 1) (Leaf 2))
Just (Node (Leaf 0) (Leaf 1))
> traverse dec (Node (Leaf 0) (Leaf 1))
Nothing

SequenceA

> sequenceA [Just 1, Just 2, Just 3]
Just [1,2,3]
> sequenceA [Just 1, Nothing, Just 3]
Nothing
> sequenceA (Node (Leaf (Just 1)) (Leaf (Just 2)))
Just (Node (Leaf 1) (Leaf 2))
> sequenceA (Node (Leaf (Just 1)) (Leaf Nothing))
Nothing