聊一聊函数式编程能解决什么问题？（以 MoonBit 月兔为例）

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 156 天前的主题，其中的信息可能已经有所发展或是发生改变。

函数式编程现在已经被越来越多地被应用到工业软件中，例如，应用广泛的编程语言 Java 在迭代到 Java 8 的时候提供了函数式编程的支持；流行的前端框架 React.js 基于函数式编程思想定义了全新的框架；云服务厂商基于函数式编程思想提供了各类云函数接口……函数式编程思想的应用已经不胜枚举。想要知道函数式编程能帮助解决什么问题，不妨就让我们从软件工程的角度来分析一下。

软件工程开发需要具备以下素质：

健壮性：程序应当是正确的，同时也能正确地处理错误；
适应性：程序能根据需求进行迭代，容易增加新的功能；
可重用性：开发过的组件可以被重复使用。

我们分别从这几个角度来讨论。我们的代码案例将使用月兔编程语言。

健壮性

对于函数式思想而言，重要的是引用透明性（ referential transparency ）。引用透明性允许我们将任意一个表达式替换为相应的值而不改变程序的行为。这就大大地降低了我们理解程序的难度，使得程序更易论证其正确性、也更易维护。

对于定义的函数而言，这就意味着对于相同的输入，总是会有相同的输出。例如，以下代码虽然用到可变变量，但是在不考虑内存的情况下，亦是函数式的：

fn fib_mut(num: Int) -> Int64 {
  var map: AVLMap[Int, Int64] = put(put(make(num), 1, 1L), 2, 1L) // 变了吗？如变
  fn aux(num: Int) -> Int64 {
    match get(map, num) {
      Some(result) => result
      None => {
        let result_1 = aux(num - 1)
        let result_2 = aux(num - 2)
        map = put(map, num, result_1 + result_2)
        result_1 + result_2
      }
    }
  }
  aux(num)
}

我们可以将程序各处的fib_mut(60)改为1548008755920L而不改变结果。这样的函数被称为纯函数。

相对的，非纯函数在运算过程中会产生副作用：输出、发送网络请求、改变变量的值等等。但即便如此，利用IO单子，我们依然可以获得引用透明性。例如，如果我们定义一个输出的操作为：

fn output[T : Show](value : T) -> IO[Unit] {
  IO::of(fn() { print(value) })
}

之后，我们定义运算x、y、z并执行y和z：

fn init {
  let x = output("x")
  let y = x.flatMap(fn(_u) { x })
  let z = output("x").flatMap(fn(_u) { output("x") })
  run(y)
  print(" | ")
  run(z)
  println("")
} // 输出："xx | xx"

如果我们运行这段代码，我们会发现，如果我们将y中的x全部替换为output("x")，也就是它的定义，那么我们依然会有完全相同的副作用：输出两遍“x”。因此，我们同样获得了引用透明性。

样例代码：斐波那契数列：https://try.moonbitlang.com/#0e0964c9； IO 单子：https://try.moonbitlang.cn/#beb88f06；可在浏览器（包括手机浏览器）直接打开运行。

可重用性

函数式编程的重要特点是函数是一等公民，也就是可以将函数作为参数传递、或作为运算结果返回函数。随之而来的高阶函数允许我们在粒度更小的函数级别进行功能复用。

例如，对于列表这个结构，我们可以定义如下的fold_left函数对列表数据进行逐个整合：

fn fold_left[A, B](self: List[A], f: (B, A) -> B, init: B) -> B {
  match self {
    Nil => init
    Cons(hd, tl) => fold_left(tl, f, f(init, hd))
  }
}

通过使用这个高阶函数，我们可以用各种方式对其中的数据进行整合：求和、数数等，例如：

fn sum(list: List[Int]) -> Int {
  list.fold_left(fn (i, j) { i + j }, 0)
}
fn count[T](list: List[T]) -> Int {
  list.fold_left(fn (n, _t) { n + 1 }, 0)
}

可以看到，我们只需简单地替换参数：一个简单的函数，即可在复用这段逻辑的基础上，实现多种不同的功能。

同时，函数式编程还允许我们通过高阶函数，来复用控制逻辑的组合。例如，我们可以定义函数and_then来定义顺序运算，也可以定义until对一个值进行迭代直到满足条件，或是用switch来根据条件选择运算：

fn and_then[A, B, C](f : (A) -> B, g : (B) -> C) -> (A) -> C {
  fn(a) { g(f(a)) }
}

fn until[A](predicate : (A) -> Bool, iterate : (A) -> A) -> (A) -> A {
  fn aux(a) {
    if predicate(a) {
      a
    } else {
      aux(iterate(a))
    }
  }

  aux
}

fn switch[A, B](predicate : (A) -> Bool, f : (A) -> B, g : (A) -> B) -> (A) -> B {
  fn(a) {
    if predicate(a) { f(a) } else { g(a) }
  }
}

