异构列表上的这种类型错误是什么意思？

Question

我有一个异构列表和一个函数

type ('ls,'tl) hlist =
  | Nil : ('a,'a) hlist
  | Cons: 'a * ('l, 't) hlist -> ('a -> 'l, 't) hlist

let rec headlist l = 
  match l with
  | Cons (h, t) -> Cons (head h, headlist t)
  | Nil -> Nil

并想遍历 hlist 个不同类型的 list，并构建每个列表的头部列表。这个想法是这样的：

headlist Cons( [1,2,3], Cons( ['a','b'], Cons( [true,false], Nil ))) 
= Cons( 1, Cons( 'a', Cons( true, Nil)))

但是，我遇到了类型错误。

Error: This expression has type ('a, 'b list -> 'a) hlist
       but an expression was expected of type
         ('b list -> 'a, 'b list -> 'a) hlist
       The type variable 'a occurs inside 'b list -> 'a

我不明白类型错误。它在说什么？我是不是在尝试做一些不可能的事情？

Answer 1

我认为没有描述您想要的功能的类型。你想说输入是一个 hlist 所有异构类型都是列表。我不知道怎么说，这对我来说意味着你不能有这样的功能。

但是，我错了很多次，GADT是我特别不稳定的东西。

Answer 2

如果我没理解错的话，你的函数 headlist 的类型应该是 ('a list -> 'b list -> ... -> 'z, 'z) hlist -> ('a -> 'b -> ... > 'z, 'z) hlist。我认为没有一种 OCaml 类型可以涵盖所有可能的特性。因此，编译器会寻找更简单的类型，因此会出现奇怪的错误消息。

Answer 3

您的问题始于这样一个事实，即无法为您想到的 headlist 函数编写类型。由于通常需要显式地编写操作 GATD 的函数类型，因此最好开始编写此类型，以检查是否可以编写该类型；并且仅在可以省略显式类型注释的极少数情况下才将其删除。

问题的根源在于异构列表比普通列表严格得多。特别是，根据此类列表所需的操作，经常需要定制专门的异构列表类型。例如，对于经典的异构列表：

type void = |
module Hlist = struct
  type 'a t =
    | []: void t
    | (::): 'a * 'l t -> ('a -> 'l) t

  let head(x::_) = x
  let rec length: type a. a t -> int = function
    | [] -> 0
    | a :: q -> 1 + length q 
end

无法表达条件：异构列表的所有元素都是至少有一个元素本身的异构列表。但是，可以定义另一个强制执行此条件的列表类型：

module Hlist_of_nonempty_hlist_0 = struct
  type 'a t =
    | []: void t
    | (::): (('h -> 'more) as 'a) Hlist.t * 'l t -> ('a -> 'l) t
end

有了这个新的列表类型，我可以计算所有嵌套列表的长度：

let rec map_length: type a. a Hlist_of_nonempty_hlist_0 t -> int list = function
 | [] -> []
 | a :: q -> Hlist.length a :: map_length q

但是，我仍然不能将head应用于所有元素，因为head的类型不容易访问。一种选择是将这些类型直接存储在 Hlist_of_nonempty_hlist:

的类型中

module Hlist_of_nonempty_hlist = struct
  type ('a,'b) t =
    | []: (void,void) t
    | (::):
       (('h -> 'more) as 'a) Hlist.t * ('l,'hl) t
       -> ('a -> 'l, 'h -> 'hl) t
end

有了这个专门的异构列表类型，写 map_head 的类型就变得简单了：

let rec map_head:
  type l hl. (l, hl) Hlist_of_nonempty_hlist.t -> hl Hlist.t
  = function
  | [] -> []
  | (a::_) :: q -> a :: map_head q

但这是一个功能类型的大量设计工作。更进一步，尝试在异构列表上编写任何通用函数通常需要大量多态记录和仿函数。

异构列表上的这种类型错误是什么意思？

What does this type error on heterogeneous lists means?

ocaml

gadt