编程语言/函数式编程

函数式编程语言

声明式编程的理念是定义环境工作规则，然后让语言找出其他所有内容。这与过程式语言形成对比，在过程式语言中，人们会精确地告诉机器该做什么。函数式编程可以是实现声明式编程风格的一种方式。一个经典的例子是阶乘函数。定义新函数的第一步是首先处理平凡情况。那么，0 的阶乘将被定义为 1。下一步是通过一种最终会解析为简单情况的方式来定义非平凡情况。那么，n 的阶乘将被定义为 n 乘以小于 n 的阶乘

fac 0 = 1

fac n = (fac (n-1)) * n

像这样天真的实现比“for”循环使用更多的内存和处理时间（它使用 O(n) 栈空间），但这可以通过简单的更改来解决，使用累加器参数使编译器或解释器能够消除函数调用成本

facb 0 acc = acc

facb n acc = facb (n-1) (n*acc)

fac n = facb n 1

函数式编程有很大的用途。人们可以将函数式语言用作代码原型——在许多情况下，编写函数式代码并证明它会产生预期结果比使用过程式语言更容易——然后使用过程式技术对其进行优化。函数式技术在遍历二叉树方面非常有效。

待办事项：只需描述流行的函数式语言与 lambda 演算的不同之处，重要的是副作用（但要提到 Haskell）
- Scheme 和 ML 都具有内置类型，例如整数、浮点数、列表和字符串
- Scheme 具有尾调用优化
- Scheme 具有多参数函数，而不是柯里化
- Scheme 对所有结构使用函数式表示法，需要括号
- Scheme 具有卫生宏
- ML 是静态类型，带有类型推断
- ML 具有模式匹配结构
- ML 只有单参数函数，但通过柯里化和元组模拟了多个参数
- ML 对函数调用使用 lambda 演算表示法（即，不需要括号），但对内置结构使用关键字（即，它没有对 if 使用函数式表示法）

由于 lambda 保留对外部范围中引用的变量的引用，而这些函数可以在调用函数已经返回很久之后被存储和调用，因此使用 lambda 的语言具有垃圾回收。函数式编程是声明式编程的一个子集，它专注于编写“纯函数”。函数式编程范式是为了明确地支持对问题解决的纯函数方法而创建的。函数式编程是一种声明式编程形式。相比之下，大多数主流语言（包括面向对象编程 (OOP) 语言，如 C#、Visual Basic、C++ 和 Java）主要是为了支持命令式（过程式）编程而设计的。在计算机科学中，函数式编程是一种编程范式——一种构建计算机程序结构和元素的风格——它将计算视为对数学函数的求值，并避免改变状态和可变数据。它是一种声明式编程范式，这意味着编程是通过表达式或声明而不是语句完成的。在函数式代码中，函数的输出值仅取决于传递给函数的参数，因此每次使用相同的值为参数 x 调用函数 f 两次都会产生相同的结果 f(x)；这与过程依赖于局部或全局状态形成对比，局部或全局状态可能会在不同时间使用相同参数但不同程序状态调用时产生不同的结果。消除副作用，即不依赖于函数输入的状态更改，可以使理解和预测程序行为变得容易得多，这是开发函数式编程的关键动机之一。

组合逻辑是由 Moses Schönfinkel 和 Haskell Curry 开发的等效理论基础。它最初是为了实现一种更清晰的数学基础方法而开发的。组合逻辑通常被认为比 lambda 更抽象，并且先于其发明。

词法范围与动态范围