How to define a data structure for a list that cannot be empty in F#?

Question

Recently, I started learning F# and I am struggling to work with discriminated unions, lists en structures. I'd found an exercise where I need to do the following:

'Define a NonEmptyList<'a> data structure which can represent a list which can never be empty'

Attempt

let NonEmptyList (input : List<'a>) = 
   match input with
   | [] -> failwith "List canot be empty"
   | [x] -> x

Not really sure if this is correctly implemented with the let-keyword. I.e... do I need this construction perhaps:

type NonEmptyList<'a> = struct
    | List

edit 1

type NonEmptyList<'T> = 
  | Cons of 'T * List<'T>
  | Single of List<'T>

edit 2

let list1 : NonEmptyList<'T> = Single[1..10]
let list2 : NonEmptyList<'T> = Cons([1..3],[1..3]) 

I am receiving a parser error: This construct causes code to be less generic than indicated by the type annotations. The type variable 'T has been constrianed to be type 'a list.

Answer 1

First of all, my reading of the task is to give a type definition (using type) rather than a function that checks whether a list is empty.

To solve this, it's best to first understand normal F# lists:

type List<'T> = 
  | Cons of 'T * List<'T>
  | Empty 

Here, a list is either empty (represented by the Empty value) or it contains a value of type 'T followed by another list represented by List<'T>. This way, you can create:

let nop = Empty                      // Empty list
let oneTwo = Cons(1, Cons(2, Empty)) // List containing 1 and 2 

So, to answer the question, you will need a very similar definition to the one for List<'T>, except that it should not be possible to create an Empty list. You can start with something like this:

type NonEmptyList<'T> = 
  | Cons of 'T * NonEmptyList<'T>

Now that I removed Empty, we can no longer create empty lists - but this does not quite do the trick, because now you can never end any list. I won't give a full answer to avoid spoilers as I think figuring this out is the point of the exercise, but you will need something like:

type NonEmptyList<'T> = 
  | Cons of 'T * NonEmptyList<'T>
  | // One more case here

What can the last case be, so that it does not contain another List<'T> (and thus lets us end a list), but is not Empty, so that we cannot create empty lists?

Answer 2

A non-empty list consists of a head and an optional non-empty tail. You can represent such a type as a single-case union:

type NEL<'a> = NEL of 'a * NEL<'a> option
let l = NEL(1, Some(NEL(2, None)))

or a record type:

type NEL<'a> = {head : 'a; tail : NEL<'a> option}
let l = { head = 1; tail = Some({head = 2; tail = None})}