YeungYeah 的乱写地

FoldLeft and FoldRight

 Posts  

看 [[Scala 函数式编程]] 当中做的练习，还挺有意思。

实现了 foldLeft 合 foldRight 之后，如何使用 foldRight / foldLeft 实现 foldRight / foldLeft?

Hard: Can you write foldRight in terms of foldLeft? How about the other way around? Implementing foldRight via foldLeft is useful because it lets us implement foldRight tail recursively, which means it works even for large lists without overflowing the stack.

1
2
3
4
5
6
7

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = as match
    case Nil => z
    case x::xs => f(x, foldRight(xs, z)(f))

def foldLeft[A,B](as: List[A], z:B)(f: (B, A) => B): B = as match
    case Nil => z
    case x::xs => foldLeft(xs, f(z, x))(f)

看到这个第一反应想到一个很 trick 的想法: foldRight 其实不就等于 reverse 之后再 foldLeft 吗？刚好前面也用 foldLeft 实现了 reverse.

1
2
3
4

def reverse[A](list: List[A]): List[A] = foldLeft(list, List.empty[A])((acc, h) => h::acc)

def foldRightViaFoldLeft[A, B](l: List[A], acc: B, f: (A, B) => B): B 
    = foldLeft(reverse(l), acc)(f)

除了这种 trick 以外，还有没其他方法呢？搜了一下官方解答，给的另一种办法是这样的

1
2

def foldRightViaFoldLeft[A, B](l: List[A], acc: B, f: (A, B) => B): B =
    foldLeft(l, (b: B) => b)((g, a) => (b: B) => g(f(a, b)))(acc)

看了好一会，然后删掉自己重新一次之后，才理解过来。思路就是在 foldLeft 的过程，维护一个 acc 的函数，然后将前面的元素逐个塞到这个函数里面，越后面的元素塞在越里层，最右面的函数最先开始处理。通过 foldLeft 得到这个函数后，再传初值调用即可。

让 gpt 生成的一个例子

  • 假设我们有一个列表 List(1, 2, 3)，一个初始值 0，和一个函数 f = (a: Int, b: Int) => a + b。调用 foldRightViaFoldLeft_1(List(1, 2, 3), 0, (a, b) => a + b) 会构建如下的函数链：
    • 初始值是 (b: Int) => b。
    • 第一个元素 1：(g, a) => b => g(f(a, b)) 变成 (b: Int) => (b: Int) => b + 1。
    • 第二个元素 2：(b: Int) => ((b: Int) => b + 1)(b + 2)。
    • 第三个元素 3 ：(b: Int) => (((b: Int) => b + 1)(b + 2))(b + 3)。
  • 最终这个链会被应用到初始值 0 上，得到 0 + 3 + 2 + 1，即 6。

说实话有了思路，写起来也还是挺绕的，但是写着写着意识到，其实可以根据类型来判断填什么值，这样就很好写了。

相关文章：