foldl by foldr

RWH上在讲述 functional programming 中的fold的时候举了个例子，说foldl也可以由foldr来实现，具体的代码如下：

foldl :: (a->b->a)->a->[b]->a
foldl f z xs = foldr step id xs z
 where step x g a = g (f  a x)

开始总是没想明白，昨天才恍然大悟，具体的例子如下，

foldl (+) 0 [1,2,3] -->
foldr step id [1,2,3] 0 -->
step 1 (step 2 (step 3 id)) 0 -->
step 2 (step 3 id) (1 + 0) -->
step 3 id ((1+0)+2) -->
id (((1+0)+2)+3)

特此记录一下，也算是脑子没白动。

章节的后面有一个与之相关的练习，用foldr实现takeWhile，倒是一个很好的回顾。先试着用foldl来实现一把，毕竟takeWhile应该从左边开始计算。

takeWhile_foldl :: (a->Bool)->[a]->[a]
takeWhile_foldl p xs = head (foldl step [[]] xs)
                     where step x y | p y = init x ++ [last x ++ [y]]
                                    | otherwise = x ++ [[]]

然后，根据上面给出的foldl的foldr解法得到下面的实现:

takeWhile_foldr :: (a->Bool)->[a]->[a]
takeWhile_foldr p xs = head (foldr step id xs [[]])
                        where step x g a | p x = g (init a ++ [last a ++ [x]])
                                         | otherwise = g (a ++ [[]])