如何表示非空列表类型

2024-05-17 • 问答

我非常喜欢创建数据结构，使表示无效状态成为不可能，所以我想问一问我该如何在Reasonml中表示一个非空列表？

由于可以在[]和[head,...rest]之类的列表上进行模式匹配，所以我认为代表一个非空列表很容易，但是我还没有找到方法。

更新：由于下面的启发性回答，我得以提出真正令我满意的东西：

module List = {
  include List;
  type nonEmpty('a) = ::('a,list('a));
  let foldNonEmpty = (type a,fn,l: nonEmpty(a)) => switch(l) {
    | [head,...tail] => fold_left(fn,head,tail)
  };
}

module Number = {
  let min = List.foldNonEmpty(Pervasives.min);
  let max = List.foldNonEmpty(Pervasives.max);
}

Number.min([]); // illegal :D
Number.min([1]); // legal

不知道你们对此感觉如何，但是我认为它很棒。谢谢！

您还可以将不带GADT的新列表类型定义为：

type nonempty('a) =
  | First('a)
  | ::('a,nonempty('a))

与GADT解决方案相比，由于语法原因，您失去了一些语法优势

let l = [1,2,3,4]

隐式添加一个终端[]，但[x,...y]语法仍然有效

let x = [1,4,...First(5)];
let head =
  fun
  | [a,...q] => a
  | First(a) => a;

let tail =
  fun
  | [a,...q] => Some(q)
  | First(a) => None;

否则，编码

type nonempty_2('a) = { head:'a,more:list('a) };
let x = { head:1,more:[2,5 ] };
let head = (x) => x.head;
let tail = fun
| {more:[head,...more],_} => Some({head,more})
| {more:[],_} => None;

甚至更简单，并且不依赖于可能令人惊讶的语法构造。

编辑：::，中缀变量构造函数

如果定义中带有::的部分看起来很奇怪，那是因为它是OCaml语法的大写形式的剩余部分。在Ocaml中，

[x,... l ]

是书面

x :: l

本身就是

的中缀形式

(::)(x,l)

（与标准运算符：1 + 2相同的前缀形式也可以写成 (+)(1,2)（正当理由））最后一种形式也是[x,...l]的前缀形式。简而言之，我们有理由

[x,... l ] ≡ (::)(x,l)

使用OCaml语法作为两个符号之间的缺失链接。

换句话说，::是一个infix构造函数（也是唯一的）。使用最新版本的OCaml，可以使用以下命令定义自己的此infix构造函数版本：

type t = (::) of int * int list

相同的构造在原因上与

type t = ::(int,list(int))

然后，如果您编写[a,...b]，它将以(::)(a,b)作为新定义的运算符转换为::。同样，

[1,3]

实际上是

的快捷方式

[1,...[]]

例如，如果您同时定义了[]和::，例如

type alternating('a,'b) =
| []
| ::('a,alternating('b,'a) )
/* here the element of the list can alternate between `'a` and `'b`:*/
let l = [1,"one","two"]

您最终得到了用于异国情调列表的语法，其工作原理与标准列表。

您可以在此用例中使用GADT。

（我们也可以添加幻像类型https://blog.janestreet.com/howto-static-access-control-using-phantom-types/），但这不是强制性的

type empty = Empty;
type nonEmpty = NonEmpty;
type t('a,'s) =
  | []: t('a,empty)
  | ::(('a,t('a,'s))): t('a,nonEmpty);

使用方法

let head: type a. t(a,nonEmpty) => a =
  fun
  | [x,..._] => x;

类型提示来自https://sketch.sh/s/yH0MJiujNSiofDWOU85loX/

如何表示非空列表类型

my_winter13292 回答：如何表示非空列表类型

大家都在问