函数式编程的基本概念与应用

posts/%E5%87%BD%E6%95%B0%E5%BC%8F%E7%BC%96%E7%A8%8B%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5%E4%B8%8E%E5%BA%94%E7%94%A8

前言

之前听说过函数式编程，也听说过 haskell 这类语言，其实像 Python, Java 这类语言其中有些地方也用到了函数式编程的思想（lambda 表达式），但又没具体去了解过其中的思想。之前 SXYZ 翻译了一遍关于函数式编程的文章 — 图解 Functor、Applicative、Monad，当时看由于不了解函数编程的基本思想，第一眼看过于抽象没有看懂。

不过最近 Youtube 推荐算法给我推荐一个关于函数式编程入门介绍的影片初探 Functional Programming：徹底改變程式思維 - 基礎概念篇，视频里面讲的很好，推荐大家观看。

编程范式

在了解函数式编程前，我们先了解下什么是编程范式（Programming paradigm）。编程范式是一种描述如何思考和组织计算机程序的方法。

目前有很多的编程范式，个人接触到的大致有这几类：

  • 命令式（Imperative）：强调程序的执行顺序和状态的变化。它的主要特点是使用变量、赋值语句和控制流语句（如循环和条件语句）等元素来描述计算机程序的执行方式。支持命令式的语言有 C、Java、Python 等。

  • 函数式（Functional）：强调将计算过程看作函数的求值过程，避免使用状态和可变数据。函数式编程的核心是函数，它们是纯函数（没有副作用）和高阶函数（可以将其他函数作为参数或返回值）的组合。Haskell、Lisp、Scala、Elixir 等都是函数式编程语言。

  • 面向对象（Object-oriented）：强调数据抽象、继承、多态和封装等概念。在面向对象编程中，程序由对象组成，对象包含数据和方法。C++、Java、Python、Ruby 等都是面向对象编程语言。

  • 声明式（Declarative）： 它们建造计算机程序的结构和元素，表达计算的逻辑而不用描述它的控制流程。这样的语言有 SQL 和 Prolog 等。

  • 面向接口（Interface-based）：强调程序应该面向接口（Interface）而不是具体实现，从而提高代码的可扩展性和可维护性。它与面向对象编程的思路相近，但更强调接口的重要性。常见的面向接口编程语言包括：Java、Golang 等。

  • 并行编程模型（Parallel）：强调如何编写能够有效利用多核和分布式系统的程序。并行编程可以通过使用多线程、进程或分布式计算等实现。C++、Java、Python 等都提供了对并行编程的支持。

以上这些范式常听说的就是面向对象了。面向对象将程序问题抽象为类从而进行实例化进而解决问题，这种方式比较符合人的直觉。而其他的编程范式也作为补充辅助程序开发，比如控制流程、并发处理等等。不过函数式编程在程序开发却很少能遇到或者说是注意到，其实其中的一些概念已经融入到程序的开发中了，下面我将说一下函数编程的核心思想。

函数式编程核心思想

函数式编程的核心思想是将计算视为一系列函数之间的组合，而不是一系列状态变化的操作。函数式编程中的函数通常是纯函数，即对于给定的输入，始终返回相同的输出，而不会对外部环境产生副作用。这使得函数可以像数学中的函数一样使用，无需考虑函数执行的顺序和副作用。函数式编程还强调了不可变性，即数据在创建后不能被修改。这可以避免许多并发问题，并且可以确保代码的可预测性。

另一个函数式编程的核心思想是高阶函数，即函数可以作为参数传递给其他函数，也可以作为返回值返回。这使得代码更加灵活和可重用。函数式编程通常使用递归代替循环，并使用函数组合和柯里化（Currying）等技术来处理复杂的问题。

这些思想可以使代码变得更加简洁并且可读性更强，但过度使用会导致代码变的不可读且不易于维护。

函数式编程概念

头等函数

头等函数（First-class function）指的是可以像其他类型的值一样被传递、赋值和使用的函数。在头等函数的概念下，函数被视为一等公民（First-class citizen），就像基本数据类型、字符串、对象等其他类型的值一样。这就意味着，函数可以作为别的函数的参数、函数的返回值，赋值给变量或存储在数据结构中。

在具有头等函数的编程语言中，函数可以被传递给其他函数作为参数，也可以从函数中返回作为结果。这使得编程变得更加灵活和高效。

下面是一个 JavaScript 的头等函数的例子，其中 myFunction 是一个头等函数，它被作为参数传递给另一个函数 higherOrderFunction，后者也是一个头等函数：

// 定义一个头等函数
const myFunction = function (x) {
  return x * x;
};

