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