函数式编程 —— 函数式编程术语

Posted on Edited on In Views: Word count in article: 2.2k Reading time ≈ 8 mins.
介绍函数式编程中的一些术语（基于 C++）

函数式编程有许多优势，由此越来越受欢迎。然而每个编程范式 (paradigm) 都有自己唯一的术语，函数式编程也不例外。我们提供一张术语表，希望使你学习函数式编程变得容易些。

本文档基于 functional-programing-jargon 进行改编，将原有的 JavaScript 示例替换为 C++ 实现，旨在帮助 C++ 开发者理解函数式编程概念。

示例均为 C++。

尚在 WIP 阶段，欢迎交流。

如果适用，本篇文档使用定义在 Fantasy Land spec 中的术语。

Arity

函数参数的个数。来自于单词 unary (一元)、binary (二元)、ternary (三元) 等等。这个单词是由 -ary 与 -ity 两个后缀拼接而成。例如，加法函数有两个参数，因此它被定义为二元函数 (binary function)，或者说它的 arity 是 2。同样地，带有可变数量的参数的函数被称为 variadic。

1
2
auto sum = [](int a, int b) { return a + b; };
// sum 的 arity 是 2

高阶函数 (Higher-Order Function / HOF)

以函数为参数或/和返回值的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <algorithm>
#include <print>

template <typename Predicate, typename T>
auto filter(Predicate predicate, const std::vector<T>& xs) {
    std::vector<T> result;
    std::copy_if(xs.begin(), xs.end(), std::back_inserter(result), predicate);
    return result;
}

auto is_number = [](const auto& x) { return true; }; // 简化示例

int main() {
    std::vector<int> nums = {0, 1, 2, 3};
    auto filtered = filter([](int n) { return n % 2 == 0; }, nums);
    // filtered: [0, 2]
}

闭包 (Closure)

闭包是访问在其作用域外的变量的一种方式。在 C++ 中，Lambda 表达式通过捕获列表实现闭包。

1
2
3
4
5
6
7
8
#include <print>

auto addTo = [](int x) {
    return [x](int y) { return x + y; };
};

auto addToFive = addTo(5);
std::println("{}", addToFive(3)); // 输出 8

在上面的例子中，x 被捕获到内部 Lambda 中，即使 addTo 执行完毕，内部 Lambda 依然可以访问 x。

偏函数应用 (Partial Application)

「部分地」应用一个函数，即预设原始函数的部分参数来创建一个新的函数。在 C++ 中可以使用 std::bind 或者 Lambda 表达式。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <functional>
#include <print>

auto add3 = [](int a, int b, int c) { return a + b + c; };

// 使用 Lambda 实现偏函数应用
auto fivePlus = [add3](int c) { return add3(2, 3, c); };

// 或者使用 std::bind
using namespace std::placeholders;
auto fivePlusBind = std::bind(add3, 2, 3, _1);

std::println("{}", fivePlus(4)); // 9

柯里化 (Currying)

将一个多元函数转变为一元函数的过程。 每当函数被调用时，它仅仅接收一个参数并且返回带有一个参数的函数，直到传递完所有的参数。

1
2
3
4
5
6
7
8
9
10
11
12
#include <print>

auto sum = [](int a) {
    return [a](int b) {
        return a + b;
    };
};

std::println("{}", sum(3)(4)); // 7

auto add2 = sum(2);
std::println("{}", add2(10)); // 12

自动柯里化 (Auto Currying)

将一个包含多个参数的函数转换成另一个函数，这个函数如果被给到的参数少于正确的数量，就会返回一个接受剩余参数的函数。

C++ 标准库没有内置自动柯里化，但可以通过复杂的模板元编程实现。

函数组合 (Function Composition)

把两个函数放在一起形成第三个函数的行为，一个函数的输入为另一个函数的输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <string>
#include <print>

template <typename F, typename G>
auto compose(F f, G g) {
    return [f, g](auto x) {
        return f(g(x));
    };
}

auto floor_func = [](double x) { return static_cast<int>(x); };
auto to_string_func = [](int x) { return std::to_string(x); };

auto floorAndToString = compose(to_string_func, floor_func);
std::println("{}", floorAndToString(12.12)); // "12"

Continuation (后续)

在一个程序执行的任意时刻，尚未执行的代码称为 Continuation。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <functional>
#include <print>
#include <string>

auto printAsString = [](int num) {
    std::println("Given {}", num);
};

auto addOneAndContinue = [](int num, std::function<void(int)> cc) {
    int result = num + 1;
    cc(result);
};

addOneAndContinue(2, printAsString); // "Given 3"

纯函数 (Purity)

输出仅由输入决定，且不产生副作用。

1
2
3
4
5
#include <string>

auto greet = [](const std::string& name) {
    return "hello, " + name;
};

副作用 (Side effects)

如果一个函数或者表达式除了返回一个值之外，还与外部可变状态进行了交互（读取或写入），则它是有副作用的。

1
2
3
4
int x = 0;
auto sideEffect = [&x]() {
    x++; // 修改了外部状态
};

幂等 (Idempotent)

如果一个函数执行多次皆返回相同的结果，则它是幂等的。

1
2
3
4
#include <cmath>

// f(f(x)) == f(x)
std::abs(std::abs(-10)); // 10

Point-Free 风格 (Point-Free Style)

定义函数时，不显地指出函数所带参数。这种风格通常需要柯里化或者高阶函数。

1
2
// C++ 中较难完全实现 Point-Free，但可以利用组合
auto incrementAll = map(add(1)); // 假设 map 和 add 已经柯里化

断定 (Predicate)

根据输入返回 true 或 false。