// 定义另一个头等函数，它接受一个函数作为参数
const higherOrderFunction = function (func) {
  const x = 2;
  const result = func(x);
  console.log(result);
};

// 调用 higherOrderFunction，并传入 myFunction 作为参数
higherOrderFunction(myFunction); // 输出：4

在上面的代码中，myFunction 接受一个参数 x 并返回 x * x 的结果。higherOrderFunction 接受一个函数作为参数，并将它应用到参数值 x = 2 上，然后将结果打印到控制台上。通过将 myFunction 作为参数传递给 higherOrderFunction，我们可以轻松地对 myFunction 进行复用，而不需要为 higherOrderFunction 定义多个版本来处理不同的函数。

纯函数

纯函数（Pure function）是指在相同输入条件下，总是返回相同输出结果，且不会对外部环境造成任何可观察的副作用的函数。

纯函数满足以下两个条件：

  • 输入确定，输出确定：给定相同的输入，纯函数总是返回相同的输出。

  • 无副作用：纯函数不会修改传入的参数，也不会对其他环境进行任何修改，包括修改全局变量、发起网络请求等等。它只是接受输入，处理输入，然后返回输出。

由于纯函数只依赖于传入的参数来计算结果，因此它具有以下优点：

  • 可缓存性：由于纯函数总是返回相同的结果，因此可以对纯函数的结果进行缓存，以便在未来的调用中快速重用，提高性能。

  • 易于测试：纯函数不依赖于外部环境，因此可以轻松编写单元测试，并且可以很容易地模拟传入的参数。

  • 可移植性：由于纯函数不依赖于外部环境，因此可以在不同的上下文中使用，并且不需要担心依赖的环境。

  • 并行可处理：由于纯函数没有副作用，因此可以在不同的线程中并行处理，提高性能。

递归

循环（Loop）在函数式编程中通常不是首选的控制流程方式，因为它会改变变量的状态，不符合函数式编程的不可变性原则。但是，函数式编程语言中也有一些循环的实现方式，比如 Haskell 中的forM_函数和 Scala 中的for表达式，它们允许我们使用循环来处理列表和其他集合。

递归（Recursion）在函数式编程中被广泛使用，因为它符合函数式编程的不可变性原则。函数式编程中的递归通常是尾递归（Tail recursion）的形式，即递归调用是函数的最后一个动作，这样编译器就可以优化递归，避免出现栈溢出的问题。在函数式编程中，递归常常用于实现高阶函数、处理列表、树和图等数据结构，以及实现一些常见算法。

尾递归

尾递归（Tail recursion）是指一个函数的最后一个动作是递归调用自身，而且递归调用的返回值不需要进一步处理，直接返回即可。这种递归调用的特殊形式称为尾递归调用。尾递归调用可以被编译器或解释器优化为迭代循环，从而避免出现栈溢出的问题。

尾递归优化的原理是，编译器或解释器会将尾递归调用转化为迭代循环，从而避免函数调用的开销和内存占用。这种优化方式在一些函数式编程语言中得到了广泛应用，比如 Haskell 和 Scheme。在 JavaScript 中，一些现代浏览器和 JavaScript 引擎（如 V8 引擎）也支持尾递归优化，但并不是所有的 JavaScript 引擎都支持该优化。

下面是使用 Javascript 实现尾递归的例子：

function factorial(n, acc = 1) {
  if (n === 0) {
    return acc;
  } else {
    return factorial(n - 1, acc * n);
  }
}
console.log(factorial(5)); // 输出120

在上面的代码中，factorial函数使用尾递归来计算 n 的阶乘。在每次递归调用中，通过传入一个累积值 acc 来避免了中间结果的存储，从而实现了尾递归调用。这种实现方式可以避免栈溢出的问题，从而计算较大的阶乘。

非尾递归

非尾递归（Non-tail recursion）是与尾递归对立的递归方式，也称为普通递归（Regular recursion）或者头递归（Head recursion）。在非尾递归中，递归调用并不是函数的最后一个动作，递归调用的返回值还需要进一步处理才能返回。这种递归方式会使得每次递归调用都会创建新的栈帧，导致栈空间的浪费，容易引起栈溢出。

下面是使用 Javascript 实现非尾递归的例子：

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
console.log(factorial(5)); // 输出120

在上面的代码中，factorial函数使用非尾递归来计算 n 的阶乘。在每次递归调用中，递归调用的返回值还需要乘以一个值 n，从而不能直接返回，需要创建新的栈帧来保存中间结果，这种实现方式容易引起栈溢出的问题。

求值策略

函数式编程中的求值策略有两种：严格求值和非严格求值。

严格求值

