f# - 从两个列表中删除相同的值并使用 F# 中的 List.fold 比较它们

Question

我正在尝试创建一个函数，该函数接受两个列表，删除一个列表中也存在于另一个列表中的值。例如，如果我们有列表 [1;2;3] 和 [1;2;3;4]，那么第一个列表变为空 []第二个列表只是 [4]。最后，我只是在比较两个列表的时候。我正在尝试为此使用 List.fold，因为我想更好地理解它。我还创建了自己的文件夹功能，用于从列表中删除元素。我是 F# 的新手，所以我只提出了部分解决方案

let rec delete x list =
    match list with 
    | [] -> []
    | hd:: tl when hd = x -> tl
    | hd:: tl-> hd:: delete x tl


let myFunc list1 list2 = 
    let x = list1 |> List.fold(delete) [] list2
    let y = list2 |> List.fold(delete) [] list1    
    x = y

但这不起作用，当我尝试使用 delete 函数时，编译器告诉我“类型 '('a -> 'b)' 不支持 'equality' 约束，因为它是函数类型”使用 list.fold 方法。

Answer 1

虽然您说您正在尝试使用 List.fold 来更好地理解它，但还有另一个 List 函数可以使它更简单。这是使用 List.except，它是将列表视为集合的众多方法之一。

let list1 = [1;2;3] 
let list2 = [1;2;3;4] 

let myFunc list1 list2= 
    list1 |> List.except list2, list2 |> List.except list1

printfn "%A" (myFunc list1 list2) 

[],[4]

如果您想在这里理解 List.fold，您可以尝试使用 List.fold 创建 except 的显式实现。然而，同样，使用 List.filter 实现起来更简单。

let list1 = [1;2;3] 
let list2 = [1;2;3;4] 

let except exclude src =
    src |> List.filter (fun i -> exclude |> List.contains i |> not)

let myFuncCustom list1 list2 = 
    (list1 |> except list2), (list2 |> except list1)

printfn "%A" (myFuncCustom list1 list2)

[],[4]

所以你真的想使用 List.fold 来实现 filter。在这种情况下，您实际上需要 List.foldBack:

let filter f src =  
    List.foldBack (fun item filtered  -> 
        if f item then item :: filtered else filtered) src []

您可以使用 List.fold，但结果会相反，您需要将其通过管道传输到 List.rev 中。请注意 List.fold 只接受三个参数:第一个是 folder 函数；第二个成为输出的累加器 - 在这种情况下也是一个列表;最后，要折叠的源列表。 (让我们也展开 List.contains):

    let list1 = [1;2;3] 
    let list2 = [1;2;3;4] 
    
    let rec contains item  = function
        | [] -> false
        | hd::tl when  hd = item -> true
        | hd::tl -> contains item tl
    
    let filter f src =  
        src 
        |> List.fold (fun filtered item  -> 
            if f item then item :: filtered else filtered) []
        |> List.rev
    
    let except exclude src =
        src |> filter (fun i -> exclude |> contains i |> not)
    
    let myFuncCustom list1 list2 = 
        (list1 |> except list2), (list2 |> except list1)
    
    printfn "%A" (myFuncCustom list1 list2)

    [],[4]