函数式编程：在 AST 中嵌入函数？

Question

我目前正在尝试使用 F# 将 linking 函数建模为 AST 的一部分（尽管目前它更像是一个链）。每个 link 都是一个函数，它也可能有一个链附加到它上面。但是，要指定附加到 link 的链的类型签名，您还必须添加更多类型参数。但是你这样做了，然后又添加了一个参数，如此循环往复。下面是一个例子。

type Chain<'a, 'b, 'c> =
| Link of ('a -> 'b) * Chain<'c>  // This doesn't work - you need more type params supplied
| End  of 'a

我希望能够将链表示为 Link ((fun x -> x + 5), Link... 之类的东西，直到它到达终点，但我无法在不遇到类型爆炸问题的情况下找到这样做的方法。

如果有人能给我指明方向，帮助创建任意长度的任意函数链，我将不胜感激。

Answer 1

虽然问题有点不清楚，但我认为你问的更像是（假设语法）：

type Chain<'a> =
| Link of ('b -> 'a) * Chain<'b>
| End of 'a

我们在 Link 的案例中引入了一个新的类型参数 'b - 它可以是任何类型，只要函数匹配嵌套 Chain<_> 的类型参数。这与 "existential type" 的想法有关（基本上是泛型通用类型量化的双重概念）。

坏消息：在 F# 中没有简单的语法来实现这一点。好（？）消息：如果你真的想要的话，有一种非常丑陋的编码方式。

结果是，如果你想表达你的link类型的想法，你可以通过机械的方式引入一些辅助类型来实现（∃'t.F<'t>类型可以编码为∀'x.(∀'t.F<'t> -> 'x) -> 'x，可以用F#类型系统表示）。

这是您的示例在此编码下的样子：

type 'a Chain = | End of 'a | Link of SomeLink<'a> and SomeLink<'a> = abstract Apply : LinkUser<'a,'x> -> 'x and LinkUser<'a,'x> = abstract Apply : ('b -> 'a) * Chain<'b> -> 'x let mkLink (f, c) = Link { new SomeLink<_> with member __.Apply(w) = w.Apply(f, c) } let chain = mkLink (sprintf "%i", End 1) let rec applyChain<'a> : 'a Chain -> 'a = function | End a -> a | Link l -> l.Apply { new LinkUser<_,_> with member __.Apply(f, c) = f (applyChain c) } applyChain chain // "1"

函数式编程：在 AST 中嵌入函数？

Functional Programming: Embedding functions in AST?

f#

functional-programming

function

abstract-syntax-tree