Shane Xu's Home

In fact, we can even write foldl using foldr!

Understanding foldl in terms of foldr

If you want to set yourself a solid challenge, try to follow the above definition of foldl using foldr. Be warned: this is not trivial! You might want to have the following tools at hand: some headache pills and a glass of water, ghci (so that you can find out what the id function does), and a pencil and paper.

前几天群里有人发了篇文章：

5 Emerging Programming Languages With a Bright Future

这五门语言分别是：Elm, Kotlin, Rust, elixir, Crystal。

Elm，Hmm，不禁让我想起了两年前在小黑屋里的日子。这几年Elm有什么长足的进步吗？然后我竟然去YouTube上搜了下。然后看了下面的视频。

From Rails to Elm and Haskell - Richard Feldman

诚然，Elm的函数式编程的特性很吸引我。

上面的视频有一段关于

如何学习 haskell ：

呵呵。

然而，

I’ve tried learn Haskell...several times!

于是重新打开了翻开了很多次的，《Real World Haskell》。

这次从第四章开始吧。

下面是关于第四章中，foldl，foldr的内容。

先来看看foldl的定义

1: import Prelude(id)
2: 
3: foldl :: (a -> b -> a) -> a -> [b] -> a
4: foldl step zero (x:xs) = foldl step (step zero x) xs
5: foldl _ zero []        = zero

例如计算[Integer]的和：

1: import Prelude((+))
2: 
3: foldl (\a b -> a+b) 0 [1,2,3,4]
4: 
5: foldl (+) 0 [1,2,3,4]

而foldr的定义是这样的

1: foldr :: (a -> b -> b) -> b -> [a] -> b
2: foldr step zero (x:xs) = step x (foldr step zero xs)
3: foldr _ zero []        = zero

同样用foldr也可以计算[Integer]的和：

1: import Prelude((+))
2: 
3: foldr (\a b -> a+b) 0 [1,2,3,4]
4: 
5: foldr (+) 0 [1,2,3,4]

看似作用相同，但是foldl和foldr的计算步骤（顺序）是不一样的，foldl从左往右计算，而foldr则是从右往左。

比如把用foldl计算[Integer]的过程展开：

((((0) + 1) + 2) + 3) + 4

比如把用foldr计算[Integer]的过程展开：

(1 + (2 + (3 + (4 + (0)))))

重点来了，其实我们常用的 map :: (a -> b) -> [a] -> [b] 函数也可以用foldr来表达。

1: myMap f xs = foldr step [] xs
2:   where
3:     step x ys = f x : ys

filter :: (a -> Bool) -> [a] -> [a] 函数也可以用foldr来表达。

1: myFilter p xs = foldr step [] xs
2:   where
3:     step x ys
4:       | p x = x : ys
5:       | otherwise = ys

我们来说标题。事实上，foldl函数也能够用foldr来表达。

1: myFoldl :: (a -> b -> a) -> a -> [b] -> a
2: myFoldl f z xs = foldr step id xs z
3:   where
4:     step x g a = g (f a x)

然后《Real World Haskell》第四章的作者在写完上面这段代码之后，就写了本文开头引用的那段话。

foldr函数有三个参数，我们可以加上括号，来帮助思考

1: myFoldl :: (a -> b -> a) -> a -> [b] -> a
2: myFoldl f z xs = (foldr step id xs) z
3:   where
4:     step x g a = g (f a x)

整个函数的返回值是a，而z的类型也是a，那么括号中的表达式的类型为 a -> a，是一个从类型a到类型a的映射（入参类型为a，出参类型为a的函数）。而id这个函数，则是Prelude模块中的函数，也就是Identity function（恒等函数），恒等函数是数学中对于传回和其输入值相同的函数的称呼。也就是括号中foldr的初始值是identity function，其类型在此场景下为 a -> a。那么step函数的类型为：

step :: b -> (a -> a) -> (a -> a)

也可以写成

step :: b -> (a -> a) -> a -> a

那么上面代码中where后面step的参数声明中x、g、a的类型分别为：

1: x :: b
2: g :: a -> a
3: a :: a

同时 step x g 的类型为：

1: step x g :: a -> a
2: step x g = \a -> g (f a x)

当 xs = [] 时

(\a -> id a) z

当 xs = [x1] 时

(\a' -> ((\a -> id a) (f a' x1))) z

当 xs = [x2, x1] 时

(\a'' -> (\a' -> ((\a -> id a) (f a' x1))) (f a'' x2)) z

当 xs = [x3, x2, x1] 时

(\a''' -> (\a'' -> (\a' -> ((\a -> id a) (f a' x1))) (f a'' x2)) (f a''' x3)) z

以此类推。

大概就这样吧。