Represent a nil list and/or a list(nil)

Question

Background

We are implementing this algorithm in F#.

Here is a little bit more information from Topor (1982) about the notation that the algorithm uses:

Formally, a 't list is either null (denoted nil) or has a hd (which is a 't) and a tl (which is a 't list)... If x is a list, we test whether it is null by writing null x... We create a new list, adding the element a at the front of an existing list x, by writing a:x... We denote the unit list containing the element a by list(a)... list(x) = x:nil.

Question

What we're wondering is how in F# to express those nil, null, and list(nil) values. For instance, should we be using the Option type, an empty list, or something else?

What We Have Tried

let rec kpermute k (xs: 't list) = 

    let rec mapPerm k xs ys =
        match ys with 
        | [] -> []
        | head::tail -> 
            let kpermuteNext = kpermute (k-1) (removeFirst head xs)
            let mapPermNext = mapPerm k xs tail
            mapcons head kpermuteNext mapPermNext

    match k with 
    | 0 -> [[]]
    | _ when xs.Length < k -> []
    | _ -> mapPerm k xs xs 

When working with lists, for list(nil) we use [[]] and for nil we use []. While that's fine, there might be a more expressive way to do it. There are also times when we use List.empty<'t list> and List.empty<'t> when the type inference needs more information.

Answer 1

The paper gives you all the answers: nil is []; null x is a test for whether x is the empty list; list(nil) is [[]].

The naïve translation of algorithm B to F# is as follows:

let rec minus a = function
    | [] -> failwith "empty list"
    | xh :: xt -> if xh = a then xt else xh :: minus a xt

let rec permute2 k x =
    if k = 0 then [[]]
    elif List.length x < k then []
    else mapperm k x x

and mapperm k x = function
    | [] -> []
    | yh :: yt -> mapcons yh (permute2 (minus yh x)) (mapperm x yt)

and mapcons a ps qs =
    match ps with
    | [] -> qs
    | ph :: pt -> a :: ph :: mapcons a pt qs