严格求值（Strict evaluation），也称为应用序求值（Applicative order evaluation），是指在函数调用时立即求值。具体来说，当一个函数被调用时，其参数必须先被求值，然后再将这些值传递给函数。这种求值策略在大多数编程语言中都是默认的。例如，C，Java 和 Python 都是采用严格求值。

严格求值的优点是简单直观，易于理解和调试。缺点是它可能会浪费计算资源。如果一个函数的某些参数在函数体中没有被使用，那么在调用该函数时仍然会对这些参数进行求值，这可能会导致计算资源的浪费。

在 JavaScript 中，函数默认采用严格求值：

function add(a, b) {
  return a + b;
}

let result = add(2 + 3, 4 * 5); // 先计算 2+3 和 4*5，然后传递给 add 函数进行计算
console.log(result); // 输出 22

在上面的代码中，调用 add 函数时，先计算参数 2+3 和 4*5，然后将它们的结果传递给 add 函数进行计算。

非严格求值

非严格求值（Non-strict Evaluation），也称为正则序求值（Normal order evaluation），是指在函数调用时不立即求值。具体来说，当一个函数被调用时，它的参数并不会立即被求值，而是将其表达式表示的值延迟到需要使用时再进行求值。这种求值策略在函数式编程语言中较为常见。例如，Haskell 和 Lisp 都采用非严格求值。

非严格求值的优点是它可以避免计算不必要的参数值，从而提高程序的效率。它还可以支持一些有用的编程技术，如惰性求值和无限数据结构。缺点是它可能会导致一些语义上的困惑，例如当多个函数调用共享同一个参数时，可能会导致参数的多次求值。

要实现非严格求值，可以使用 JavaScript 的闭包和惰性求值。下面是一个简单的示例：

function addLazy(a, b) {
  return function () {
    return a() + b(); // 延迟计算 a 和 b 的值，直到这个函数被调用时才进行求值
  };
}

let resultLazy = addLazy(
  () => 2 + 3,
  () => 4 * 5
);
console.log(resultLazy()); // 输出 22

在上面的代码中，我们定义了一个名为 addLazy 的函数，它接受两个参数 a 和 b，这两个参数都是函数类型。addLazy 函数返回一个闭包函数，这个闭包函数会在被调用时才对 a 和 b 的值进行求值。

注意，在 addLazy 函数中，我们并没有对 a 和 b 的值进行求值。相反，我们将 a 和 b 包装在一个闭包函数中，并将这个闭包函数返回。这样，在调用 resultLazy 时，它才会对 a 和 b 的值进行求值，然后将结果相加返回。

类型系统

函数式编程语言的类型系统通常基于 lambda 演算，这种类型系统被称为 λ-演算类型系统。它们的基本概念是函数和类型之间的一一对应关系，即每个函数都有一个输入类型和一个输出类型。这种类型系统强调函数的纯粹性和不可变性，它通过限制可接受的输入类型和输出类型来帮助确保函数的正确性。

在 λ-演算类型系统中，类型是通过简单的基本类型（如整数、布尔值、字符串等）以及更复杂的类型构造器（如列表、元组、函数等）组合而成的。类型检查器会检查每个函数的输入和输出类型是否匹配，并尝试确定每个表达式的类型。

函数式编程语言的类型系统通常具有以下特点：

  • 静态类型检查：类型检查通常是在编译时进行的，而不是在运行时进行的。这有助于提高程序的性能和可靠性。

  • 类型推导：编译器可以根据上下文自动确定表达式的类型，而无需显式指定。

  • 多态类型：可以编写可以适用于多种类型的函数。这有助于提高代码的复用性和可读性。

  • 高阶类型：类型可以作为参数传递和返回值返回。这使得可以编写更通用和灵活的函数。

引用透明

引用透明（Referential transparency）指的是一个表达式可以被它的值所代替，而不会影响程序的行为。换句话说，如果一个函数在同样的输入下总是返回同样的输出，那么它就是引用透明的。

假设我们有一个普通的 JavaScript 函数 add，它的功能是将两个数字相加并返回结果。我们可以这样定义它：

function add(a, b) {
  return a + b;
}

这个函数是不是引用透明的呢？答案是不一定。如果 a 和 b 是相同的值，那么 add(a, b) 总是返回相同的结果，因此它是引用透明的。但是如果 a 和 b 是可变的对象或数组，那么函数就不是引用透明的了，因为它们的值可能在函数调用期间被修改。例如：

let x = [1, 2, 3];
let y = [4, 5, 6];

function add(a, b) {
  a.push(...b); // 修改了 a
  return a.reduce((acc, val) => acc + val, 0);
}

console.log(add(x, y)); // 输出 21
console.log(x); // 输出 [1, 2, 3, 4, 5, 6]

