F#：递归函数：连接两个列表之间的公共值

Question

let rec common a b =
    match isolate(a) b with
    | (x::xs,isolate(b)) ->
        if memberof(b x) then [x,common(xs b)]
        else common(xs b)

这是我现在拥有的，但我一直在尝试许多不同的东西。 memberof() 采用浮点列表和浮点，如果浮点是浮点列表的成员，则 return 为真。 memberof() 函数有效。我不知道如何 return 新列表。

我还有一个 isolate() 函数，它会获取一个列表并删除列表中所有重复的浮点数。这看起来可能会有帮助。

编辑：我正在尝试弄清楚如何在 xs = [] 时 return 我的新列表。在中，答案是正确的，直到 common 不是 return 列表中的公共成员，而是包含所有元素的串联列表。

示例我希望common产生结果：

[1.0;2.0;3.0;4.0;5.0] [4.0;3.0;9.0] -> [3.0;4.0]

而不是 'common' 产生：

[1.0;2.0;3.0;4.0;5.0] [4.0;3.0;9.0] -> [1.0;2.0;3.0;4.0;5.0;9.0]

如何使用递归解决这个问题？

Answer 1

因此，要使用列表递归执行此操作，您需要这样的东西：

let common a b =
    let rec commonRec a b =
        match a with
        | [] -> [] // a is empty : no elements can be common so return empty list
        | x::xs ->
            if memberof x b then x :: commonRec xs b // if x is a member of b, keep it
            else commonRec xs b // otherwise continue with remaining elements
    commonRec (isolate a) (isolate b) // remove duplicates here

注意我在递归函数中去掉了isolate，开始时只需要执行一次

由于您没有 post isolate 或 memberof 函数的代码，我不想假设它们可能来自其他问题或此答案不会对其他人有用。当然，您可以自由地使用相同功能的不同实现。

我只是做了以下简单的定义：

let isolate lst =
    lst |> Set.ofList |> Set.toList

let memberof a list =
    List.contains a list

结果：

[1.0; 2.0; 3.0; 4.0; 5.0] [4.0; 3.0; 9.0] ----> [3.0; 4.0]

Answer 2

据我了解这个函数的要求，应该是return两个列表的intersection。由于这是一个基于集合的操作，它已经内置于 F#:

> set [1.0;2.0;3.0;4.0;5.0] |> Set.intersect (set [4.0;3.0;9.0]);;
val it : Set<float> = set [3.0; 4.0]

Answer 3

基于我给出的示例 to your earlier 。

注意：这与TheInnerLight的基本相同，我只是使用了前面问题中提到的格式，并举例说明了所有需要的功能。

由于您似乎没有使用这种格式，我将逐步完成我用来制作函数的步骤 common。

开始于

let funXYZ list =
    let rec funXYZInner list acc =
        match list with
        | head :: tail ->
            let acc = (somefunc head) :: acc
            funXYZInner tail acc
        | [] -> acc
    funXYZInner list []

并将函数命名为 common

let common list =
    let rec commonInner list acc =
        match list with
        | head :: tail ->
            let acc = (somefunc head) :: acc
            commonInner tail acc
        | [] -> acc
    commonInner list []

普通需要两个输入列表和一个输出列表。
首先，我们将设置签名，然后将两个列表传递给 commonInner。在这一点上我还没有决定如何处理这两个列表我知道我需要它们都做转换功能。
由于输出将来自累加器并且是一个列表，我们在 commonInner a b []

中用一个空列表初始化累加器

let common (a : 'a list) (b : 'a list) : 'a list =
    let rec commonInner a b acc =
        match list with
        | head :: tail ->
            let acc = (somefunc head) :: acc
            commonInner tail acc
        | [] -> acc
    commonInner a b []

现在我们可以决定如何将两个列表转换为一个列表，其中的项目是两者共有的。由于最终列表不会重复，让我们使用 isolate.

将每个列表单独转换为唯一项目列表

let common (a : 'a list) (b : 'a list) : 'a list =
    let aUnique = isolate a
    let bUnique = isolate b
    let rec commonInner a b acc =
        match list with
        | head :: tail ->
            let acc = (somefunc head) :: acc
            commonInner tail acc
        | [] -> acc
    commonInner aUnique bUnique  []

