Foldable and traversable
Foldable
The Foldable type class provides foldr and associated folding
functions for types which implement it.
class Foldable t where
foldr :: (a -> b -> b) -> b -> t a -> b
foldr
foldr is the right-associative fold function. It takes a combining
function, a base case and the Foldable to fold. The foldr
implementation for lists is as follows:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
sum can be defined using foldr:
sum :: (Num a) => [a] -> a
sum xs = foldr (+) 0 xs
The process of applying sum to the list [1,2,3] is as follows:
sum [1,2,3]
sum (1 : 2 : 3 : [])
foldr (+) 0 (1 : 2 : 3 : [])
1 + (foldr (+) 0 (2 : 3 : []))
1 + (2 + (foldr (+) 0 (3 : [])))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + (0)))
1 + (2 + (3))
6
foldl
foldl is the left associative fold function.
The below shows the same example as for foldr but with foldl.
sum [1,2,3]
sum (1 : 2 : 3 : [])
foldl (+) 0 (1 : 2 : 3 : [])
foldl (+) (0 + 1) (2 : 3 : [])
foldl (+) ((0 + 1) + 2) (3 : [])
foldl (+) (((0 + 1) + 2) + 3) []
((0 + 1) + 2) + 3
6
There is also foldl', which is the strict left associative fold
function. Instead of building up the results they are evaluated each
step. So instead of foldl (+) ((0 + 1) + 2) (2 : 3 : []) it becomes
foldl' (+) 3 (2 : 3 : []).
Traversable
The Traversable type class defines the sequenceA and traverse
functions for traversing data types.
sequenceA
sequenceA takes a traversable structure of applicatives and lifts the
whole structure into a single applicative.
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
An example is combining a list of Maybes into a Maybe containing a
list. sequenceA [Just 1, Just 2, Just 3] will give Just [1, 2, 3].
The type has gone from [Maybe Int] to Maybe [Int].
traverse
traverse takes a function to an applicative which is applied to each
element of the structure, the result of which is combined with
sequenceA.
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
An example of this is a function which integer divides 10 by a given
number, returning a Maybe and a list of numbers to try.
x = [0, 2, 4, 6]
y = [1, 3, 5, 7]
safe10Div n = if n /= 0 then Just (10 `div` n) else Nothing
traverse safe10Div x
Nothing
traverse safe10Div y
Just [10, 3, 2, 1]