如何推翻受歧视的工会

Question

我正在尝试对受歧视的联合实施折叠。DU称为Expr，表示程序表达式，并且通常是递归的。我正在尝试编写一个折叠，以递归方式累积 Exprs 上的操作结果。下面是我尝试写的折叠。

let rec foldProceduralExpr (folder : 's -> Expr list -> 's) (state : 's) (expr : Expr) : 's =
    let children =
        match expr with
        | Series s -> s.SerExprs
        | Lambda l -> [l.LamBody; l.LamPre; l.LamPost]
        | Attempt a -> a.AttemptBody :: List.map (fun ab -> ab.ABBody) a.AttemptBranches
        | Let l -> l.LetBody :: List.concat (List.map (fun lb -> match lb with LetVariable (_, expr) -> [expr] | LetFunction (_, _, body, _, pre, post, _) -> [body; pre; post]) l.LetBindings)
        | Case c -> c.CaseTarget :: List.concat (List.map (fun branch -> [branch.TBBody; branch.TBTest]) c.CaseBranches)
        | Condition c -> List.concat (List.map (fun branch -> [branch.TBBody; branch.TBTest]) c.CondBranches)
        | List l -> l.ListElements
        | Array a -> Array.toList a.ArrElements
        | Composite c -> LunTrie.toValueList (LunTrie.map (fun _ mem -> mem.MemExpr) c.CompMembers)
        | _ -> []
    let listFolder = fun state expr -> foldProceduralExpr folder state expr
    let listFolded = List.fold listFolder state children
    folder state (expr :: listFolded)

问题是代码不起作用，这是已知的，因为我在最后一行the construct causes code to be less generic than indicated by the type annotations. The type variable 's has been constrained to be type 'Expr list'收到错误。listFolded这是因为 的定义foldProceduralExpr几乎肯定是错误的。

现在，我很想修复代码并因此修复类型错误，但我根本不知道如何修复。我想我缺乏的是对非列表或递归数据结构的折叠如何工作的理解。我最近将 trie 的折叠从 OCaml 翻译为 F#，并且在理解该折叠如何工作方面遇到了很多困难。

问题 1：这段代码是否有一个我可以理解的可见修复？

问题 2：是否有资源可以获取了解如何编写这些类型的折叠所需的背景知识？

如果您需要更多信息，请告诉我。我没有将 DU 包括在内，因为它太大、太复杂，无法使问题清晰。希望足以说明，这是典型的 Lisp 风格 AST 数据结构。

后续问题：一旦它起作用，我还想用该折叠写一张地图。这看起来像一张典型的地图吗？还是需要额外的脑力才能弄清楚？

编辑：关于托马斯的帮助，我已将最后三行变成 -

let exprs = expr :: children
let listFolder = fun state expr -> foldProceduralExpr folder state expr
let listFolded = List.fold listFolder state exprs
folder listFolded exprs

我希望这仍然有意义。

编辑：这是我的最终解决方案。这是普遍的关于生孩子的事情 -

let rec foldRdu (getChildren : 't -> 't list) (folder : 's -> 't -> 't list -> 's) (state : 's) (parent : 't) : 's =
    let children = getChildren parent
    let listFolder = fun state child -> foldRdu getChildren folder state child
    let listFolded = List.fold listFolder state children
    folder listFolded parent children

我将 Expr 和 Expr 列表作为折叠值的原因是我想保留父/子关系的结构以供以后使用。在某种程度上，我认为这是一个非常特定于领域的折叠。

Answer 1

第一个问题是，你想要实现什么样的折叠？树状结构有多种选择。假设您有一个n 叉树（即任意数量的子树），您可以：

1. Expr仅对叶子中的节点应用折叠功能
2. 在叶子上应用折叠函数，然后将其应用于所有内部节点（递归调用后）
3. 在处理树时对内部节点应用折叠函数，然后对叶子应用折叠函数

在你的例子中，你的文件夹函数让Expr list我有点困惑 - 我认为你可以只给它当前的Expr而不是子列表，但是在子列表上调用它也是一个选项。

您首先进行递归调用，然后在当前表达式上调用文件夹，所以我想您想实现选项 2。我可以理解折叠的前两行：

// This defines a function that recursively folds the a given 
// expression and produces a new state of type 's
let listFolder = fun state expr -> foldProceduralExpr folder state expr 
// Here, you fold all children recursively starting with 'state' and 
// obtaining a result 'listFolded' of type 's
let listFolded = List.fold listFolder state children 

然而，最后一行可能是错误的：

// From the previous line, 'listFolded' is of type 's, but 
// here you use it as if it was a list:
folder state (expr :: listFolded) 

我假设您可能想使用listFolded作为传递给folder. 该文件夹采用表达式列表，因此您可以将其children作为第二个参数（或者您可以更改folder为仅采用单个表达式Expr，然后仅给出expr，恕我直言，这更有意义）。不管怎样，这应该让它工作，这样你就可以运行它并看看发生了什么：

folder listFolded children