而这些控制结构本身作为函数，也可以作为参数被传递、组合。例如著名的冰雹猜想，我们便可以如此模拟，来获得从给定数n到1的流程：

fn 冰雹猜想(n : Int) -> List[Int] {
  let aux = until(
    and_then(head, fn (i) { i == 1}),
    switch(
      and_then(head, fn (i) { i % 2 == 0}),
      fn(list) { Cons(head(list) / 2, list) },
      fn(list) { Cons(3 * head(list) + 1, list) },
    ),
  )
  aux(Cons(n, Nil))
}

样例代码：https://try.moonbitlang.com/#c08051b1

适应性

提到适应性问题，那不由想到著名的表达式问题了。

表达式问题：假如我们需要有如下数学表达式：整数、加法表达式；有如下操作：计算表达式、转为字符串。例如：

enum Expr {
  Lit(Int) // 整数
  Add(Expr, Expr) // 加法
}

fn compute(expr : Expr) -> Int {
  match expr {
    Lit(i) => i
    Add(expr1, expr2) => compute(expr1) + compute(expr2)
  }
}

fn display(expr : Expr) -> String {
  match expr {
    Lit(i) => i.to_string()
    Add(expr1, expr2) => "(" + display(expr1) + " + " + display(expr2) + ")"
  }
}

let expr: Expr = Add(Lit(1), Lit(2))
fn init {
  println(compute(expr)) // 3
  println(display(expr)) // "(1 + 2)"
}

现在我们需要对程序进行拓展：添加数据结构，如乘法表达式；添加操作，如转为树状图。我们希望能尽可能少地修改原有的程序。

面向对象编程与函数式编程在这个问题上各有千秋。

普通的面向对象编程易于添加新的数据结构，却很难添加新的运算：添加新的数据结构只需要定义新的类，继承原有的类即可，而添加新的运算则须修改所有的现有的类；普通的函数式编程则易于添加新的操作，却很难添加新的数据结构：添加新的操作只需要定义新的函数即可，而添加新的数据结构意味着每一处模式匹配都会变得不完整，需要重新修改。面向对象编程可以用访问者模式来使得添加新的操作变得容易，但同时添加数据结构也会变得困难。

Oleg Kiseylov 教授等人提出的 Tagless Final 技术则允许我们利用函数式编程通常使用的类型类，以一种较为优雅的方式解决这个问题。

我们用类型类，根据表达式的不同元素，定义如下：

interface Expr  {
  Self::lit(Int) -> Self
  add(Self, Self) -> Self
}

之后，我们只需要根据不同的数据结构定义类型类的实例即可。例如针对计算操作，我们可以有如下定义：

struct Num { i : Int }

fn Num::lit(i : Int) -> Num { { i, } }

fn add(self : Num, other : Num) -> Num { { i: self.i + other.i } }

而针对显示操作，我们可以另行定义为：

struct Display {
  str : String
}

fn Display::lit(i: Int) -> Display { { str: i.to_string() } }

fn add(self: Display, other: Display) -> Display {
  let str_self = self.str
  let str_other = other.str
  { str: "(\(str_self) + \(str_other))"}
}

之后，我们可以用一个泛型函数定义我们的表达式，并且用不同的类型参数来生成对应的结果：

fn build_exp[T: Expr]() -> T { T::lit(1).add(T::lit(2)) }

fn init {
  let compute_result: Num = build_exp()
  println(compute_result.i) // 3
  let display_result: Display = build_exp()
  println(display_result.str) // "(1 + 2)"
}

到这一步，我们来看如何拓展数据结构，如何拓展操作。

拓展数据结构，只需要重新定义一个对应操作的类型类，并且对现有的操作都添加实现即可：

interface ExtendExpr  {
  mul(Self, Self) -> Self
}

fn mul(self : Num, other : Num) -> Num { { i: self.i * other.i } }

fn mul(self : Display, other : Display) -> Display {
  let str_self = self.str
  let str_other = other.str
  { str: "(\(str_self) * \(str_other))" }
}

fn build_extended[T: Expr + ExtendExpr]() -> T {
  T::lit(1).mul(T::lit(2).add(T::lit(3)))
}

fn init {
  let compute_extended : Num = build_extended()
  println(compute_extended.i) // 5
  let display_extended : Display = build_extended()
  println(display_extended.str) // "(1 * (2 + 3))"
}

拓展操作，只需要重新定义一个数据结构，并且对现有的类型类添加实现即可，例如在这里，我们添加一个输出为后缀表达式的操作：

struct PostFix { expr: String }

fn PostFix::lit(i: Int) -> PostFix {
  { expr : i.to_string() }
}

fn add(self: PostFix, other: PostFix) -> PostFix {
  let str_self = self.expr
  let str_other = other.expr
  { expr: "\(str_self) \(str_other) +"}
}

fn mul(self: PostFix, other: PostFix) -> PostFix {
  let str_self = self.expr
  let str_other = other.expr
  { expr: "\(str_self) \(str_other) *"}
}

