第二十四 λ演算

函数式编程 廖雪峰

λ演算

函数式编程的一个特点就是，允许把函数本身作为参数传入另一个函数，还允许返回一个函数！

优点：抽象程度高，代码简洁，代码可读性好。

24.1 概述

λ演算（Lambda Calculus）是由美国数学家 Alonzo Church 于 1930 年代提出的一种数学形式系统。它是函数式编程的理论基础，也是计算机科学中最重要的理论模型之一。

λ演算的核心思想极其简单：一切皆为函数。在λ演算中，没有变量赋值、没有循环、没有状态——只有函数的定义和应用。然而，正是这种极简的系统，被证明是图灵完备的，即它能够表达任何可计算的函数。

λ演算对现代编程语言产生了深远的影响：

• Lisp（1958年）直接受到λ演算的启发
• ML 家族语言（OCaml、Standard ML）将λ演算与类型系统结合
• Haskell 是纯函数式编程语言的典范
• Rust 吸收了函数式编程的许多特性，尤其是闭包和迭代器
• Java 从 8 开始引入 Lambda 表达式和 Stream API
• JavaScript、Python、C++ 等主流语言都支持 Lambda/闭包

24.2 λ演算的核心概念

24.2.1 λ表达式的语法

λ演算中只有三种基本构造：

1. 变量（Variable）：如 $x$、$y$、$z$
2. 抽象（Abstraction）：$\lambda x . M$，表示一个匿名函数，接受参数 $x$，返回表达式 $M$
3. 应用（Application）：$(M , N)$，表示将函数 $M$ 应用到参数 $N$ 上

一个λ表达式的完整语法可以定义为：

$$ E ::= x \mid \lambda x . E \mid (E_1 , E_2) $$

其中：

• $x$ 是变量
• $\lambda x . E$ 是函数抽象
• $(E_1 , E_2)$ 是函数应用

24.2.2 基本示例

恒等函数（Identity Function）：

$$ I = \lambda x . x $$

它将任何输入原样返回。例如：$(I , 5) = (\lambda x . x) , 5 = 5$。

常量函数（Constant Function）：

$$ K = \lambda x . \lambda y . x $$

它接受两个参数，总是返回第一个参数。例如：$((K , a) , b) = a$。

应用示例：

$$ (\lambda x . x + 1) , 5 = 5 + 1 = 6 $$

24.2.3 三种基本转换规则

α转换（Alpha Conversion）

α转换是指对绑定变量进行重命名，而不改变表达式的含义。

$$ \lambda x . M \equiv_\alpha \lambda y . M[x := y] $$

其中 $y$ 不在 $M$ 中自由出现。

例如：

$$ \lambda x . x + 1 \equiv_\alpha \lambda y . y + 1 $$

β归约（Beta Reduction）

β归约是λ演算中最核心的计算规则，表示函数应用：

$$ (\lambda x . M) , N \to_\beta M[x := N] $$

意思是：将函数体 $M$ 中所有自由出现的 $x$ 替换为参数 $N$。

例如：

$$ (\lambda x . x \times x) , 3 \to_\beta 3 \times 3 = 9 $$

另一个例子：

$$ (\lambda x . \lambda y . x + y) , 2 \to_\beta \lambda y . 2 + y $$

η转换（Eta Conversion）

η转换表示一个函数如果对所有输入都产生与另一个函数相同的结果，那么这两个函数相等：

$$ \lambda x . (f , x) =_\eta f \quad \text{（当 } x \text{ 不在 } f \text{ 中自由出现时）} $$

例如：

$$ \lambda x . (\sin , x) =_\eta \sin $$

24.3 λ演算与编程

24.3.1 图灵完备性

1936年，Alonzo Church 和 Alan Turing 分别独立证明了λ演算与图灵机在计算能力上是等价的。这意味着：

• 任何图灵机可以计算的函数，λ演算也可以计算
• 任何λ演算可以计算的函数，图灵机也可以计算
• 这一结论被称为 Church-Turing 论题

24.3.2 Church 编码

Church 编码是一种用λ演算表示数据的方法。在纯λ演算中没有数字、布尔值等原生类型，但可以用函数来编码它们。

Church 数（Church Numerals）

Church 数将自然数 $n$ 编码为将函数 $f$ 应用 $n$ 次的高阶函数：

$$ 0 = \lambda f . \lambda x . x $$

$$ 1 = \lambda f . \lambda x . f , x $$

