2

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

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 数据结构。

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

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

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 列表作为折叠值的原因是我想保留父/子关系的结构以供以后使用。这是一个非常特定于领域的折叠，在某种程度上我想。

4

2 回答 2

4

第一个问题是，你想实现什么样的折叠？树状结构有多种选择。假设您有一个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
于 2012-09-05T19:27:23.417 回答
2

我曾经写过一篇关于维护涉及大型可区分联合及其转换的代码的实用方法的文章：

http://t0yv0.blogspot.com/2011/09/transforming-large-unions-in-f.html

在实践中，我发现折叠假设太多，经常有无法用折叠表示的转换。您还希望控制转换的方式——自下而上或自上而下，以及哪些节点被跳过或特殊处理。transform本文通过一个简单的函数展示了如何做到这一点。我还从transform.

它没有直接回答如何解决您的问题，但它可能会为构建此类代码的另一种方式提供一些启示。

于 2012-09-09T12:22:24.040 回答