Scala:编写foldLeft的常见实践

Question

在函数式编程中，有两种重要的方法：foldLeft和foldRight。下面是foldRight的实现

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tails: List[A]) extends List[A]

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

下面是foldLeft的实现

  @annotation.tailrec
  def foldLeft[A, B](ls: List[A], z: B)(f: (B, A) => B): B = ls match {
    case Nil => z
    case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
  }
}

我的问题是:我从很多文献中读到，他们经常把f函数的顺序是：f: (B, A) => B而不是f: (A, B) => B。为什么这个定义更好？因为如果我们使用其他方式，它将具有与foldLeft相同的签名，并且它会更好。

Answer 1

因为foldLeft在遍历过程中“改变”了cons结构：

foldRight(Cons(1, Cons(2, Nil)), z)(f) ~> f(1, f(2, z))
                                            ^  ^
                                            A  B
foldLeft(Cons(1, Cons(2, Nil)), z)(f) ~> f(f(z, 2), 1)
                                           ^        ^
                                           B        A

而且由于它以相反的顺序访问conses，所以类型也传统上是反转的。当然，参数可以互换，但如果你有一个非交换操作，并且期望“传统”行为，你会感到惊讶。

Answer 2

...if我们使用其他方式，它将具有与foldLeft相同的签名，并且它会更好。

不，我认为那不会更好。如果它们具有相同的签名，那么如果您打算使用一个签名，但无意中输入了另一个签名，则编译器将无法捕获它。

A/B顺序也很方便地提醒了B (初始或“零”)值与A元素集合的关系。

foldLeft: B-->>A, A, A, ...   // (f: (B, A) => B)
foldRight: ... A, A, A<<--B   // (f: (A, B) => B)