$$ 2 = \lambda f . \lambda x . f , (f , x) $$

$$ 3 = \lambda f . \lambda x . f , (f , (f , x)) $$

一般形式：

$$ n = \lambda f . \lambda x . f^n , x $$

其中 $f^n$ 表示将 $f$ 应用 $n$ 次。

Successor 函数（后继函数）：

$$ \text{SUCC} = \lambda n . \lambda f . \lambda x . f , (n , f , x) $$

例如，计算 $\text{SUCC} , 1$：

$$ \begin{aligned} \text{SUCC} , 1 &= (\lambda n . \lambda f . \lambda x . f , (n , f , x)) , (\lambda f . \lambda x . f , x) \ &\to_\beta \lambda f . \lambda x . f , ((\lambda f . \lambda x . f , x) , f , x) \ &\to_\beta \lambda f . \lambda x . f , (f , x) \ &= 2 \end{aligned} $$

Church 布尔值（Church Booleans）

布尔值可以编码为在两个选项之间做选择的函数：

$$ \text{TRUE} = \lambda x . \lambda y . x $$

$$ \text{FALSE} = \lambda x . \lambda y . y $$

条件表达式：

$$ \text{IF} = \lambda b . \lambda x . \lambda y . b , x , y $$

验证：

$$ \text{IF} , \text{TRUE} , a , b = (\lambda b . \lambda x . \lambda y . b , x , y) , (\lambda x . \lambda y . x) , a , b \to_\beta a $$

$$ \text{IF} , \text{FALSE} , a , b = (\lambda b . \lambda x . \lambda y . b , x , y) , (\lambda x . \lambda y . y) , a , b \to_\beta b $$

逻辑运算：

$$ \text{AND} = \lambda p . \lambda q . p , q , p $$

$$ \text{OR} = \lambda p . \lambda q . p , p , q $$

$$ \text{NOT} = \lambda p . p , \text{FALSE} , \text{TRUE} $$

24.3.3 Y 组合子

在λ演算中，函数是匿名的，那么如何实现递归呢？Y 组合子（Y Combinator）解决了这个问题：

$$ Y = \lambda f . (\lambda x . f , (x , x)) , (\lambda x . f , (x , x)) $$

Y 组合子的关键性质是：

$$ Y , f = f , (Y , f) $$

这意味着 $Y , f$ 是 $f$ 的不动点，从而可以实现递归。

例如，定义阶乘函数的高阶版本：

$$ F = \lambda f . \lambda n . \text{IF} , (n = 0) , 1 , (n \times f , (n - 1)) $$

那么 $Y , F$ 就是真正的阶乘函数。

24.3.4 Rust 中的 λ 表达式（闭包）

Rust 通过闭包（Closure）支持λ表达式：

#![allow(unused)]
fn main() {
// 恒等函数
let identity = |x| x;

// 加一函数
let add_one = |x| x + 1;

// 应用函数：将函数 f 应用到参数 x
let apply = |f, x| f(x);

// 使用
let result = apply(add_one, 5); // result = 6
}

Rust 的闭包语法 |参数| 表达式 直接对应于λ演算的 $\lambda$ 抽象。

24.4 函数式编程范式

24.4.1 纯函数

纯函数（Pure Function）是指满足以下两个条件的函数：

1. 无副作用：函数的执行不会修改外部状态（不修改全局变量、不执行 I/O 操作等）
2. 引用透明：相同的输入总是产生相同的输出

数学上，纯函数就是一个从定义域到值域的映射：

$$ f: A \to B $$

Rust 示例：

#![allow(unused)]
fn main() {
// 纯函数
fn add(a: i32, b: i32) -> i32 {
    a + b
}

// 非纯函数（有副作用）
fn impure_add(a: i32, b: i32) -> i32 {
    println!("Adding..."); // 副作用：I/O 操作
    a + b
}

// 非纯函数（依赖外部状态）
static mut COUNTER: i32 = 0;

fn impure_increment(x: i32) -> i32 {
    unsafe {
        COUNTER += 1; // 副作用：修改全局状态
        x + COUNTER
    }
}
}

24.4.2 不可变性

函数式编程强调数据的不可变性（Immutability）。一旦数据被创建，就不能被修改。如果需要“修改“，则创建一个新的数据副本。

Rust 中默认变量绑定是不可变的：

#![allow(unused)]
fn main() {
let x = 5;
// x = 6; // 编译错误！

let mut y = 5;
y = 6; // 可以，因为 y 是可变的
}

