借助累积参数转换可遍历结构

两个 mapAccum 函数结合了折叠和映射的操作。

--                                                       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

这些函数概括了 fmap，因为它们允许映射的值取决于折叠中先前发生的事情。他们概括了 foldl / foldr，因为他们将结构映射到位并将其减少到一个值。

例如，tails 可以使用 mapAccumR 实现，其姐妹 inits 可以使用 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 是通过遍历 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 通过反向运行 mapAccumL 来工作 。

mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse