F#:过滤从另一个列表中的一个列表中找到的项目

Question

说我有两个清单:

let a = [1 .. 1000]
let b = [250 .. 500]

如何获取包含值{1-249,501-1000}的新列表？

Answer 1

由于您的列表已排序,您可以使用此(非尾递归)函数在线性时间内解决此问题:

let rec except a b =
    match (a, b) with
    | [], x | x, [] -> x
    | x::xs, y::ys ->
        if x < y then x :: except xs (y::ys)
        elif x > y then y :: except (x::xs) ys
        else except xs ys

尾递归版:

let rec except_tail_recursive a b =
    let rec loop acc a b =
        match (a, b) with
        | [], x | x, [] -> (List.rev acc) @ x
        | x::xs, y::ys ->
            if x < y then loop (x::acc) xs (y::ys)
            elif x > y then loop (y::acc) (x::xs) ys
            else loop acc xs ys
    loop [] a b

Answer 2

如果您需要纯F#解决方案,您的选择将根据您的要求而有所不同.如果您的列表不包含重复项,并且您不关心输出的顺序,则可以执行以下操作:

(Set.of_list a) - (Set.of_list b) |> Set.to_list

如果您知道您的商品已经过排序,那么这应该有效且效率很高:

let exclude =
  let rec exclude = function
    | [],_ -> [] 
    | a,[] -> a
    | (x::xs as l),(y::ys as r) -> 
        if x < y then x :: (exclude (xs, r))
        elif x > y then exclude (l, ys)
        else exclude (xs, ys)
  fun a b -> exclude (a,b)

如果您有两个可能包含重复项的列表,不一定要排序,您希望按照它们发生的顺序得到结果a,而您不关心性能,您可以这样做:

a |> List.filter (fun x -> not (List.contains x b))

Answer 3

如果您正在使用3.5或更高版本的框架,则可以执行以下操作

let c = System.Linq.Enumerable.Except(a,b)

它不是一个纯粹的F#解决方案,但它完成了工作.返回将是一个实例IEnumerable<int>而不是F#列表.