使用C++ constexpr模拟函数式编程的cons-cell链表结构

我来帮你把这段代码补全并详细解释如何用C++ constexpr来模拟函数式语言里的cons-cell链表结构，这其实是个挺有意思的编译期编程实践～

首先，先把你定义的pair结构体补全并优化，它就是cons-cell的核心载体：

template <typename E1, typename E2>
struct pair {
    // 默认构造函数，值初始化两个成员
    constexpr pair() : _car{E1{}}, _cdr{E2{}} {}
    // 带参数的构造函数，初始化car（当前节点值）和cdr（链表剩余部分）
    constexpr pair(const E1 &car, const E2 &cdr) : _car{car}, _cdr{cdr} {}
    
    // 获取当前节点值的constexpr方法
    constexpr auto car() const { return _car; }
    // 获取链表剩余部分的constexpr方法
    constexpr auto cdr() const { return _cdr; }

private:
    E1 _car;
    E2 _cdr;
};

核心思路解释 #

这个pair结构体完全对应函数式语言里的cons-cell：

• car存储当前节点的元素值
• cdr存储链表的剩余部分（可以是另一个pair，或者标记链表结束的空类型）
• 模板特性让它支持任意类型的嵌套，完美适配链表的递归结构，而且所有操作都是constexpr，意味着可以在编译期完成所有链表的构建和计算。

简化链表创建的辅助函数 #

为了更贴近函数式语言的写法，我们可以加一个cons辅助函数，避免每次手动写模板参数：

template <typename E1, typename E2>
constexpr auto cons(const E1 &car, const E2 &cdr) {
    return pair<E1, E2>{car, cdr};
}

完整的链表示例 #

我们需要一个空类型来标记链表的结束，比如nil：

// 空节点类型，用于标记链表的末尾
struct nil {};

// 编译期构建链表：1 -> 2 -> 3 -> nil
constexpr auto my_list = cons(1, cons(2, cons(3, nil{})));

编译期链表操作示例 #

既然是constexpr，我们可以在编译期完成链表的计算，比如递归计算链表长度：

// 递归计算链表长度的constexpr函数（空节点长度为0）
constexpr auto list_length(const nil&) {
    return 0;
}

// 递归处理非空链表：当前节点长度1 + 剩余链表长度
template <typename E1, typename E2>
constexpr auto list_length(const pair<E1, E2>& lst) {
    return 1 + list_length(lst.cdr());
}

// 编译期获取链表长度，len的值会在编译时确定为3
constexpr int len = list_length(my_list);

甚至可以支持异构链表（不同类型的元素共存）：

// 编译期构建混合类型链表：42 -> "hello" -> nil
constexpr auto mixed_list = cons(42, cons("hello", nil{}));

内容的提问来源于stack exchange，提问作者meguli