Haskell Language Traversable Transforming a Traversable structure with the aid of an accumulating parameter
Example
The two mapAccum functions combine the operations of folding and mapping.
-- A Traversable structure
-- |
-- A seed value |
-- | |
-- |-| |---|
mapAccumL, mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
-- |------------------| |--------|
-- | |
-- A folding function which produces a new mapped |
-- element 'c' and a new accumulator value 'a' |
-- |
-- Final accumulator value
-- and mapped structure
These functions generalise fmap in that they allow the mapped values to depend on what has happened earlier in the fold. They generalise foldl/foldr in that they map the structure in place as well as reducing it to a value.
For example, tails can be implemented using mapAccumR and its sister inits can be implemented using mapAccumL.
tails, inits :: [a] -> [[a]]
tails = uncurry (:) . mapAccumR (\xs x -> (x:xs, xs)) []
inits = uncurry snoc . mapAccumL (\xs x -> (x `snoc` xs, xs)) []
where snoc x xs = xs ++ [x]
ghci> tails "abc"
["abc", "bc", "c", ""]
ghci> inits "abc"
["", "a", "ab", "abc"]
mapAccumL is implemented by traversing in the State applicative functor.
{-# LANGUAGE DeriveFunctor #-}
newtype State s a = State { runState :: s -> (s, a) } deriving Functor
instance Applicative (State s) where
pure x = State $ \s -> (s, x)
State ff <*> State fx = State $ \s -> let (t, f) = ff s
(u, x) = fx t
in (u, f x)
mapAccumL f z t = runState (traverse (State . flip f) t) z
mapAccumR works by running mapAccumL in reverse.
mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse
