使用具有高阶函数的GADT

这里有两个根本问题（由于存在GADT而有些混乱）。第一个问题是replaceNode第二级多态函数。确实，在第一个匹配中，f将应用于type的节点a node，但是在Paragraph分支内部，将其应用于type的节点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;;

产生一个更直接的错误：

错误：此表达式具有类型内联节点，
但是期望一个类型为节点的表达式
类型内联与类型a不兼容

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

例如，使用记录路径，我们可以定义一个记录类型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函数具有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;;

最后，我们获得type的函数mapper -> 'a node -> 'a node。请注意，这let f: type a.…是组合本地抽象类型和显式多态注释的快捷方式。

完成说明后，(type a)此处需要局部抽象，因为在GADT上进行模式匹配时，只能对抽象类型进行优化。换句话说，我们就需要精确的类型a中Paragraph，Strong并Text服从不同的等式：a=block段落分支，a=inline在Strong和Text分公司。

编辑：如何定义一个映射器？

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

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

产生了一个类型inline node -> inline node option为f，由于在构造匹配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 }

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