1
auto isGreaterTwo = [](int a) { return a > 2; };

契约 (Contracts)

契约规定了函数或表达式在运行时的行为的职责和保障。C++ 中可以使用 assert 或 C++ 20 的契约（虽然 C++ 20 契约被推迟，但概念一致）。

1
2
3
4
5
6
#include <cassert>

auto addOne = [](int num) {
    assert(num > 0); // 契约：输入必须大于 0
    return num + 1;
};

范畴 (Category)

在范畴论中，范畴是指对象集合及它们之间的态射 (morphism)。在编程中，数据类型作为对象，函数作为态射。

遵从三个原则：

  1. 同一态射 (Identity)
  2. 可组合性 (Composition)
  3. 结合律 (Associativity)

值 (Value)

任何可以赋给变量的东西叫做值。

1
2
3
4
5
#include <string>

5
std::string("hello")
[](int a){ return a; }

常量 (Constant)

一旦被定义之后就不可以被重新赋值。

1
2
const int five = 5;
constexpr double pi = 3.14159;

函子 (Functor)

函子是一个实现了 map 的对象。在 C++ 中，std::optional 或 std::vector（配合变换）可以看作函子。

1
2
3
4
5
6
7
8
9
#include <optional>

template <typename T, typename F>
auto map(const std::optional<T>& opt, F f) {
    if (opt) return std::optional(f(*opt));
    return std::optional<decltype(f(*opt))>{std::nullopt};
}

auto result = map(std::optional(2), [](int x) { return x + 1; }); // Some(3)

抬升 (Lift)

抬升是指将一个值放进一个对象（如函子）中。

1
2
3
4
5
6
#include <optional>

template <typename T>
std::optional<T> lift(T val) {
    return std::optional(val);
}

引用透明性 (Referential Transparency)

如果一个表达式能够被它的值替代而不改变程序的行为，则它是引用透明的。

等式推理 (Equational Reasoning)

当一个应用程序由表达式组成并且没有副作用时，我们可以从这些组成部分中得知系统的真相。

Lambda

一种可以被视作一个值的匿名函数。

1
auto add1 = [](int a) { return a + 1; };

惰性求值 (Lazy evaluation)

惰性求值是将表达式的求值延迟到需要它的值为止。C++ 20 的 std::ranges::views 提供了这种能力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <ranges>
#include <print>
#include <vector>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    auto results = nums | std::views::transform([](int n) {
        std::println("Evaluating {}", n);
        return n * 2;
    });
    // 此时并没有求值
    for (int n : results | std::views::take(2)) {
        // 只会评估前两个元素
    }
}

幺半群 (Monoid)

一个对象，它拥有一个结合性的二元操作和单位元 (identity)。

1
2
3
4
5
// 加法幺半群
// 操作：+
// 单位元：0
1 + 0 == 1;
(1 + 2) + 3 == 1 + (2 + 3);

单子 (Monad)

拥有 unit (或 of) 和 bind (或 chain) 的对象。C++ 23 为 std::optional 引入了 and_then。

1
2
3
4
5
6
7
8
#include <optional>
#include <string>

std::optional<int> get_id(std::string name) { /* ... */ }
std::optional<std::string> get_name(int id) { /* ... */ }

// and_then 类似于单子的 bind
auto result = get_id("Alice").and_then(get_name);

应用函子 (Applicative Functor)

一个拥有 ap 函数的对象。ap 将对象中的函数应用于另一个同样类型的对象中的值。

态射 (Morphism)

一个变形函数。

  • Endomorphism (自同态): 输入输出类型相同。
  • Isomorphism (同构): 保持结构的双向变换。

Setoid

拥有 equals (在 C++ 中通常是 operator==) 的对象。

1
2
3
4
5
6
7
8
#include <string>

struct Person {
    std::string name;
    bool operator==(const Person& other) const {
        return name == other.name;
    }
};

半群 (Semigroup)

一个拥有结合性二元操作 (concat) 的对象。

1
2
3
4
5
#include <string>

std::string a = "hello";
std::string b = " world";
auto c = a + b; // string 的拼接满足结合律

可折叠性 (Foldable)

一个拥有 reduce (C++ 中为 std::accumulate 或 std::ranges::fold_left) 函数的对象。

1
2
3
4
5
#include <numeric>
#include <vector>

std::vector<int> nums = {1, 2, 3};
int sum = std::accumulate(nums.begin(), nums.end(), 0); // 6

类型签名 (Type Signatures)

在 C++ 中通常通过函数原型或 std::function 表示。

1
2
3
4
#include <functional>

// add :: int -> int -> int
std::function<int(int, int)> add = [](int x, int y) { return x + y; };

代数数据类型 (Algebraic data type)

  • 和类型 (Sum type): std::variant
  • 积类型 (Product type): std::tuple, struct
1
2
3
4
5
6
7
8
9
10
#include <variant>
#include <string>

// Sum type
using Status = std::variant<int, std::string>;

// Product type
struct Point {
    double x, y;
};

可选类型 (Option)

在 C++ 中即 std::optional。

1
2
3
4
5
6
#include <optional>

std::optional<int> safe_div(int a, int b) {
    if (b == 0) return std::nullopt;
    return a / b;
}

偏函数 (Partial function)

偏函数是没有为全部参数定义的函数（例如除法在除数为 0 时未定义）。

处理偏函数的方法：

  1. 返回 std::optional
  2. 抛出异常
  3. 使用默认值
1
2
3
4
5
6
7
#include <vector>
#include <numeric>

// 使用默认值处理
int sum(const std::vector<int>& arr) {
    return std::accumulate(arr.begin(), arr.end(), 0);
}

在 C++ 中的函数式编程库

参考资料