how to represent a non-empty list type

Question

I'm a big fan of creating data structures that make representing invalid states impossible, so I wanted to ask how I could represent a non empty list in reasonml?

Since it's possible to pattern match on lists like [] and [head, ...rest] I thought it would be easy to represent a non empty list, but I haven't found a way yet.

Update: Thanks to the enlightening answers below I was able to come up with something that really strikes my tune:

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

Don't know how you guys feel about it, but I think it's awesome. Thanks!

Answer 1

You can also define a new list type without GADT as:

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

Compared to the GADT solution, you lose some syntactic sugar, because the syntax

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

implicitly adds a terminal [] but the [x, ...y] syntax still works

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;

Otherwise, the encoding

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;

is even simpler and does not rely on potentially surprising syntactic constructions.

EDIT: ::, the infix variant constructor

If the part of the definition with :: seems strange, it is because it is a left-over of corner case of the OCaml syntax. In Ocaml,

[x, ... l ]

is written

x :: l

which is itself the infix form of

(::)(x,l)

(This the same prefix form of standard operator : 1 + 2 can also be written as (+)(1,2) (in Reason) ) And the last form is also the prefix form of [x,...l] in reason. In brief, in Reason we have

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

with the OCaml syntax as the missing link between the two notations.

In other words :: is an infix constructor (and the only one). With recent enough version of OCaml, it is possible to define your own version of this infix constructor with

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

The same construction carries over in Reason as

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

Then if you write [a, ...b] it is translated to (::)(a,b) with :: as your newly defined operator. Similarly,

[1,2,3]

is in fact a shortcut for

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

So if you define both [] and ::, for instance in this silly example

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

you end up with a syntax for exotic lists, that works exactly the same as standard lists.

Answer 2

You can use GADT for this use case.

(we can also add phantom type https://blog.janestreet.com/howto-static-access-control-using-phantom-types/) but it isn't mandatory

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

How to use it

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

type idea come form https://sketch.sh/s/yH0MJiujNSiofDWOU85loX/