F#:递归函数:连接两个列表之间的公共值 [英] F#: Recursive Functions: Concatenating the common values between two lists

问题描述

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()接受一个浮动列表和一个浮动，如果该浮动是该浮动列表的成员，则返回true. memberof()函数起作用.我不知道如何返回新列表.

Here is what I have right now, but I've been trying many different things. The memberof() takes a float list and a float and returns true if the float is a member of the float list. The memberof() function works. I can't figure out how to return the new list.

我还有一个isolate()函数，该函数将获取一个列表并删除列表中所有重复的浮点数.这似乎很有帮助.

I also have an isolate() function which will take a list and remove any duplicate floats within the list. This seem like it may be helpful.

edit:当xs = []时，我试图弄清楚如何返回我的新列表.在此线程中答案是正确的，直到common，它不会返回列表中的公共成员，而是包含所有元素的串联列表.

edit: I'm trying to figure out how to return my new list when xs = []. In this thread the answer is right until common which does not return the common members in a list but rather concatenated list containing all elements.

示例我希望common产生结果:

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

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

不是普通"生产:

[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]

[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]

如何使用递归解决此问题?

How can I solve this problem using recursion?

推荐答案

以我作为 answer 给出的示例为基础到您之前的问题.

Building upon the examples I gave as an answer to your earlier question.

注意:这与TheInnerLight的答案基本相同，我只是使用了前面问题中提到的格式并给出了所有所需功能的示例.

Note: This is basically the same as the answer by TheInnerLight, I just used the format mentioned in the earlier questions and gave examples of all of the needed functions.

由于您似乎没有使用这种格式，因此我将逐步介绍我用来制作函数common的步骤.

Since you appear to not be using this format I will walk through the steps I used to make the function 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 []

Common needs two input list and one output list.
First we will set the signature then then pass both list to commonInner. At this point I have not decided how to handle the two list I know that I need them both to do the transformation function.
Since the output will come from the accumulator and be a list, we initialize the accumulator with an empty list in 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将每个列表分别转换为唯一项列表.

Now we can decide how to transform the two lists into one list with items common to both. Since the final list will not have duplicates, lets transform each list individually into list of unique items using 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语句时，我们有两个列表.我们只需要将一个列表中的每个项目与另一个列表进行比较，并且当它们相同时，请对该项目执行某些操作.

At this point when we reach the match statement we have the two list. We only need to compare each item in one list against the other list and when they are the same do something with the item.

使用函数式编程时，您必须知道列表是不可变的，并将其用于我们的益处.不可变是无法更改的，不能添加，删除或更改其值.现在您可能会问，为什么要添加到列表中，这始终在代码中完成.答案是，原始列表保留在堆栈中，并且使用原始列表和要添加的项目构造了新列表.是的，这是多余的工作，但这就是它的工作方式.从我的角度来看，关于代码的可证明性，值得付出代价.因此，要获取输出列表，最好从空列表开始创建列表，而不是修改现有列表.这就是为什么在我给您的示例中从未看到过删除功能的原因.

With functional programming one has to be aware that list are immutable and use that to our benefit. An immutable is one that cannot be changed, you can not add to it, delete from it, or even change its value. Now you are probably asking, why can I add to a list, this is done all the time in the code. The answer is that the original list is left on the stack and a new list is constructed using the original list and the item to be added. Yes this is more work than necessary, but that's how it works. From my perspective with regards to provability of code, its worth the price. So to get the output list it is better to create the list starting from an empty list than to modify an existing list. That is why in the examples I gave you never saw a delete function.

因此，我们知道如何递归地查看列表中的每个项目.如果这没有意义，那么只需在一些不同类型的列表上使用它，然后仅打印值即可.对于大多数人来说，学习递归是其中的一件事，如果您挣扎了一段时间，然后立刻获得了递归.

So we know how to look at each item in a list individually with recursion. If this doe not make sense then just play with this on some list of different types and only print the values. Learning recursion for most people is one of those things were you struggle for a while then all at once you get it.

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

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

and we have to make a decision when we have a head and the other list 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中，该累加器将成为输出列表.

When the head from a is in list b then we want to add it to the accumulator, acc which will become the output list. When the head from a is NOT in list b then we do NOT want to add it to the accumulator, acc which will become the output list.

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反转列表，然后返回结果即可.

and lastly since the accumulator has the output list in a backward order because of the use of ::, we just use reverse to reverse the list before returning the result.

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#:递归函数:连接两个列表之间的公共值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！