scala - 函数式编程 : is foldLeft is the parent method of all functional methods such as foldRight, 映射、过滤器

Question

我正在学习 Scala，并且是函数式编程领域的新手。我看到大多数方法，例如 foldRight、map、filter、reduce ... 总是可以由 foldLeft 编写(由 foldLeft 编写 foldRight 用于使用尾递归)。

例如:

def map[A, B](l: List[A])(f: A => B): List[B] =
    foldRight(l, Nil: List[B])((x, xs) => Cons(f(x), xs))

def reverse[A](l: List[A]): List[A] =
    foldLeft(l, l)((xs, x) => Cons(x, xs))

def foldRight[A, B](l: List[A], z: B)(f: (A, B) => B): B =
    foldLeft(reverse(l), z)((xs, x) => f(x, xs))

在进入函数式编程世界之前，我认为map 和reduce 是函数式编程的两种基本方法。从这两个方法，我可以构建更复杂的方法。但基于上面的例子，我认为 foldLeft 应该是所有功能方法的基础，例如 map、filter、...

在函数式编程世界中是这样吗？

谢谢

Answer 1

我要把我的评论扩展成一个答案。

让我们从一个名为 Bunch[T] 的类型开始，它是 Traversable[T]，这是所有 Scala 集合的基本特征。它实现了所有常见的 monadic 东西，比如 map[U](f: T=>U) 等。

现在让我们开始根据它们的签名对所有方法进行分类。在下面，U 是 T 的父类(super class)型:

• 遍历:其实有两个子类:
  • shape-preserving:这些定义了 Bunch[U] 的返回类型；示例: map ；
  • non-shape-preserving:这些定义了 Iterator[T]、Traversable[T]、Traversable 的返回类型[U]等；示例:迭代器；
• selecting:这些定义了 T 的返回类型；例子 head;
• maybeSelecting:这些定义了 Option[U]
的返回类型
• 聚合:这些定义了 U 的返回类型；示例:左折叠；
• 测试:这些定义Boolean 的返回类型；示例:空；
• side-effecting:这些定义了 Unit 的返回类型；例子 foreach;
• 等等

这些方法中的每一个都与其他方法有着根本的不同。有些，例如聚合，需要对集合进行完整遍历(例如，这在 Stream 上是不可能的)。其他人没有。

我们可以为这些方法类中的每一个定义一个“父”方法。例如，我称为“副作用”的类的父方法显然是 foreach。我认为将 foldLeft 称为“聚合”方法的“父亲”可能是合理的。但我认为，总的来说，我们一定会遇到这种方法的问题。您不能总是根据另一种方法来定义一种方法。 map 本身可以根据其他方法定义，但它需要两个:flatMap 和“unit”，一个构造方法，因此不在我的列表中。