summaion by mapM on State vs. by foldl

sum-mapm.hs

sum''''' :: Num a => [a] -> a
sum''''' xs = snd $ foldr h (\s -> ((), s)) xs 0
  where
    h :: Num a => a -> (a -> b) -> a -> b
    h x k = \s -> k (s + x)

{-

snd $ foldr h (\s -> ((), s)) xs 0
 = (snd . foldr h (\s -> ((), s)) xs) 0
 = (fmap snd $ foldr h (\s -> ((), s)) xs) 0
 = (fmap snd . foldr h (\s -> ((), s))) xs 0

foldrの融合則をふたたび適用する。
(h x :: (a -> b) -> (a -> b))が(a ->)上の自然変換だから、

fmap snd (h x k) = h x (fmap snd k)

よって

snd $ foldr h (\s -> ((), s)) xs 0
  = foldr h (fmap snd (\s -> ((), s))) xs 0
  = foldr h (\s -> s) xs 0
  = foldr h id xs 0

-}

{-さすがに長くなってきたので、プライムをやめる-}
sum6 :: Num a => [a] -> a
sum6 xs = foldr h id xs 0
  where
    h :: Num a => a -> (a -> b) -> a -> b
    h x k = \s -> k (s + x)

sum7 :: Num a => [a] -> a
sum7 xs = go xs 0
  where go = foldr h id
        h x k = \s -> k (s + x)

{-

xs に関して場合分けしてみる。

go []     acc
  = foldr h id [] acc
  = id acc
  = acc
go (x:xs) acc
  = foldr h id (x:xs) acc
  = h x (foldr h id xs) acc
  = (\s -> foldr h id xs (s + x)) acc
  = foldr h id xs (acc + x)
  = go xs (acc + x)

まとめると、

go []     acc = acc
go (x:xs) acc = go xs (acc + x)

これはすなわち

go xs acc = foldl (+) acc

-}

sum8 :: Num a => [a] -> a
sum8 xs = foldl (+) 0 xs