list - 表示一个 nil 列表和/或一个 list(nil)

Question

背景

我们正在 F# 中实现该算法。

这里有更多信息from Topor (1982)关于算法使用的符号:

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.

问题

我们想知道的是如何在 F# 中表达那些 nil , null , 和 list(nil)值。例如，我们应该使用 Option 类型、空列表还是其他类型？

我们的尝试

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 

使用列表时，对于 list(nil)我们使用 [[]]和 nil我们使用 [] .虽然这很好，但可能有一种更具表现力的方式来做到这一点。有时我们会使用 List.empty<'t list>和 List.empty<'t>当类型推断需要更多信息时。

Answer 1

论文给了你所有的答案:nil就是[]； null x 是对x 是否为空列表的测试； list(nil) 是 [[]]。

算法 B 到 F# 的简单翻译如下:

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