函数式编程

函数式编程将计算视为数学函数的求值，避免可变状态，并强调高阶函数、不变性以及等式推理。

Definition

函数式编程是一种编程范式，其中程序通过组合作用于不可变数据的纯函数来构建，从而表达式的求值仅依赖于其输入，并且不产生可观察的副作用。

Scope

本主题涵盖了以Lambda演算为基础的函数式范式：一等函数和高阶函数、不变性和引用透明性、递归、惰性求值、代数数据类型和模式匹配，以及使用单子（monads）和其他抽象来构造副作用。它阐述了纯函数如何有助于组合、推理和并行化。

Core questions

• 高阶函数和惰性求值如何提高模块化？
• 引用透明性在推理和优化方面有何益处？
• 在纯函数式环境中如何建模副作用？
• 函数式代码与Lambda演算和类型理论有何关系？

Key theories

高阶函数和惰性求值的“胶水”作用

休斯（Hughes）认为，函数式编程的模块化优势来自于高阶函数和惰性求值，它们充当了组合小型、可重用程序片段的“胶水”。

用于构造副作用的单子

瓦德勒（Wadler）展示了单子如何提供一种统一的、可组合的方式，将状态、异常和其他副作用贯穿于原本纯粹的函数式程序中。

函数式程序的代数

巴克斯（Backus）的函数级编程提出了一种组合子代数，其具有支持程序推理和转换的等式定律。

Clinical relevance

函数式技术，如不变性和纯函数，减少了与共享可变状态相关的错误类别，并使代码更易于测试和并行化。这些思想通过Lambda表达式、不可变集合以及流/Map-Reduce抽象，已广泛渗透到主流语言中。

History

函数式编程起源于丘奇（Church）的Lambda演算和麦卡锡（McCarthy）的Lisp（1958年）。1970年代和1980年代产生了ML、Miranda和Scheme；巴克斯（Backus）1977年的图灵讲座推动了对命令式编程风格的函数式批判。Haskell在1990年左右标准化了惰性、纯函数式编程，而瓦德勒（Wadler）基于单子的副作用处理使得纯函数式编程在实际任务中变得实用。

Debates

惰性求值与严格求值

函数式语言设计者们争论，惰性（按需调用）求值虽然能够实现优雅的无限结构和模块化，但与严格求值相比，其在推理空间和性能方面的成本是否值得。

Key figures

• John Hughes
• Philip Wadler
• John Backus
• Richard Bird
• Simon Peyton Jones

Seminal works

• hughes1989
• wadler1992
• backus1978
• bird1998

Frequently asked questions

什么是引用透明性？

如果一个表达式可以被其值替换而不改变程序的行为，那么它就是引用透明的，这在函数是纯粹的且数据是不可变的情况下成立。

函数式编程如何处理输入/输出和状态？

副作用通常被显式建模，例如通过单子或效应系统，这样副作用的顺序和存在性被捕获在类型中，而不是隐式地由可变性产生。