我正在尝试建模“异构树”,即。一棵树,其中节点具有不同的“种类”,并且每个“种类”都被限制在它们可能包含的子“种类”中:
type id = string
type block
type inline
type _ node =
| Paragraph : id * inline node list -> block node
| Strong : id * inline node list -> inline node
| Text : id * string -> inline node
然后可以像这样定义树:
let document =
Paragraph ("p1", [
Text ("text1", "Hello ");
Strong ("strong1", [
Text ("text2", "Glorious")
]);
Text ("text3", " World!")
])
通常这将使用每种“类型”节点的单独变体来完成,但我试图将其定义为 GADT,以便能够使用模式匹配每种节点的高阶函数来操作树:
function
| Text ("text2", _) ->
Some (Text ("text2", "Dreadful"))
| _ ->
None
我遇到的问题是定义接受上述高阶函数并将其应用于每个节点的函数。到目前为止,我有这个:
let rec replaceNode (type a) (f: a node -> a node option) (node: a node): a node = 匹配 f 节点 | 一些其他节点 -> 其他节点 | 无 -> 匹配节点 | 段落(id,children)-> 段落 (id, (List.map (replaceNode f) children)) | 强(id,儿童)-> 强 (id, (List.map (replaceNode f) children)) | 文本 (_, _) -> 节点
但是编译器在突出显示的行上给了我以下错误
这个表达式的类型是块节点 -> 一个节点选项,但是一个表达式应该是类型块节点 -> 一个节点选项这个块的实例是模棱两可的:它会逃脱其方程的范围
或者,如果我将类型更改为,则会f
收到'a node -> 'a node option
此错误
此表达式具有节点类型,但表达式应为节点类型 类型构造函数 a 将逃脱其范围
显然,我并不完全理解本地抽象类型(或真正的 GADT,就此而言),但据我所知,这些错误似乎出现了,因为该类型,顾名思义,是“本地的”,而在在外面,传递它会“泄漏”它,我猜?
所以我的问题是,首先是:这甚至可能做到吗(并且“这个”我认为我的意思是在高阶函数中对 GADT 进行模式匹配,但我什至不确定这是实际问题) ?