在上述代码中，我们将两个数组作为参数传递给 add 函数，然后将它们合并在一起，并返回它们的总和。虽然这个函数在同样的输入下总是返回相同的结果，但是它不是引用透明的，因为它修改了它的输入参数 a，从而产生了副作用。

相比之下，如果我们用函数式编程的方式重新实现 add 函数，就可以确保它是引用透明的。例如，我们可以使用纯函数 concat 将两个数组连接在一起，然后使用 reduce 函数计算它们的总和，而不会对原始数组进行任何修改。这样实现的函数不仅更容易理解和测试，而且还可以获得更好的性能，因为它可以进行更有效的优化。代码如下：

function add(a, b) {
  return a.concat(b).reduce((acc, val) => acc + val, 0);
}

let x = [1, 2, 3];
let y = [4, 5, 6];

console.log(add(x, y)); // 输出 21
console.log(x); // 输出 [1, 2, 3]

数据结构

函数式编程中的数据结构通常是不可变的，即它们的值一旦被创建就不能被修改。这与传统的命令式编程方式有所不同，命令式编程中的数据结构通常是可变的，即它们的值可以在程序执行过程中被修改。

不可变数据结构有助于提高程序的可靠性、可维护性和可测试性。不可变数据结构在多线程环境中更容易进行并发访问，因为多个线程可以同时访问同一个不可变数据结构，而不需要担心数据竞争和并发修改的问题。同时，不可变数据结构还可以被用来实现引用透明的函数，因为它们的值不会在函数调用期间被修改。

函数式编程中常见的不可变数据结构包括：数组、链表、树、映射和集合。

使用场景

函数式编程的优点可以为其他编程范式提供一些借鉴。在实际开发中，我们可以根据具体情况选择使用函数式编程的某些特点，从而提高代码的可读性、可测试性、可复用性和可维护性。

纯函数

对于固定的数学计算，数据转换，缓存计算等可以将其定义为纯函数进行调用。这样易于理解函数的自身也利于理解调用函数的上下文代码，更易于对定义函数的测试。在多线程条件下由于多个线程会共享同一个状态，因此使用纯函数可以避免不同线程之间的数据污染和竞态条件。但由于纯函数的定义，无法作用与全局，只试用于局部变量处理。当传输的参数过多时，程序将变得不易读。

头等函数

闭包

头等函数可以形成闭包，这允许函数保留对其创建时作用域中变量的引用。通过使用闭包，我们可以在函数之间共享状态，从而实现更高效的代码。

函数数组

  • 事件处理程序：在某些情况下，我们需要在一个特定事件发生时调用一系列函数。例如，当用户单击按钮时，我们可能需要触发多个处理程序来执行不同的操作。使用函数数组，我们可以将所有这些处理程序组织在一起，并在需要时逐一调用它们。

  • 路由器处理：在 Web 开发中，路由器用于将 HTTP 请求映射到不同的处理程序函数。使用函数数组，我们可以将所有这些处理程序组织在一起，并在路由器中动态选择正确的处理程序。

  • 插件系统：在某些应用程序中，我们可能希望允许用户编写自己的插件来扩展功能。函数数组可以用于存储和管理所有可用的插件函数，并在运行时动态选择和调用它们。

  • 算法：在一些算法问题中，我们需要同时对多个函数进行操作。使用函数数组，我们可以将所有这些函数组织在一起，并在需要时逐一调用它们。

惰性求值

  • 延迟加载：在一个大型的应用程序中，有些资源可能只有在用户请求时才需要加载，这种情况下使用惰性求值就非常有用。例如，当用户浏览网页时，只有在他们点击链接时才需要加载链接指向的页面。

  • 无限列表：惰性求值可以用来表示无限列表。例如，一个无限的斐波那契数列可以通过一个递归函数来定义，该函数只计算前两个数的和，而不需要事先计算所有数的值。

  • 延迟计算：有些计算可能非常耗时，而且只有在需要时才需要执行。在这种情况下，使用惰性求值可以避免不必要的计算，提高程序的性能。例如，一个大型的数据集合中可能只需要查找其中的一小部分数据，使用惰性求值可以避免计算未使用的数据。

  • 缓存：惰性求值可以用来实现缓存。例如，在一个网络应用程序中，当用户请求某个页面时，服务器可以使用惰性求值来缓存该页面的内容，当下一次用户请求同样的页面时，可以直接返回缓存中的结果，而不需要重新计算。

  • 延迟处理：有些处理可能需要等到所有的数据都可用之后才能执行，例如对一组数据进行排序。在这种情况下，使用惰性求值可以将处理延迟到数据全部可用之后，从而避免不必要的计算和内存开销。

参考链接