如何表示一个非空列表类型

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 用于此用例。

（我们也可以添加幻像类型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/

Answer 2

您也可以在没有 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)（理性） ) 而最后一种形式在道理上也是[x,...l]的前缀形式。简而言之，在 Reason 中我们有

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

使用 OCaml 语法作为两个符号之间缺少的 link。

换句话说，:: 是一个中缀构造函数（也是唯一的）。使用足够新的 OCaml 版本，可以使用

定义您自己的中缀构造函数版本

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

Reason 中的结构与

相同

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

然后如果你写 [a, ...b] 它被翻译成 (::)(a,b) 并且 :: 作为你新定义的运算符。同样，

[1,2,3]

实际上是

的快捷方式

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

因此，如果您同时定义 [] 和 ::，例如在这个愚蠢的示例中

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"]

你最终得到了一种用于奇异列表的语法，它的工作原理与标准列表。

如何表示一个非空列表类型

how to represent a non-empty list type

ocaml

list

reason