代表零列表和/或列表(零)

Question

背景

我们在F#中实现这个算法.

以下是Topor(1982)关于算法使用的符号的更多信息:

形式上,a 't list是null(表示nil)或者是hd(a是't)和a tl(是a 't list)...如果x是列表,我们测试是否是null通过写null x...我们创建一个新列表,添加元素a在现有列表的前面x,通过写a:x......我们表示包含该元素的单位名单a由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