函数式数据结构（如持久化数据结构）通过结构共享来高效地实现不可变性。

24.4.3 高阶函数

高阶函数（Higher-Order Function）是指接受函数作为参数或返回函数作为结果的函数。

数学表示：

$$ \text{map}: (A \to B) \to [A] \to [B] $$

$$ \text{filter}: (A \to \text{Bool}) \to [A] \to [A] $$

$$ \text{fold}: (B \to A \to B) \to B \to [A] \to B $$

Rust 示例：

#![allow(unused)]
fn main() {
fn apply_twice<F>(f: F, x: i32) -> i32
where
    F: Fn(i32) -> i32,
{
    f(f(x))
}

let result = apply_twice(|x| x + 1, 5); // result = 7
}

24.4.4 惰性求值与严格求值

严格求值（Strict Evaluation / Eager Evaluation）：表达式在绑定到变量时立即求值。Rust 默认使用严格求值。

惰性求值（Lazy Evaluation）：表达式只在需要时才求值。Haskell 使用惰性求值。

Rust 中可以通过迭代器和闭包模拟惰性求值：

#![allow(unused)]
fn main() {
// 惰性求值：在调用 collect() 之前，map 和 filter 不会执行
let result: Vec<i32> = (1..100)
    .map(|x| {
        println!("mapping {}", x); // 不会立即打印
        x * x
    })
    .filter(|x| {
        println!("filtering {}", x); // 不会立即打印
        *x > 10
    })
    .collect(); // 这里才会触发实际计算
}

24.4.5 函数式编程语言

24.5 Rust 中的闭包与迭代器

24.5.1 闭包的三种捕获方式

Rust 的闭包根据它们如何捕获环境中的变量，分为三种 trait：

#![allow(unused)]
fn main() {
let mut counter = 0;

// Fn：不可变借用
let fn_closure = |x: i32| x + counter;
println!("{}", fn_closure(5)); // 可以多次调用
println!("{}", fn_closure(5));

// FnMut：可变借用
let fn_mut_closure = |x: i32| {
    counter += x;
    counter
};
// fn_mut_closure(5); // 需要在可变上下文中调用

// FnOnce：移动所有权
let data = vec![1, 2, 3];
let fn_once_closure = || data; // data 被移动到闭包中
// let result = fn_once_closure(); // 只能调用一次
}

24.5.2 迭代器适配器

Rust 的迭代器是惰性的，只有在调用消耗型方法（如 collect、for_each、fold）时才会实际执行。

helpful-methods-for-closures-and-iterators

#![allow(unused)]
fn main() {
std::iter::DoubleEndedIterator

iter()
iter_mut()
into_iter()

next()
next_back()
nth()

flatten
filter() where P: FnMut(&Self::Item) -> bool  // 返回 true 时，元素将保留下来
filter_map() where P: FnMut(Self::Item) -> Option<B>
for_each()
zip()

ok()
ok_or()
ok_or_else()

any()
all()
find()
position()

rev()    // 翻转
cycle()

fold()   // "累加"操作
try_fold() // 累加，是短路的：一旦闭包返回 Try::Output 的失败变体，立即停止
take()
take_while()
skip()
skip_while()

chunks()
window()

matches_indices()

peekable()

# std::iter::Extend trait
extend()
}

24.5.3 常用迭代器模式

map / filter / reduce 模式：

#![allow(unused)]
fn main() {
let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// map + filter + fold（reduce）
let sum_of_squares_of_evens: i32 = numbers
    .iter()
    .filter(|&&x| x % 2 == 0)      // 筛选偶数
    .map(|&x| x * x)                // 平方
    .fold(0, |acc, x| acc + x);     // 求和

println!("{}", sum_of_squares_of_evens); // 220
}

函数组合：

#![allow(unused)]
fn main() {
fn compose<F, G, A, B, C>(f: F, g: G) -> impl Fn(A) -> C
where
    F: Fn(B) -> C,
    G: Fn(A) -> B,
{
    move |x| f(g(x))
}

let add_one = |x: i32| x + 1;
let double = |x: i32| x * 2;
let add_one_then_double = compose(double, add_one);

println!("{}", add_one_then_double(5)); // (5 + 1) * 2 = 12
}

惰性无限序列：

