是否可以让异构列表的元素取决于前面元素的类型？

Question

上下文

我想对 Web 应用程序的路由进行建模，使其满足以下要求：

可以执行完整的定义
可以创建不完整的定义
可以检查不完整的定义是否“匹配”（即包含在）完整的定义中。

作为工作示例：

type root =
  | Fruit of fruit
  | Veggie of veggie
  
and fruit =
  | Apple of apple
  | Banana of banana
  
and veggie =
  | Carrot of carrot
  
and apple = { diameter: int; cultivar: string; }
and banana = { length: int }
and carrot = { length: int; color: [`Orange | `Purple] }

有了这个，我们可以轻松地创建和执行完整的定义：

let complete = Fruit (Apple { diameter = 8; cultivar = "Golden Delicious" })

但不能创建不完整的定义

let incomplete = Fruit Apple

                       ^^^^^
Error: The constructor Apple expects 1 argument(s),
       but is applied here to 0 argument(s)

因此也无法匹配不完整和完整的定义，但我们至少可以详细地实现一个忽略参数的部分相等函数：

let equal a b = match a, b with
  | Fruit (Apple _), Fruit (Apple _ ) -> true
  | Fruit (Apple _), _ -> false
  | Fruit (Banana _), Fruit (Banana _ ) -> true
  | Fruit (Banana _), _ -> false
  | Veggie (Carrot _) , Veggie (Carrot _) -> true
  | Veggie (Carrot _) , _ -> false

对可能解决方案的模糊想法

所以我有了使用 GADT 树和异构列表的想法，通过将路由定义为列表来使定义更加灵活，例如：

let route = [Fruit; Apple; { diameter = 6; cultivar = "Granny Smith" }]

然后它们可以与模式匹配和递归一起使用，以更容易地解构和比较它们。

不幸的是，实现这个并不是那么容易。这是我目前所拥有的：

type _ root =
  | Fruit : _ fruit root
  | Veggie : _ veggie root

and _ fruit =
  | Apple : apple fruit
  | Banana : banana fruit

and _ veggie =
  | Carrot : carrot veggie

and apple = { diameter: int; cultivar: string; }
and banana = { length: int }
and carrot = { length: int; color: [`Orange | `Purple] }

type 'a t =
  | [] : _ root t
  | ( :: ) : 'b * 'a t -> 'b t

我在这里看到的两个问题：

'b 不受 'a 的限制，所以任何东西都可以放入列表中，只要它以 root t 开头，并且可能没有恢复元素类型的方法。我认为这需要更高级的类型，但也许有办法解决这个问题？
即使我能够解决这个问题，我也不确定我将如何终止它。也许参数也可以制成 GADT，并以 unit.

Answer 1

可以有异构列表，其中每个元素的类型取决于前一个元素并对后一个元素施加约束。核心思想是实现每个元素都需要定义在哪个上下文允许在哪个上下文，然后就是链式匹配上下文的问题：

 type ('a,'b) t =
  | [] : ('a,'a) t
  | ( :: ) : ('a, 'b) element * ('b,'c) t -> ('a,'c) t

这里的类型('a,'b) t描述了一个从上下文类型'a开始到上下文类型'b结束的异构列表。它是 ('a,'b) element 的类型定义，它确定允许哪些转换。

在您的情况下，元素类型可以定义为类似

module Tag = struct
  type final = Done
  type root = Root
  type fruit = Fruit
  type veggie = Veggie
end
type (_,_) element=
  | Fruit : (Tag.root, Tag.fruit) element
  | Veggie : (Tag.root, Tag.veggie) element
  | Apple : (Tag.fruit, apple) element
  | Banana : (Tag.fruit, banana) element
  | Carrot: (Tag.veggie, carrot) element
  | End: 'a -> ('a, Tag.final) element

请务必注意模块 Tag 仅提供与任何值无关的类型级标签（索引）。

有了这个定义：

let fruit = [Fruit]

是一个(Tag.root,Tag.fruit) element：该元素只允许在顶部并且要求在Tag.fruit上下文中允许在下面的元素。一个有效的下一个元素将是

let apple = [Fruit;Apple]

这是一个 (Tag.root,Tag.apple) t 路径。最后，一旦我们处于映射到具体类型的上下文中，就可以使用 End 构造函数关闭路径：

type complete = (Tag.root,Tag.final) t
let full_apple : complete =
  [Fruit; Apple; End { diameter=0; cultivar="apple"}]

并且这种构造仍然足够静态，通常可以以一些冗余为代价恢复足够的类型信息来处理部分路径：

let rec prefix: type a b c d. (a,b) t -> (c,d) t -> bool = fun pre x ->
  match pre, x with
  | [], _ -> true
  | Fruit :: q, Fruit :: r -> prefix q r
  | Veggie :: q, Veggie :: r -> prefix q r
  | [Apple], Apple :: r -> true
  | [Banana], Banana :: r -> true
  | [Carrot], Carrot :: r -> true
  | [Apple; End x], [Apple; End y] -> x = y
  | [Banana; End x], [Banana; End y] -> x = y 
  | [Carrot; End x], [Carrot; End y] -> x = y
  | _ -> false

是否可以让异构列表的元素取决于前面元素的类型？

Is it possible to have elements of a heterogeneous list depend on the type of preceding elements?

ocaml

gadt

heterogeneous-list

上下文

对可能解决方案的模糊想法