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!

Tunic

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.

Genro

ooookay, thanks for your answer but I must say I'm a bit overwhelmed here. I did not even know you could write fun to shortcut pattern matching (that's what this does, right?). Is this syntax documented somewhere? What about the ::, where can I see what this does exactly? Do I have to learn ocaml first for this? – Tunic

The notation fun ... => ... | ... => ... is indeed just a shortcut for (x)=>switch(x){ | ... => ... | ... => ... }. – Genro

ok, so if you can use the infix constructor to sort of "concatenate" types, why not go for a definition of type nonEmpty('a) = ::('a, list('a))? – Tunic

also, as soon as I introduce the nonEmpty('a) type (either my or your version) every single usage of ['a] is inferred as nonEmpty('a) instead of list('a). Why is that? Am I shadowing the definition of list? – Tunic

You can indeed define nonEmpty('a)=::('a,list('a)), it may work even better because you get back tyhe [1,2,3] syntax, and can easily extract a list. – Genro

But yes, one issue with such definition is that you are shadowing the original variant constructor :: from the list type. There is two way to mix harmoniously two types of list: either with type-guided disambigation: ([1]:list(_)) selects the right constructor. Orthogonally, you can define the exotic list inside a module/submodule and use the local open syntax: Nonempty.[1,2,3] – Genro

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/

Hebert

Note that the list constructor syntax []and :: requires OCaml 4.03.0, and hence BuckleScript 6.x. It does not work on BuckleScript 5.x which uses OCaml 4.02.3. – Virginavirginal

Also, there are a few layers of syntax sugar here and it might make more sense to know that [x, ..._] translates to x :: _ in OCaml, where the :: constructor is used as an infix operator. For construction it would be x :: []. If the constructors had ordinary constructor names, Empty for [] and Cons for :: for example, it would be equivalent to Const(x, Empty)). That is how lists are conceptually implemented. – Virginavirginal