需求：实现将Tree转换为按序ConsList的F#函数

我定义了如下类型：

ConsList 类型 #

type ConsList<'value> =
    | Cons of head: 'value * tail: ConsList<'value>
    | Empty

Tree 类型 #

type Tree<'value> =
    | Node of value: 'value * children: ConsList<Tree<'value>>
    | Leaf of value: 'value

需要实现一个函数，按根节点优先、从左到右的顺序收集 Tree 中所有节点和叶子的值，转换为 ConsList。

示例：输入 Node(1, Cons(Leaf 2, Cons(Leaf 3, Empty)))，期望输出 Cons(1, Cons(2, Cons(3, Empty)))

已有如下 fold 函数可作为参考：

// ConsList 的 fold 函数
let rec fold folder acc lst =
    let f = fold folder
    match lst with
    | Empty -> acc
    | Cons (hd, tl) -> f (folder acc hd) tl

// Tree 的 fold 函数
let rec fold folder acc tree =
    let f = fold folder
    match tree with
    | Leaf value -> folder acc value
    | Node(value, children) -> ConsList.fold f (folder acc value) children

可以利用已有的 Tree fold 函数实现目标功能。由于直接用 fold 构建的 ConsList 是反向的（每次将新元素添加到头部），需要先实现一个反转 ConsList 的辅助函数，再完成最终转换：

1. 实现 ConsList 反转函数 #

let rec reverse lst =
    let rec revHelper acc = function
        | Empty -> acc
        | Cons(hd, tl) -> revHelper (Cons(hd, acc)) tl
    revHelper Empty lst

2. 实现前序遍历转 ConsList 的函数 #

let toConsList tree =
    // 将当前值添加到 ConsList 头部
    let folder acc value = Cons(value, acc)
    // 先用 fold 收集反向列表，再反转得到正确顺序
    tree |> fold folder Empty |> reverse

测试示例 #

// 构造测试输入
let testTree = Node(1, Cons(Leaf 2, Cons(Leaf 3, Empty)))
// 调用函数
let result = toConsList testTree
// result 的值为 Cons(1, Cons(2, Cons(3, Empty)))，符合预期

原理说明 #

• Tree 的 fold 函数是前序遍历逻辑：先处理当前节点/叶子的值，再递归处理所有子节点（从左到右）。
• folder 函数将每个值添加到 ConsList 头部，fold 结束后得到前序遍历的反向列表。
• 通过 reverse 函数反转列表，得到正确的前序顺序 ConsList。

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