使用具有高阶函数的 GADT

Question

我正在尝试建模 "heterogeneous tree"，即。一棵树，其中的节点具有不同的 "kinds" 并且每个 "kind" 都被限制在 children 的 "kind" 中，它们可能包含：

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!")
  ])

通常这会为每个 "kind" 节点使用单独的变体来完成，但我试图将其定义为 GADT 以便能够使用 higher-order 函数操作树该模式在每种节点上都匹配：

function
  | Text ("text2", _) ->
    Some (Text ("text2", "Dreadful"))
  | _ ->
    None

我遇到的问题是定义接受上述 higher-order 函数并将其应用于每个节点的函数。到目前为止我有这个：

let rec replaceNode (type a) (f: a node -> a node option) (node: a node): a node =
  match f node with
  | Some otherNode -> otherNode
  | None ->
    match node with
    | Paragraph (id, children) -> 
      Paragraph (id, (List.map (replaceNode f) children))
    | Strong (id, children) ->
      Strong (id, (List.map (replaceNode f) children))
    | Text (_, _) -> node

但是编译器在突出显示的行上给我以下错误

This expression has type block node -> a node option but an expression was expected of type block node -> a node option This instance of block is ambiguous: it would escape the scope of its equation

或者，如果我将 f 的类型更改为 'a node -> 'a node option，则会出现此错误

This expression has type a node but an expression was expected of type a node The type constructor a would escape its scope

显然我不完全理解本地抽象类型（或 GADT，就此而言），但据我所知，这些错误似乎是因为类型，顾名思义，"local", 虽然在外面是多态的，但传递它会 "leak" 它，我猜？

所以我的问题是，首先也是最重要的：这甚至可以做到吗（"this"我想我的意思是模式匹配在 higher-order 函数 中的 GADT 上，但我什至不确定这是实际问题）？

Playground with all the code here

Answer 1

这里有两个根本问题（由于 GADT 的存在而有点混乱）。第一个问题是 replaceNode 是二阶多态函数。实际上，在第一个匹配中，f 应用于类型 a node 的节点，但在 Paragraph 分支内，它应用于类型 inline node 的节点。此处的类型检查器错误因 List.map 调用有点复杂，但将函数重写为

let rec replaceNode (type a) (f:a node -> a node option) 
(node:a node): a node =
  match f node with
  | Some otherNode -> otherNode
  | None ->
    match node with
    | Paragraph(id, []) -> Paragraph(id,[])
    | Paragraph (id, a :: children) -> 
      Paragraph (id, f a :: (List.map (replaceNode f) children))
    | Strong (id, children) ->
      Strong (id, (List.map (replaceNode f) children))
    | Text (_, _) -> node;;

产生更直接的错误：

Error: This expression has type inline node
but an expression was expected of type a node
Type inline is not compatible with type a

因此，问题是我们需要向类型检查器保证 f 适用于任何类型 a 而不仅仅是原始类型 a。换句话说，f 的类型应该是 'a. 'a node -> 'a node option（又名 forall 'a. 'a -> 'a node option）。不幸的是，显式多态注释只能出现在 OCaml 中的第一个位置 (prenex)，因此我们不能只更改 replaceNode 中 f 的类型。但是，可以通过使用多态记录字段或方法来解决此问题。

例如，使用记录路径，我们可以定义一个记录类型mapper:

type mapper = { f:'a. 'a node -> 'a node option } [@@unboxed]

其中字段 f 具有正确的显式多态表示法（也称为通用量化），然后在 replaceNode 中使用它：

let rec replaceNode (type a) {f} (node: a node): a node =
  match f node with
  | Some otherNode -> otherNode
  | None ->
    match node with
    | Paragraph (id, children) -> 
      Paragraph (id, (List.map (replaceNode {f}) children))
    | Strong (id, children) ->
      Strong (id, (List.map (replaceNode {f}) children))
    | Text (_, _) -> node

但是第二个问题出现了：这个 replaceNode 函数有 for type mapper -> inline node -> inline node。内联类型从何而来？这次的问题是多态递归。如果没有显式多态注释，replaceNode 的类型在其递归定义中被视为常量。换句话说，类型检查器认为 replaceNode 具有 mapper -> 'elt node -> 'elt node 的类型 given 'elt。而在 paragraph 和 strong 分支中， children 列表是 inline node 的列表。因此 List.map (replaceNode {f}) children 对类型检查器意味着 'elt=inline 因此 replaceNode 的类型变为 mapper -> inline node -> inline node.

要解决这个问题，我们需要添加另一个多态注释。好在这次，我们可以直接添加：

let rec replaceNode: type a. mapper -> a node -> a node =
  fun {f} node -> match f node with
  | Some otherNode -> otherNode
  | None ->
    match node with
    | Paragraph (id, children) -> 
      Paragraph (id, (List.map (replaceNode {f}) children))
    | Strong (id, children) ->
      Strong (id, (List.map (replaceNode {f}) children))
    | Text (_, _) -> node;;

最后，我们得到一个mapper -> 'a node -> 'a node类型的函数。请注意，let f: type a.… 是结合局部抽象类型和显式多态注释的快捷方式。

完成解释，这里需要局部抽象(type a)，因为在GADTs上进行模式匹配时只能细化抽象类型。换句话说，我们需要它来精确地表明 Paragraph、Strong 和 Text 中的类型 a 服从不同的等式： a = block 在段落分支中，a = inline 在 Strong 和 Text 分支中。

编辑：如何定义映射器？

这个局部抽象类型位实际上在定义映射器时很重要。例如，定义

let f = function
  | Text ("text2", _) -> Some (Text ("text2", "Dreadful"))
  | _ -> None

为 f 生成类型 inline node -> inline node option，因为匹配构造函数 Text 会生成等式 'type_of_scrutinee=inline.

要纠正这一点，需要添加一个本地抽象类型注释使类型检查器能够逐个分支地细化受审查者的类型：

 let f (type a) (node:a) : a node option= match node with
 | Text ("text2", _) -> Some (Text ("text2", "Dreadful"))
 | _ -> None

然后这个 f 有正确的类型并且可以被包装在映射器记录中：

let f = { f }

广告：从 4.06 版开始的 OCaml 手册中详细介绍了所有这些内容。

使用具有高阶函数的 GADT

Using GADTs with higher order functions

ocaml

types

higher-order-functions

gadt

locally-abstract-type