此时，当我们到达 match 语句时，我们有两个列表。我们只需要将一个列表中的每个项目与另一个列表中的每个项目进行比较，当它们相同时对项目进行一些处理。

使用函数式编程时，必须意识到列表是 immutable 并将其用于我们的利益。不可变是无法更改的，您无法添加、删除，甚至无法更改其值。现在您可能会问，为什么我可以添加到列表中，这一直在代码中完成。答案是原始列表留在堆栈中，使用原始列表和要添加的项目构造一个新列表。是的，这比必要的工作要多，但这就是它的工作原理。从我关于代码可证明性的角度来看，它物有所值。因此，要获得输出列表，最好从空列表开始创建列表，而不是修改现有列表。这就是为什么在我给你的例子中从来没有看到删除功能。

所以我们知道如何使用递归单独查看列表中的每个项目。如果这没有意义，那么只需在一些不同类型的列表上使用它并只打印值。对大多数人来说，学习递归就是其中之一，你努力了一段时间，然后一下子就明白了。

let rec processlist list =
    match list with
    | head :: tail ->
        do something with head, e.g. print head
        processlist tail
    | []

当我们有一个 head 和另一个列表 b

时，我们必须做出决定

if (memberof b hd) the

这让我们做到了这一点

let common (a : 'a list) (b : 'a list) : 'a list =
    let aUnique = isolate a
    let bUnique = isolate b
    let rec commonInner a b acc =
        match list with
        | head :: tail ->
            if (memberof b head) then
                do something
                commInner tail acc
            else
                do something different
                commonInner tail acc
        | [] -> acc
    commonInner aUnique bUnique  []

当 a 中的 head 在列表 b 中时，我们要将其添加到累加器，acc 将成为输出列表。当 a 中的 head 不在列表 b 中时，我们不想将它添加到累加器中，acc 将成为输出列表。

let common (a : 'a list) (b : 'a list) : 'a list =
    let aUnique = isolate a
    let bUnique = isolate b
    let rec commonInner a b acc =
        match list with
        | head :: tail ->
            if (memberof b head) then
                let acc = head :: acc
                commInner tail acc
            else
                commonInner tail acc
        | [] -> acc
    commonInner aUnique bUnique  []

最后，由于使用 ::，累加器的输出列表倒序排列，我们只需在返回结果之前使用 reverse 反转列表即可。

let common (a : 'a list) (b : 'a list) : 'a list =
    let aUnique = isolate a
    let bUnique = isolate b
    let rec commonInner a b acc =
        match list with
        | head :: tail ->
            if (memberof b head) then
                let acc = head :: acc
                commInner tail acc
            else
                commonInner tail acc
        | [] -> reverse acc
    commonInner aUnique bUnique  []

这是工作代码

// Reverse the order of the items in a list.

// val reverse : l:'a list -> 'a list
let reverse l =
    let rec reverseInner l acc =
        match l with
        | x::xs -> 
            let acc = x :: acc
            reverseInner xs acc
        | [] -> acc
    reverseInner l []

// Predicate that returns true if item is a member of the list.

// val memberof : l:'a list -> item:'a -> bool when 'a : equality
let memberof l item =
    let rec memberInner l item =
        match l with
        | x::xs -> 
            if x = item then
                true
            else 
                memberInner xs item
        | [] -> false
    memberInner l item


// Return a list of unique items.

// val isolate : list:'a list -> 'a list when 'a : equality
let isolate list =
    let rec isolateInner searchList commonlist =
        match searchList with
        | x::xs ->
            if (memberof commonlist x) then
                isolateInner xs commonlist
            else
                let commonlist = (x :: commonlist)
                isolateInner xs commonlist
        | [] -> reverse commonlist
    isolateInner list []

// val common : a:'a list -> b:'a list -> 'a list when 'a : equality
let common a b =
    let aUnique = isolate a
    let bUnique = isolate b
    let rec commonInner a b acc =
        match a with
        | x::xs ->
            if memberof b x then
                let acc = x :: acc
                commonInner xs b acc
            else
                commonInner xs b acc
        | [] -> reverse acc
    commonInner aUnique bUnique []

common [1.0;2.0;3.0;4.0;5.0] [4.0;3.0;9.0]      // val it : float list = [3.0; 4.0]

F#：递归函数：连接两个列表之间的公共值

F#: Recursive Functions: Concatenating the common values between two lists

recursion

f#

tail-recursion

function

helper