F#:递归函数:连接具有共同元素的2个列表 [英] F#: Recursive Functions: concatenate 2 lists which have common elements
问题描述
这就是我到目前为止所拥有的.感觉很近，但是我不确定如何解决第84行中的问题(第二到最后一行:elif List.append(isolate(a)，isolate(b))！= []然后是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 时，请参见:
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.
虽然您提供的代码只能与浮点类型列表一起使用，但将来要使其与更多类型一起使用，您将需要了解
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.
有一个谓词函数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屋！
