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

函数式编程现在已经被越来越多地被应用到工业软件中，例如，应用广泛的编程语言 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 环境），欢迎尝鲜。