Traversable
traverse: map with an effect
map applies a function to every element of a list and keeps the list. traverse applies a function that also carries an effect, and keeps both the list and the effect:
map :: (a -> b) -> [a] -> [b]
traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
sequenceA :: Applicative f => [f a] -> f [a]
The first type has no effect to carry, so it cannot fail. The second one carries f, which may be Maybe, Either String or IO: the function returns a value wrapped in the effect, and traverse builds a list of values inside one effect. sequenceA is the same thing when the effects are already in the list, and traverse f = sequenceA . map f is the definition you can remember.
A list of checks
A parser that returns Either String Int has the shape traverse expects. The program parses two rows: both good gives a list, one bad gives the first error, and partitionEithers shows the other style, where every row is checked and the good and bad rows are collected:
module Main (main) where
import Data.Either (partitionEithers)
data User = User
{ userName :: String
, userAge :: Int
}
deriving (Show)
parseAge :: String -> Either String Int
parseAge text =
case reads text :: [(Int, String)] of
[(n, "")] | n >= 0 && n < 150 -> Right n
_ -> Left ("bad age: " ++ text)
parseUser :: String -> String -> Either String User
parseUser name age = User name <$> parseAge age
main :: IO ()
main = do
print (traverse parseAge ["30", "41"] :: Either String [Int])
print (traverse parseAge ["30", "x"] :: Either String [Int])
print (sequenceA [Just (1 :: Int), Just 2, Nothing] :: Maybe [Int])
print (sequenceA [Just 1, Just 2] :: Maybe [Int])
print (partitionEithers (map (uncurry parseUser) [("ann", "30"), ("bob", "x")]))
ghc -Wall -O1 -o checks checks.hs
./checks
Right [30,41]
Left "bad age: x"
Nothing
Just [1,2]
(["bad age: x"],[User {userName = "ann", userAge = 30}])
The second line is the shape of a check with traverse over Either: it stops at the first Left and returns it, because that is what <*> does for Either. The last line is the other policy: partitionEithers runs every row and splits the two outcomes, which the last lesson on Either used for validation.
Traversable for a tree
The tree of the earlier lesson is already a Functor and a Foldable. A Traversable instance is one more method, and the type of the result tells you what it does: an effect around the same shape. traverse f on a Leaf has no value to visit, so it is pure Leaf; on a node it visits the left subtree, the value and the right subtree and rebuilds the node with <$> and <*>.
module Main (main) where
data Tree a = Leaf | Node (Tree a) a (Tree a)
deriving (Show)
instance Functor Tree where
fmap _ Leaf = Leaf
fmap f (Node left value right) = Node (fmap f left) (f value) (fmap f right)
instance Foldable Tree where
foldr _ z Leaf = z
foldr f z (Node left value right) = foldr f (f value (foldr f z right)) left
instance Traversable Tree where
traverse _ Leaf = pure Leaf
traverse f (Node left value right) =
Node <$> traverse f left <*> f value <*> traverse f right
checked :: Int -> Either String Int
checked n
| n <= 2 = Right (n * 10)
| otherwise = Left ("too big: " ++ show n)
sample :: Tree Int
sample = Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)
main :: IO ()
main = do
print (traverse checked sample)
print (traverse checked (Node Leaf 1 Leaf))
print (sequenceA (Node Leaf (Just (5 :: Int)) Leaf) :: Maybe (Tree Int))
ghc -Wall -O1 -o tree tree.hs
./tree
Left "too big: 3"
Right (Node Leaf 10 Leaf)
Just (Node Leaf 5 Leaf)
The instance rebuilt the tree as Either String (Tree Int) and the first failing value stopped the walk: the value 3 comes after the values 1 and 2 in the order the Foldable instance chose, so the error is about 3. The third line is the other direction: values of the tree were already in Maybe, and sequenceA pushed the effect to the outside.
sequenceA and the shape
The two directions are worth naming, because they are the same function seen from two sides:
- traverse f takes a container of plain values and a function with an effect, and gives the effect around the container.
- sequenceA takes a container of effects and turns it into an effect around the container, which is traverse id.
- mapM and mapM_ are the same idea over Monad, and for and forM_ are the argument-flipped versions.
For Maybe the effect is "one failure loses the whole result", for Either e it is "the first error is the answer", for [] it is "every combination", and for IO it is "run the actions in order". One instance, and the same program works in all four.
mapM and the loops
In IO, traverse is the loop you write every day: one action per element, run in order. The picture is the same as the list example, with the effect being the printing:
module Main (main) where
import Control.Monad (forM_, when)
report :: String -> [String] -> Maybe [String]
report tag = traverse check
where
check row
| null row = Nothing
| otherwise = Just (tag ++ row)
main :: IO ()
main = do
print (report "row: " ["a", "b"])
print (report "row: " ["a", "", "c"])
mapM_ putStrLn ["first", "second"]
forM_ [1, 2, 3 :: Int] $ \n -> when (even n) (print n)
ghc -Wall -O1 -o loops loops.hs
./loops
Just ["row: a","row: b"]
Nothing
first
second
2
The last two lines are the loop in IO: mapM_ runs one action per element and throws the results away, and forM_ is the same with the list at the end, which reads better when the body is long. Both return IO (): there is nothing to collect.
Exercises
- Write parseAll :: [String] -> Maybe [Int] with traverse and readMaybe from Text.Read.
- Change the tree program so that checked returns Maybe Int instead of Either String Int, and run it.
- Use sequenceA on a list of [Int] values and explain the length of the result.
- Write a Traversable instance for a type of your own with two constructors.
- Add a function that counts the visited nodes during the traversal and explain why traverse cannot do that with a pure counter.
- Replace the mapM_ putStrLn line with traverse putStrLn and print the result.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is the type of
traverse?Answer
Applicative f => (a -> f b) -> [a] -> f [b]traverse keeps the list and wraps it in any Applicative, which is why it works for Maybe, Either and IO.
-
What does
sequenceA [Just 1, Nothing]return when the type isMaybe [Int]?Answer
Nothing
One Nothing loses the whole result, because that is how the Maybe Applicative combines values.
-
What does
traversedo on a Leaf of the tree?Answer
Returns pure Leaf, because there is no value to visit
A leaf carries no value, so the effect is the pure one and the shape is kept.
-
What does this program print?
module Main (main) where main :: IO () main = print (sequenceA [Just (2 :: Int), Just 3] :: Maybe [Int])Answer
Just [2,3]
sequenceA turns a list of Just values into one Just around the list.
-
Which function is
traverse id?Answer
sequenceAWith the identity function there is nothing to map, so the effects are only sequenced.
-
What does
traversereturn forEither Stringwhen the third element fails?Answer
The first Left, and the values after it are not visited
The Either Applicative stops at the first Left, which is why a check reports one error.
-
What does
mapM_return?Answer
IO ()The underscore version discards the results of the actions and returns unit in IO.
-
What does this program print?
module Main (main) where main :: IO () main = print (traverse (\n -> if n > 0 then Just n else Nothing) [1, 2, 3 :: Int])Answer
Just [1,2,3]
Every element passes the check, so the result is one Just around the whole list.
-
Why can a Traversable instance not change the shape of the tree?
Answer
The instance must rebuild the same constructors, and only the values change
traverse walks the existing structure and rebuilds it, so the shape is preserved and only values are replaced.
-
Which class does
Traversableextend?Answer
FunctorandFoldableThe class declaration is
class (Functor t, Foldable t) => Traversable t, so both are available on every instance.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev