函数式编程的基本概念与应用
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 请求映射到不同的处理程序函数。使用函数数组,我们可以将所有这些处理程序组织在一起,并在路由器中动态选择正确的处理程序。
插件系统:在某些应用程序中,我们可能希望允许用户编写自己的插件来扩展功能。函数数组可以用于存储和管理所有可用的插件函数,并在运行时动态选择和调用它们。
算法:在一些算法问题中,我们需要同时对多个函数进行操作。使用函数数组,我们可以将所有这些函数组织在一起,并在需要时逐一调用它们。
惰性求值
延迟加载:在一个大型的应用程序中,有些资源可能只有在用户请求时才需要加载,这种情况下使用惰性求值就非常有用。例如,当用户浏览网页时,只有在他们点击链接时才需要加载链接指向的页面。
无限列表:惰性求值可以用来表示无限列表。例如,一个无限的斐波那契数列可以通过一个递归函数来定义,该函数只计算前两个数的和,而不需要事先计算所有数的值。
延迟计算:有些计算可能非常耗时,而且只有在需要时才需要执行。在这种情况下,使用惰性求值可以避免不必要的计算,提高程序的性能。例如,一个大型的数据集合中可能只需要查找其中的一小部分数据,使用惰性求值可以避免计算未使用的数据。
缓存:惰性求值可以用来实现缓存。例如,在一个网络应用程序中,当用户请求某个页面时,服务器可以使用惰性求值来缓存该页面的内容,当下一次用户请求同样的页面时,可以直接返回缓存中的结果,而不需要重新计算。
延迟处理:有些处理可能需要等到所有的数据都可用之后才能执行,例如对一组数据进行排序。在这种情况下,使用惰性求值可以将处理延迟到数据全部可用之后,从而避免不必要的计算和内存开销。