F#:从另一个列表中过滤一个列表中找到的项目 [英] F#: Filter items found in one list from another list

问题描述

说我有两个列表:

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

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

How do I get a new list that contains the values {1-249, 501-1000}?

推荐答案

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

Since your list is sorted, you can solve this in linear time using this (non-tail recursive) function:

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

这篇关于F#:从另一个列表中过滤一个列表中找到的项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！