概念理解

在函数式编程中，从已有的类型构造一个新类型有两种主要的操作：和与乘积，通过这两种操作产生的新类型称为代数数据类型（Algebraic Data Type）。

• 和类型，类型A和类型B的和是一个包含A实例或B实例新类型。C++中enum、union、std::variant、std::optional、std::any类型。
• 积类型，类型A和类型B的积是一个包含A实例和B实例新类型，即类型A集合和类型B集合中所有值的笛卡尔积。C++中使用std::pair和std::tuple产生积类型。

随着C++中tuple和variant等工具对代数数据类型的更好支持，与它们交互的机制的重要性也有所增加。虽然已经添加了apply和visit等机制，但它们的使用非常复杂，即使在简单的情况下也是有限的。模式匹配（Pattern Matching）是许多编程语言广泛采用的与代数数据类型交互的机制，可以极大地简化C++。

C++模式匹配提案：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1371r2.pdf

函数式编程范式：

函数式编程风格建立在简单的、日常的数学直觉之上：若一个过程或方法没有副作用， 那么在忽略效率的前提下，我们需要理解的一切便只剩下如何将输入映射到输出了 —— 也就是说，我们只需将它视作一种计算数学函数的具体方法即可。这也是 “函数式编程”中“函数式”一词的含义之一。程序与简单数学对象之间这种直接的联系， 同时支撑了对程序行为进行形式化证明的正确性以及非形式化论证的可靠性。函数式编程中“函数式”一词的另一个含义是它强调把函数作为'一等'的值 —— 即，这类值可以作为参数传递给其它函数，可以作为结果返回， 也可以包含在数据结构中等等。这种将函数当做数据的方式， 产生了大量强大而有用的编程习语（Idiom）。其它常见的函数式语言特性包括'代数数据类型（Algebraic Data Type）'， 能让构造和处理丰富数据结构更加简单的'模式匹配（Pattern Matching）'， 以及用来支持抽象和代码复用的'多态类型系统（Polymorphic Type System）'。

现有实现方式示例

#include <string>
#include <iostream>
#include <variant>
#include <memory>

// 创建可重载的表达式集合
template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;

template<typename T>
using Ptr = std::shared_ptr<T>;
// 代数数据结构
struct Nil {};
template<typename T>
struct Cons {
    T h;
    Ptr<std::variant<Nil, Cons<T>>> ts;
    Cons(T a, Ptr<std::variant<Nil, Cons<T>>> b): h(a) { ts = b; };
};
template<typename T>
using list = std::variant<Nil, Cons<T>>;
template<typename T>
Ptr<list<T>> nil() {
    return std::make_shared<list<T>>(Nil());
}
template<typename T>
Ptr<list<T>> cons(T a, Ptr<list<T>> b) {
    return std::make_shared<list<T>>(Cons(a,b));
}
// 模式匹配
template<typename T, typename Func, typename Func2>
auto match(Ptr<list<T>> l, Func f, Func2 g) {
    return std::visit(overloaded {
            [&](Nil n) {return f(n); },
            [&](Cons<T> c) { return g(c.h, c.ts); }
            }, *l);
}
// 递归打印
template<typename T>
void print(Ptr<list<T>> l) {
    match(l,
        [](Nil n) { (void)n;std::cout << "null" << std::endl; },
        [](T t, Ptr<list<T>> tail){ 
            std::cout << t << " "; 
            print(tail); 
        });
}

int main() {
    auto l = cons(3, cons(4,  cons(5, nil<int>())));
    print(l);
    return 0;
}

https://wandbox.org/nojs/gcc-head
https://wandbox.org/nojs/clang-head