#![allow(unused)]
fn main() {
// 使用迭代器生成无限斐波那契数列
fn fibonacci() -> impl Iterator<Item = u64> {
    let mut a = 0;
    let mut b = 1;
    std::iter::from_fn(move || {
        let current = a;
        a = b;
        b = current + b;
        Some(current)
    })
}

let first_10: Vec<u64> = fibonacci().take(10).collect();
println!("{:?}", first_10);
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
}

24.6 从 λ 演算看 Stream/Iterator

24.6.1 Java Stream API

Java 从 8 开始引入 Stream API，受函数式编程启发，提供了一种声明式处理集合数据的方式。

创建 Stream 的四种方式：

1. 基于数组或 Collection：Arrays.stream(int[] array)、collection.stream()
2. Stream.of：由一系列值构造
3. Stream.generate(Supplier<T> s)：生成无限流
4. Stream.iterate(seed, f)：迭代生成

常用操作：

• 转换操作：map()、filter()、sorted()、distinct()
• 合并操作：concat()、flatMap()
• 并行处理：parallel()
• 聚合操作：reduce()、collect()、count()、max()、min()、sum()、average()
• 其他操作：allMatch()、anyMatch()、forEach()

Stream 转为其他类型：

• Collectors.toList()
• Collectors.toMap()
• stream().toArray(String[]::new)
• Collectors.groupingBy()

24.6.2 Rust Iterator trait

Rust 的 Iterator trait 是所有迭代器的核心：

#![allow(unused)]
fn main() {
pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // ... 大量默认方法
}
}

任何实现了 Iterator trait 的类型都可以使用所有迭代器适配器方法。

24.6.3 Java Stream vs Rust Iterator 对比

24.6.4 常见操作对比示例

map / filter / collect：

// Java
List<Integer> result = numbers.stream()
    .filter(n -> n % 2 == 0)
    .map(n -> n * n)
    .collect(Collectors.toList());

#![allow(unused)]
fn main() {
// Rust
let result: Vec<i32> = numbers
    .iter()
    .filter(|&&n| n % 2 == 0)
    .map(|&n| n * n)
    .collect();
}

reduce / fold：

// Java
int sum = numbers.stream()
    .reduce(0, (a, b) -> a + b);

#![allow(unused)]
fn main() {
// Rust
let sum: i32 = numbers
    .iter()
    .fold(0, |a, b| a + b);
}

flatMap / flatten：

// Java
List<Integer> flat = lists.stream()
    .flatMap(List::stream)
    .collect(Collectors.toList());

#![allow(unused)]
fn main() {
// Rust
let flat: Vec<i32> = lists
    .iter()
    .flatten()
    .copied()
    .collect();
}

24.7 实战：1BRC 挑战

24.7.1 问题描述

1BRC（The One Billion Row Challenge）是一个编程挑战：处理一个包含 10 亿行气象数据的文本文件，计算每个城市的最低温度、平均温度和最高温度。

每行数据的格式为：城市名;温度值，例如：

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8

24.7.2 Rust 实现

下面的实现展示了 Rust 中函数式编程思想的实际应用，包括迭代器链式调用、HashMap 的 entry API 等。

#![allow(unused)]
fn main() {
/// The One Billion Row Challenge(1BRC)
/// https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java

use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::io::prelude::*;
use std::io::BufReader;
use std::fs::File;
use std::path::Path;

fn one_billion_row_challenge() {
    // let records = String::from("");

    #[derive(Debug, Clone, Copy)]
    struct WeatherResult {
        min: f32,
        max: f32,
        sum: u64,
        count: u32,
    }

    let mut words: HashMap<String, WeatherResult> = HashMap::with_capacity(42000);
    // let mut words: HashMap<String, i32> = HashMap::with_capacity(300);
    match File::open("file/measurements.txt") {
        Ok(f) => {
            let reader = BufReader::new(f);
            let lines = reader.lines();
            for line in lines.map(|x| x.unwrap()) {
                // let pair: Vec<&str> = line.split(';').collect();
                // let pair = line.split_once(';').unwrap();
                let pair = line.rsplit_once(';').unwrap();

                let city_name = pair.0.to_string();
                let weather_temp = pair.1.to_string();

                match words.entry(city_name.clone()) {
                    Entry::Occupied(entry) => {
                        let mut value = entry.into_mut();
                        value.count += 1;

                        let temp: f32 = weather_temp.parse().unwrap();

                        let sum: u64 = (temp * 10000.0) as u64;
                        value.sum += sum;

                        if value.min > temp {
                            value.min = temp;
                        } else if value.max < temp {
                            value.max = temp;
                        }
                    }
                    Entry::Vacant(entry) => {
                        let temp: f32 = weather_temp.parse().unwrap();
                        let sum: u64 = (temp * 10000.0) as u64;

                        let wr = WeatherResult {
                            min: temp,
                            max: temp,
                            sum,
                            count: 1u32,
                        };

                        // println!("insert value {}", city_name.clone());
                        let _ = *entry.insert(wr);
                    }
                }
            }
        }
        Err(e) => println!("{}", e),
    }

    let mut rank: Vec<(String, WeatherResult)> = words.into_iter().collect();
    rank.sort_by_key(|pair| pair.0.clone());
    rank.iter().for_each(|(key, value)| {
        println!(
            "{} {}/{:.4}/{}",
            key,
            value.min,
            value.sum as f64 / (10000f64 * (value.count as f64)),
            value.max
        );
    });
}

let path = Path::new("src/file/measurements.txt");
println!("尝试读取文件: {:?}", path.canonicalize());

one_billion_row_challenge();
}

