F#:递归函数:连接 2 个具有公共元素的列表 [英] F#: Recursive Functions: concatenate 2 lists which have common elements

问题描述

这就是我目前所拥有的.感觉很接近，但我不知道如何解决第 84 行中的问题(倒数第二行:elif List.append(isolate(a),isolate(b)) != [] then List.append(isolate(a),隔离(b))).

So here is what I have so far. It feels close but im not sure how to fix the problems in line 84 (2nd to last line: elif List.append(isolate(a),isolate(b)) != [] then List.append(isolate(a),isolate(b))).

    (* val isolate : l:'a list -> 'a list when 'a : equality *)
    let rec isolate (l:'a list) = 
        match l with
        | [] -> []
        | x::xs ->
            if memberof(x,xs)
            then
                let xs = remove (x,l)
                isolate xs
            else isolate xs
    ( * val common : 'a list * 'a list -> 'a list when 'a : equality *)
    let rec common (k: 'a list, l:'a list) = 
        match ((k:'a list),(l:'a list)) with
        | (a, b) -> 
            if a=[] then []
            elif b=[] then []
            elif List.append(isolate(a),isolate(b)) != [] then List.append(isolate(a),isolate(b))
            else []

要求发布完整代码:

(* val sumlist : l:float list -> float *)
let rec sumlist l =  
    match (l:float list) with
    | [] -> 0.0
    | a::x -> (sumlist x) + a
    (* :: creates a list. *)
sumlist([1.0;2.0;3.0])
(* val squarelist : l:float list -> float list *)
let rec squarelist l = 
    match (l:float list) with
    | [] -> []
    | a::x -> (a*a)::(squarelist x)

(* val mean : l:float list -> float *)
let mean l = 
    match (l:float list) with
    | [] -> 0.0
    | l -> (sumlist l)/(float)l.Length
mean([1.0;2.0;3.0])
(* val mean_diffs : l:float list -> float list *)
let mean_diffs l = 
    match l with
    set a = mean(l)

    | [] -> []
    let rec diffs (a,l)=
        match l with
        | x::xs -> (x-(mean(l))::diffs(xs)
        | [] -> l
mean_diffs([1.0;2.0;3.0])

(* val variance : l:float list -> float *)
let variance l = 
    match (l:float list) with
    | [] -> 0.0
    | l -> (sumlist (squarelist (mean_diffs l)))/(float)l.Length


(* End of question 1 *) (* Do not edit this line. *)

(* Question 2 *) (* Do not edit this line. *)

(* val memberof : 'a * 'a list -> bool when 'a : equality *)
let rec memberof l=
    match (l: 'a * 'a list) with
    | (t,[]) -> false
    | (t, x::xs) when t=x -> true
    | (t, x::xs) -> t=x || memberof(t,xs)

(* val remove : 'a * 'a list -> 'a list when 'a : equality *)
let rec remove ((k:'a),(l:'a list)) = 
    match l with
    | [] -> []
    | x::xs when x=k -> xs
    | x::xs ->x::(remove(k,xs))

(* End of question 2 *) (* Do not edit this line *)

(* Question 3 *) (* Do not edit this line *)

(* val isolate : l:'a list -> 'a list when 'a : equality *)
let rec isolate (l:'a list) = 
    match l with
    | [] -> []
    | x::xs ->
        if memberof(x,xs)
        then
            let xs = remove (x,l)
            isolate xs
        else isolate xs

(* End of question 3 *) (* Do not edit this line *)

(* Question 4 *) (* Do not edit this line *)

(* val common : 'a list * 'a list -> 'a list when 'a : equality *)
let rec common (k: 'a list, l:'a list) = 
    match ((k:'a list),(l:'a list)) with
    | (a, b) -> 
        if a=[] then []
        elif b=[] then []    
        elif List.append(isolate(a),isolate(b)) <> [] then List.append(isolate(a),isolate(b))
        else []
common([1.0;2.0;6.0;10.0],[5.0;6.0;10.0])

看来 <> 已经解决了问题，但您对我的函数 mean_diffs 有什么建议吗?

It seems that <> has fixed the problem but do you have any advice on my function mean_diffs?

推荐答案

由于这看起来您正在学习一门课程并且它建立在前面的练习的基础上，因此代码被转换为更符合 F# 惯用语和递归的标准化格式使它们在您访问 currying 时更易于使用的功能，请参阅:F# 的乐趣和利润 和 函数作为一等值 (F#) 和其他更高级的概念.

Since this appears that you are working on a course and it is building upon the previous exercises, the code is converted to more F# idiomatic and a standardized format of recursive functions to make them easier to use when you get to currying See: F# for fun and profit and Functions as First-Class Values (F#) and other more advanced concepts.

格式基本是

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

其中 funXYZ 是一个没有 rec 的公开函数名称.我不记得源代码了，但是如果您可以实现一个需要 rec 且不公开 rec 的函数，它会使代码更具可移植性.

where funXYZ is an exposed function name that does NOT have a rec. I can't recall the source but if you can implement a function needing a rec with the rec not being exposed it makes the code more portable.

基本概念是你把一个列表拉成一个head和tail:

The basic concept is that you take a list and pull the list apart into a head and tail:

head :: tail

然后你处理头部:

somefunc head

然后将结果累加到累加器中

then accumulate the result into the accumulator

let acc = value :: acc
let acc = value + acc
let acc = acc + (value * value)

然后处理列表的其余部分，例如尾部，传递累加器

then process the remainder of the list, e.g. tail, passing the accumulator

funXYZInner tail acc

当输入列表匹配为空时

| []

只返回累加器中累加的结果

just return the result which was accumulated in the accumulator

acc

内部函数 funXYZInner 确实有一个 rec 并使用一个 累加器，即acc.这将有助于理解如何使用尾调用，这将防止您在大型计算.

The inner function funXYZInner does have a rec and uses an accumulator, i.e. acc. This will help in understanding how to use tail calls which will keep you from running out of memory on large computations.

您可能已经知道，使用 match 语句您希望涵盖 match 变量的所有情况.这是因为代数数据类型，也是您看到有关并非所有情况都涵盖的警告的原因.如果您看到这些警告之一并且不知道为什么会收到它，则您需要修复它们，否则就会冒出现意外运行时错误或崩溃的风险.

You probably know already that with match statements you want to cover all of the cases of the match variable. This is because of algebraic data types and is the reason you see those warnings about not all cases being covered. If you see one of those warnings and don't know why you are getting it you need to fix them, or run the risk of unexpected runtime errors or crashes.

虽然您提供的代码仅适用于浮点类型列表，但将来要使其适用于更多类型，您需要了解 LanguagePrimitives.GenericZero<^T> 类型函数 (F#).

While the code you gave can only work with float type list, in the future to make it work with more types you will need to learn about LanguagePrimitives.GenericZero<^T> Type Function (F#).

添加了一些更基本的功能，因为它们是需要的，例如reverse，并帮助显示随着示例变得更复杂的进展.

There are some more basic functions that were added because they were needed, e.g. reverse, and help to show the progression as the examples get more complex.

如果例子是建立在自己的基础上的，而你在最后一个中有一个特定的错误，最好给例子一个更好的基础，这样可以减少第一次学习递归函数时遇到的常见问题.

Do to the fact that examples build upon themselves and you had a specific error in the last one, it was better to give the examples a better foundation which should mitigate common problems encountered when first learning about recursive functions.

关于累加器，累加器可以容纳不同的类型，例如float、list、int，并且在递归函数中可以使用多个累加器，例如numeratorAcc、denominatorAcc.同样通过提取累加器值的计算，例如let acc = ...，当您使用更高级的函数时，您只需传入一个函数来替换该计算.

With regards to the accumulator, the accumulator can hold different types, e.g. float, list, int, and there can be more than one accumulator being used in the recursive function, e.g. numeratorAcc, denominatorAcc. Also by pulling out the calculation of the accumulator value, e.g.let acc = ..., when you get to more advanced functions you can just pass in a function to replace that calculation.

有一个 predicate 函数 memberof不使用蓄能器.谓词是一个返回 true 或 false 的函数，一旦您达到所需的值，您就可以停止处理列表的其余部分.

There is one predicate function memberof which does not use an accumulator. A predicate is a function that returns true or false, and once you reach the desired value you can stop processing the remainder of the list.

另外值得注意的是，虽然一些函数可以调用之前定义的函数，但示例不会进行调用，因此它们可以一次性处理列表.当函数使用列表调用其他函数时，每个函数都必须处理整个列表才能返回结果.通过使用 rec 函数，有时可以通过使用头部进行多次计算来处理列表一次.然而，有时这是无法做到的.我没有以某种方式最大化这些功能，而是给它们留下了一种为学习提供更多变化的方式.随意重写它们，这将导致函数组合.

Also of note is that while some of the functions could call earlier defined functions, the examples don't make the calls so that they can process the list in one pass. When functions call other functions with list, each function has to process the entire list to return the result. By using rec functions it is sometimes possible to process the list once by doing multiple calculations with the head. However there are times this cannot be done. I did not maximize the functions one way or the other but left them a way that give more variation for learning. Feel free to rewrite them which will lead to function composition.

您可能会对这些示例有更多疑问，因此请作为单独的 SO 问题提出，而不是以此为基础.

You will probably have more questions about these examples, so please ask as separate SO questions instead of building on this one.

所有代码

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

reverse [ 3.0; 2.0; 1.0 ]  // val it : float list = [1.0; 2.0; 3.0]    

// val length : l:'a list -> int
let length l =
    let rec lengthInner l acc =
        match l with
        | x::xs -> 
            let acc = acc + 1
            lengthInner xs acc
        | [] -> acc
    lengthInner l 0

length [ 3.0; 2.0; 1.0 ]  // val it : int = 3

// val sum : l:float list -> float
let sum l =
    let rec sumInner l acc =
        match l with
        | x::xs -> 
            let acc = acc + x
            sumInner xs acc
        | [] -> acc
    sumInner l 0.0

sum [ 1.0; 2.0; 3.0 ]  // val it : float = 6.0

// val square : l:float list -> float list
let square (l : float list) = 
    let rec squareInner l acc =
        match l with
        | x::xs -> 
            let acc = (x * x) :: acc
            squareInner xs acc
        | [] -> reverse acc
    squareInner l []

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

// val mean : l:float list -> float
let mean l = 
    let rec meanInner l sumacc lengthacc =
        match l with
        | x::xs -> 
            let sumacc = sumacc + x
            let lengthacc = lengthacc + 1.0
            meanInner xs sumacc lengthacc
        | [] -> sumacc / lengthacc
    meanInner l 0.0 0.0

mean([1.0;2.0;3.0]) // val it : float = 2.0

// val mean_diffs : l:float list -> float list
let meanDiff l = 
    let rec meanDiffInner l m acc =
        match l with
        | x::xs -> 
            let diff = (x - m)
            let acc = diff :: acc
            meanDiffInner xs m acc
        | [] -> reverse acc
    meanDiffInner l (mean l) []

meanDiff [ 1.0; 2.0; 3.0 ]  // val it : float list = [-1.0; 0.0; 1.0]


// From: https://en.wikipedia.org/wiki/Variance
// Suppose a population of numbers consists of 3, 4, 7, and 10. 
// The arithmetic mean of these numbers, often informally called the "average", is (3+4+7+10)÷4 = 6. 
// The variance of these four numbers is the average squared deviation from this average. 
// These deviations are (3–6) = –3, (4–6) = –2, (7–6) = 1, and (10–6) = 4. 
// Thus the variance of the four numbers is ((-3)^2 + (-2)^2 + (1)^2 + (4)^2) / 4 = 15/2 = 7.5

// val variance : l:float list -> float
let variance l = 
    let deviations = meanDiff l
    let rec varianceInner l numeratorAcc denomenatorAcc =
        match l with
        | devation::xs ->
            let numeratorAcc = numeratorAcc + (devation * devation) 
            let denomenatorAcc = denomenatorAcc + 1.0
            varianceInner xs numeratorAcc denomenatorAcc
        | [] -> numeratorAcc / denomenatorAcc
    varianceInner deviations 0.0 0.0

variance [ 1.0; 2.0; 3.0 ]          // val it : float = 0.6666666667
variance [ 3.0; 4.0; 7.0; 10.0 ]    // val it : float = 7.5


(* End of question 1 *) (* Do not edit this line. *)

(* Question 2 *) (* Do not edit this line. *)

// 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

memberof [ 1.0; 2.0; 3.0 ] 0.0  // val it : bool = false
memberof [ 1.0; 2.0; 3.0 ] 1.0  // val it : bool = true
memberof [ 1.0; 2.0; 3.0 ] 2.0  // trueval it : bool = true
memberof [ 1.0; 2.0; 3.0 ] 3.0  // val it : bool = true
memberof [ 1.0; 2.0; 3.0 ] 4.0  // val it : bool = false

// val remove : l:'a list -> item:'a -> 'a list when 'a : equality
let remove l item =
    let rec removeInner l item acc =
        match l with
        | x::xs ->
            if x = item then
                removeInner xs item acc
            else
                let acc = x :: acc
                removeInner xs item acc
        | [] -> reverse acc
    removeInner l item []

remove [ 1.0; 2.0; 3.0 ] 0.0    // val it : float list = [1.0; 2.0; 3.0]
remove [ 1.0; 2.0; 3.0 ] 1.0    // val it : float list = [2.0; 3.0]
remove [ 1.0; 2.0; 3.0 ] 2.0    // val it : float list = [1.0; 3.0]
remove [ 1.0; 2.0; 3.0 ] 3.0    // val it : float list = [1.0; 2.0]
remove [ 1.0; 2.0; 3.0 ] 4.0    // val it : float list = [1.0; 2.0; 3.0]

(* End of question 2 *) (* Do not edit this line *)

(* Question 3 *) (* Do not edit this line *)

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

isolate [ 1.0; 2.0; 3.0 ]                                    // val it : float list = [1.0; 2.0; 3.0]
isolate [ 1.0; 1.0; 2.0; 3.0 ]                               // val it : float list = [1.0; 2.0; 3.0]
isolate [ 1.0; 2.0; 2.0; 3.0 ]                               // val it : float list = [1.0; 2.0; 3.0]
isolate [ 1.0; 2.0; 3.0; 3.0 ]                               // val it : float list = [1.0; 2.0; 3.0]
isolate [ 3.0; 2.0; 1.0; 1.0; 2.0; 3.0; 2.0; 1.0; 1.0; 3.0]  // val it : float list = [3.0; 2.0; 1.0]

(* End of question 3 *) (* Do not edit this line *)

(* Question 4 *) (* Do not edit this line *)

// val common : a:'a list -> b:'a list -> 'a list when 'a : equality
let common a b = 
    let rec commonInner a b acc =
        match (a,b) with
        | (x::xs,b) ->
            if (memberof acc x) then
                commonInner xs b acc
            else
                let acc = x :: acc
                commonInner xs b acc
        | ([],y::ys) ->
            if (memberof acc y) then
                commonInner [] ys acc
            else
                let acc = y :: acc
                commonInner [] ys acc
        | ([],[]) -> reverse acc
    commonInner a b []

common [ 1.0; 2.0; 6.0; 10.0] [ 5.0; 6.0; 10.0 ]   // val it : float list = [1.0; 2.0; 6.0; 10.0; 5.0]

这篇关于F#:递归函数:连接 2 个具有公共元素的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！