如何表示非空列表类型

Question

我非常喜欢创建可以表示无效状态的数据结构，所以我想问一下如何在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

不知道大家怎么看，我觉得挺好看的。谢谢！

Answer 1

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

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

与 GADT 解决方案相比，您失去了一些语法糖，因为语法

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

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

let x = [1, 2, 3, 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,3,4,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)(in Reason) ）最后一种形式也是[x,...l]in reason的前缀形式。简而言之，在理性中，我们有

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

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

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

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

相同的结构在 Reason 中延续

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

然后，如果您编写[a, ...b]它，则将其转换为(::)(a,b)with::作为您新定义的运算符。相似地，

[1,2,3]

实际上是一个捷径

[1,2,3, ...[]]

所以如果你同时定义[]and ::，例如在这个愚蠢的例子中

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

您最终会得到一个异国列表的语法，它的工作原理与标准列表完全相同。