24.7.3 代码中的函数式编程思想

1. 迭代器链式调用：reader.lines() 返回一个迭代器，map(|x| x.unwrap()) 对每个元素进行转换
2. HashMap 的 entry API：words.entry(city_name.clone()) 提供了一种函数式的方式来处理“键存在“和“键不存在“两种情况，避免了重复的哈希查找
3. 不可变与可变的平衡：WeatherResult 结构体用 Copy trait 实现值语义，而 HashMap 用可变引用来更新状态
4. 消费迭代器：words.into_iter().collect() 消费 HashMap，将其转换为 Vec 进行排序
5. 声明式输出：rank.iter().for_each(...) 用声明式方式遍历并打印结果

24.8 总结

24.8.1 λ演算核心概念对比

24.8.2 函数式编程特性

24.8.3 Rust 闭包类型对比

24.9 练习题

练习 24.1

将以下数学函数写成λ表达式：

1. $f(x) = x^2$
2. $f(x, y) = x + y$
3. 一个函数，接受两个参数，返回较大的那个

练习 24.2

对以下λ表达式进行 β 归约，写出每一步：

1. $(\lambda x . x , x) , (\lambda y . y)$
2. $(\lambda x . \lambda y . x , y) , a , b$
3. $(\lambda f . \lambda x . f , (f , x)) , (\lambda y . y + 1) , 3$

练习 24.3

验证 Church 布尔值的 AND 运算：证明 $\text{AND} , \text{TRUE} , \text{FALSE} = \text{FALSE}$，其中 $\text{AND} = \lambda p . \lambda q . p , q , p$。

练习 24.4

用 Church 编码定义乘法运算 $\text{MULT} = \lambda m . \lambda n . \lambda f . m , (n , f)$，并验证 $\text{MULT} , 2 , 3 = 6$。

练习 24.5

编写一个 Rust 闭包，实现 Church 数的后继函数（Successor）的功能：接受一个 u32，返回其加一的结果。然后使用 fold 将该闭包应用 5 次到初始值 0 上。

练习 24.6

给定一个 Vec<String>，使用迭代器方法链完成以下操作（每个操作一行代码）：

1. 筛选出长度大于 3 的字符串
2. 将所有字符串转换为大写
3. 按字典序排序
4. 去重
5. 收集为 Vec<String>

练习 24.7

实现一个 Rust 函数 compose_three，它接受三个函数 f、g、h，返回它们的组合 $f \circ g \circ h$（即先应用 $h$，再应用 $g$，最后应用 $f$）。

#![allow(unused)]
fn main() {
fn compose_three<F, G, H, A, B, C, D>(f: F, g: G, h: H) -> impl Fn(A) -> D
where
    F: Fn(C) -> D,
    G: Fn(B) -> C,
    H: Fn(A) -> B,
{
    // 你的实现
}
}

练习 24.8

阅读 1BRC 代码，回答以下问题：

1. 为什么使用 rsplit_once(';') 而不是 split_once(';')？
2. 为什么温度值要乘以 10000.0 后转为 u64 存储？
3. 如果将代码中的 for line in lines.map(|x| x.unwrap()) 改为 lines.for_each(...)，需要做哪些修改？
4. （挑战）尝试使用 rayon crate 将 1BRC 代码并行化，使用 par_iter() 处理文件行。