藉助累積引數轉換可遍歷結構

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