我正在尝试对受歧视的联盟实施折叠。 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'
on 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 列表作为折叠值的原因是我想保留父/子关系的结构以供以后使用。在某种程度上,我认为这是一个非常特定于领域的折叠。