テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

(haskell report) TraversableのmapAccumL

forMなどで単にTraversableをたどるのではなく, その過程でaccumulativeな計算をしたい場合がある. 例えば, 今までに起こったエラーの数は?, 現在何番目か?などを記録していく.

これは, 明らかにStateを使えば技術的には出来るが, 現実的には結構めんどくさい. しかしよくある処理なので, 便利な関数が用意されている. mapAccumL, mapAccumRである. 名前から分かる通り, mapしながらaccumする.

型は以下. 自明

Prelude Data.Traversable> :t mapAccumL
mapAccumL
  :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)

利用例は以下. aはaccであり, bは今の値である. ペアの左側は新しいaccの計算であり, 右側はmapに相当する計算である.

Prelude Data.Traversable> mapAccumL (\a b -> (a+b, b*2)) 0 [1,2,3]
(6,[2,4,6])

実装について調べる.

newtype StateL s a = StateL { runStateL :: s -> (s, a) }

instance Functor (StateL s) where
    fmap f (StateL k) = StateL $ \ s -> let (s', v) = k s in (s', f v)

instance Applicative (StateL s) where
    pure x = StateL (\ s -> (s, x))
    StateL kf <*> StateL kv = StateL $ \ s ->
        let (s', f) = kf s
            (s'', v) = kv s'
        in (s'', f v)

-- |The 'mapAccumL' function behaves like a combination of 'fmap'
-- and 'foldl'; it applies a function to each element of a structure,
-- passing an accumulating parameter from left to right, and returning
-- a final value of this accumulator together with the new structure.
mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL f s t = runStateL (traverse (StateL . flip f) t) s

これはかなりうざいが, やりたいことは, traverseのf :: (a -> f b)のfをStateにして, State伝搬の文脈を組み入れることである. だからまず, flipによってb -> a -> (a, c)を作り, これとStateLをつなぎ, b -> StateL a c(f = StateL a)を作る. これをTraversableのt bに適用して, StateL a (t c)を作る. 最後に, runStateLを適用すれば, (a, t c)を得ることが出来る.

Haskellは良い.