fn init {
  let postfix_extended : PostFix = build_extended()
  println(postfix_extended.expr) // "1 2 3 + *"
}

我们可以看到，函数式编程具有强大的适应性，而类型类的低耦合也允许我们更加自由地进行拓展。当然，这并不代表这是表达式问题的唯一解，或者说最优解，但是学习不同的编程思想可以拓宽我们的视野。

样例代码：https://try.moonbitlang.com/#bd103432

参考资料：https://userpages.uni-koblenz.de/~laemmel/TheEagle/resources/pdf/xproblem1.pdf与https://www.okmij.org/ftp/tagless-final/course/lecture.pdf

总结

我们在这里只提到了函数式编程的冰山一角。事实上，函数式编程还有很多优点可以应用在工程中。例如，不可变性可以避免在并行程序中产生数据冲突；不可变性也可以让编译器进行大量激进的优化，以获得较高性能。

从软件工程的角度，我们可以看到，函数式编程可以让我们开发出健壮、可适应、可重用的软件，来更好地面对工程中的需求与挑战。但需要强调的是，函数式编程毕竟不能包打天下，因此，我们推荐采用多范式编程。月兔编程语言支持多范式编程（命令式、函数式、面向对象等），同时面向云原生开发（提供浏览器中的 IDE ，可编译到 WebAssembly ），面向 AI 开发（集成 AI 环境），欢迎尝鲜。

函数

expr

num

self

11 条回复 • 2023-11-27 10:14:55 +08:00

AntiFraud

156 天前

说起函数式编程，我就要再提一嘴我的大 Erlang 了。

villa2935

156 天前 via Android

这不又成 90 年代之前没对象的时代了。

bianhui

156 天前

再天花乱坠，你把求伯君、廖雪峰、，马士兵喊来，也是我的一把撸最好用。

tool2d

156 天前

函数式编程最大的问题，是没写过的人看不太懂，不太便于代码交流。

qaqLjj

156 天前

FP 和 OOP 这两种编程范式为什么会出现，解决了什么问题？

qaqLjj

156 天前

函数式编程（ FP ）和面向对象编程（ OOP ）是两种不同的编程范式，它们出现的原因是为了解决不同的问题和满足不同的编程需求。

**函数式编程（ FP ）**是一种编程范式，它将计算视为数学函数的求值过程。FP 强调使用纯函数（ Pure Function ）来进行计算，纯函数是指具有相同输入始终产生相同输出的函数，且没有副作用。FP 的主要特点包括：

1. **不可变性（ Immutability ）**：FP 鼓励使用不可变数据结构，即数据一旦创建就不能被修改。这样可以减少并发访问的竞争条件，简化代码的理解和调试。

2. **函数的高阶特性（ Higher-Order Functions ）**：FP 支持函数作为参数传递和返回值，可以将函数看作是一等公民。这使得代码更加灵活和可组合，可以通过组合和转换函数来构建复杂的逻辑。

函数式编程的出现主要是为了解决以下问题和需求：
- 处理大规模并行和分布式计算，因为纯函数可以避免共享状态和副作用，使得并行计算更加容易。
- 提高代码的可读性和可维护性，因为纯函数的结果仅依赖于输入，不会受到外部状态的影响。
- 减少 bug 和易于调试，因为纯函数的结果可预测且容易测试。

**面向对象编程（ OOP ）**是一种编程范式，它将程序组织为对象的集合，这些对象可以通过消息传递进行通信和交互。OOP 的主要特点包括：

1. **封装（ Encapsulation ）**：OOP 通过将数据和相关的操作封装在对象中，实现了数据的隐藏和保护。对象的内部状态只能通过公共接口进行访问和修改，提高了代码的安全性和可维护性。

2. **继承（ Inheritance ）**：OOP 支持类之间的继承关系，通过继承可以实现代码的重用和扩展。子类可以继承父类的属性和方法，并可以添加自己的特定功能。

3. **多态（ Polymorphism ）**：OOP 允许同一种类型的对象表现出不同的行为，这种特性称为多态。多态提高了代码的灵活性和可扩展性，使得可以处理不同类型的对象而无需修改相同的代码。

面向对象编程的出现主要是为了解决以下问题和需求：
- 模块化和代码重用，通过封装和继承可以将代码组织成可复用的模块和类。
- 复杂系统的抽象和建模，通过对象的概念可以更好地描述和解决现实世界中的问题。
- 团队协作和大型项目的开发，OOP 提供了一种结构化的方法，使得团队成员可以独立开发和维护不同的模块。

综上所述，函数式编程和面向对象编程是为了解决不同的问题和满足不同的需求而出现的。函数式编程强调纯函数和不可变性，用于处理并行计算和提高代码的可读性和可维护性。面向对象编程则通过封装、继承和多态来实现模块化、代码重用和团队协作。在实际开发中，可以根据具体的需求和场景选择合适的编程范式。