I’m a poor object-oriented programmer, not versed to category theory and advanced Haskell. I understand
Functor, Applicative, Foldable, but what is the sense behind Traversable?
class (Functor t, Foldable t) => Traversable t where
-- | Map each element of a structure to an action, evaluate these actions
-- from left to right, and collect the results. For a version that ignores
-- the results see 'Data.Foldable.traverse_'.
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f
-- | Evaluate each action in the structure from left to right, and
-- and collect the results. For a version that ignores the results
-- see 'Data.Foldable.sequenceA_'.
sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA = traverse id
In particular what is the meaning of
traverse f = sequenceA . fmap f?
TL;DR
For beginner Haskell programmers specific class instances are more understandable and useful than abstract class definitions. It is better understanding and using the IO Monad, or the Maybe Monad, than knowing perfectly the theory behind the generic Monad class definition. For the same reasons, it is better understanding different instances of
Traversable class, than the abstract theory behind it.
Traverse a List applying Maybe semantic
Traversable uses functions with two generic types:
f that is an
Applicative context,
t that is a
Foldable Functor.
We will start with an example using
Maybe for the applicative part (the
f), and
List for the
Functor part (the
t).
Maybe has a simple and clear
Applicative semantic: stop the computation and return
Nothing when one of intermediate passages returns
Nothing.
List has a simple
Functor semantic:
fmap applies a function to every element of the list.
sequenceA
The
sequenceA function became
sequenceA :: [Maybe a] -> Maybe [a]
Studying type definition, the semantic is clear: extract
Just from the elements of the list, and if there is any
Nothing element, return
Nothing instead of the list.
{-# LANGUAGE ScopedTypeVariables #-}
module Main where
import Data.Traversable
import Control.Applicative
import Data.List as L
-- | All the tests of the code assertions.
main = putStrLn $ show $ L.all id [
mtest1
, mtest2
, mtest1M
, mtest2M
, mtest3
, mtest4
, mtest3M
, mtest4M
, mtest4M'
, stest1
, stest2
, stest3
, ltest1
, ltest2
]
We will remove
Just from the list:
mf1 :: Maybe [Int]
mf1 = sequenceA [Just 1, Just 2]
mtest1 :: Bool
mtest1 = (mf1 == Just [1, 2])
If we pass a
Nothing value, then the entire result became
Nothing:
mf2 :: Maybe [Int]
mf2 = sequenceA [Just 1, Just 2, Nothing]
mtest2 :: Bool
mtest2 = (mf2 == Nothing)
We can rewrite these functions using the do-notation:
mf1M :: Maybe [Int]
mf1M = do
x <- return 1
y <- return 2
return [x, y]
mf2M :: Maybe [Int]
mf2M = do
x <- return 1
y <- return 2
z <- empty
return [x, y, z]
So what is the semantic of
sequenceA for this specific instance of
Traversable? The semantic is self-explanatory studying its type
sequenceA :: [Maybe a] -> Maybe [a]. But sadly for us, we can not generalize it, as we will see in next sections.
traverse
The
traverse function became:
traverse :: (a -> Maybe b) -> [a] -> Maybe [b]
For playing with
traverse, we need a function returning
Maybe:
mf :: Int -> Maybe Int
mf x = if (even x) then Just x else Nothing
and then:
mf3 :: Maybe [Int]
mf3 = traverse mf [2,4]
mtest3 = (mf3 == Just [2,4])
All elements of the list are even, and so the same list without modifications is returned.
If we insert a not even element, then
Nothing is returned:
mf4 :: Maybe [Int]
mf4 = traverse mf [2,4,5]
mtest4 = (mf4 == Nothing)
As usual we can rewrite using the
do notation
mf3M :: Maybe [Int]
mf3M = do
x <- mf 2
y <- mf 4
return [x, y]
mf4M :: Maybe [Int]
mf4M = do
x <- mf 2
y <- mf 4
z <- mf 5
return [x, y, z]
Traversable defines also
mapM that is simply
traverse. We can rewrite in this way:
mf4M' :: Maybe [Int]
mf4M' = do
r <- mapM mf [2, 4, 5]
return r
mtest4M' = (mf4M' == mf4M)
In this case, the
traverse function captures the well known concept of
mapM inside the
Maybe Applicative.
Traverse a List applying List semantic
Now we will use an instance of
Traversable with
List both as container (for
t), and as
Applicative (for
f).
The List applicative behavior is similar to Prolog: it combines all possible combinations of generators, filtering on constraints.
The List functor behavior is the usual
map: it applies a function to every element of the list.
sequenceA
In this case, we have:
sequenceA :: [[a]] -> [[a]]
sequenceA = traverse id
where
traverse :: (a -> [b]) -> [a] -> [[b]]
traverse f = List.foldr cons_f (pure [])
where consF x ys = (:) <$> f x <*> ys
Due to specific implementation of
traverse for
List,
sequenceA became a combinatoric function performing a “transpose-like” operation, combining columns with lines:
stest1 = sequenceA [[1,2,3], [4,5]] == [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]
The corresponding function defined using Prolog-like semantic is
transposeAndCombine :: [[a]] -> [[a]]
transposeAndCombine linesAndCols = tc [] linesAndCols
where
tc :: [a] -> [[a]] -> [[a]]
tc r1 [] = return r1
tc r1 (xs:rs) = do
x <- xs
tc (r1 ++ [x]) rs
stest3 = let l = [[1,2,3], [4,5]]
in transposeAndCombine l == sequenceA l
In case of
Maybe the
Nothing value invalidates all the computations. In case of
List the value invalidating all computations is
[]:
stest2 = sequenceA [[1,2,3], [4,5], []] == []
In this case the
sequenceA function has a rather useful and reusable behaviour: transpose and combine columns with lines. Knowing this behavior in advance, the
sequenceA function can be called directly, without using the do-notation form that is less clear.
But this behavior is very different from the
Traversable instance with
Maybe and
Applicative. So the
Traversable class does not help us in predicting the
sequenceA semantic. We had to study it case by case.
traverse
traverse became:
traverse :: (a -> [b]) -> [a] -> [[b]]
traverse f = List.foldr cons_f (pure [])
where consF x ys = (:) <$> f x <*> ys
If we play with
traverse, we obtain:
lf :: Int -> [Int]
lf x = [x * 10, x * 100]
lxs :: [Int]
lxs = [1, 2]
lf1 :: [[Int]]
lf1 = traverse lf lxs
lfxs = [[10, 20], [10, 200], [100, 20], [100, 200]]
The semantic using Prolog-like rules is not immediate. A first but bad version is:
lf1M' :: [Int]
lf1M' = do
x <- lxs
y <- lf x
return y
ltest1M' = (lf1M' == [10, 20, 100, 200])
It isn’t correct because it combines too few things.
The behavior of
traverse is:
transposeAndCombine the results of the function applications with the list of possible arguments. The corresponding code is:
lf1AsTransf :: [[Int]]
lf1AsTransf = transposeAndCombine (map lf lxs)
ltest2 = (lf1AsTransf == lfxs)
In this form the code is clear, so we don’t derive a Prolog-like version.
In this case
traverse has not a basic and natural semantic. Probably there are not much cases in real-life code, where we want such strange and extreme combinatoric behavior. Probably we are more interested to the behavior of functions like
lfm1M', expressed with the do-notation.
Conclusions
After these examples, we can return to our original question: what is the meaning of
traverse f = sequenceA . fmap f? My lazy and arrogant answer is: I don’t bother! :-)
The motivations are:
- also if I can grasp the concepts behind
Traversable, it will not help in understanding real-life code using Traversable, because every instance of traverse and sequenceA has a very different and specific semantic.
- so I must study each instance of
Traversable in isolation, for understanding its behavior. This is similar to IO Monad, Maybe Monad, Either Monad: knowing the Monad concepts helps, but every instance has its proper semantic and usage case, and it must be mastered apart.
- maybe instance by instance, I can someday comprehend the concepts behind
Traversable, but up to date this can be postponed, because it seems more complex to master respect Functor and other base class.
- in the end I’m a poor OO programmer, not a mathematician expert of category-theory.
In Haskell there are very few class, and they are usually very abstract and tied to category theory concepts: Monad, Functor, Applicative, etc.. The laws of these class allows for nice combinations of instances. This is a sign of the power and effectiveness of category-theory. But these class are mainly used for writing composable DSLs or nice libraries. End-user code uses instead specific instances. Each instance has a specific semantic that can not be predicted only from the knowledge of the reference class. This is in contrast with the OO world where a parent class describes exactly the behavior of a child class. For example Monad is a class describing nice properties for composable actions. But the semantic of a List Monad (Prolog-like rules) is very different from the semantic of an Either Monad (actions with exceptions).
So
Traversable can represent many different things in Haskell. Also if I don’t understand completely its meaning, because it is too much abstract and tied to category-theory universe, this does not prevent me from studying and comprehending perfectly its specific instances, and using them in end-user code.
