如何在Haskell中编写递归函数 [英] How to write a recursion function in haskell
问题描述
我该如何在Haskell中编写一个函数，该函数接受一个列表和一个数字，并删除所有大于该数字的元素并返回列表.
How can I write a function in Haskell which takes a list and a number and it removes all the elements greater than that number and returns the list.
删除[5，4，3，9，1] 5应该返回[5,4,3,1]
remove [5, 4, 3, 9, 1 ] 5 should return [5,4,3,1]
我编写了以下方法，该方法在遇到大于给定数字的某些位置变成无限循环.我离开了[5,4,3，然后程序没有结束.
I wrote the following method which is becoming infinite loop some where when it hits the greater than the given number. I am getting out [5,4,3 and then program is not ending.
remove l1 x = if (null l1 == True)
then l1
else if (head l1 > x)
then remove (drop 0 l1) x
else ((head l1) : remove (tail l1) x)
这是我第一次尝试Haskell程序，请在这里建议我做错了什么.
This is first time I am trying Haskell programs, please suggest me what I am doing wrong here.
谢谢
推荐答案
嗯，您的起步不错，但请务必注意，您并未采取最"Haskell"的方法.
Well, you're off to a decent start, but it's important to note that you are not taking the most "Haskell" approach to this.
让我向您展示一些解决此问题的方法:
Let me show you a few different approaches to this problem:
方法1:递归函数
首先，我们可以编写一个递归函数来解决这个问题.
First and foremost, we could write a recursive function (as you are) to solve this.
为此，我们首先适应一个基本情况(在正常情况下不会允许无限循环).这应该起作用:
To do this we first accommodate for a base-case (one that will not, under normal circumstances, allow for an infinite loop). This should work:
remove [] _ = []
这只是说，如果我们要从一个空列表中删除元素，我们最终将得到一个空列表.就这么简单. _表示我们不在意x是什么值.
This simply says that if we are to remove elements from an empty list, we end up with an empty list. It's that simple. The _ means that we don't care what value x is.
现在我们必须定义其他情况.为此，我将使用警卫(我确定还有其他方法，为了完成也添加了基本情况):
Now we must define our other cases. For this, I would use guards (I'm sure there are other approaches, base-case added also for completion):
remove [] _ = []
remove (x:xs) y
| x > y = remove xs y
| otherwise = x : remove xs y
因此，第一行(remove (x:xs) y)表示我们的函数将获取一个列表(其中x是head/first值，而xs是其余值).
So, the first line (remove (x:xs) y) is saying that our function will take a list (where x is the head/first value and xs is the rest).
第二行说，如果x大于y，请考虑其余元素，而我们不认为x是我们最终解决方案的一部分.
The second line is saying that, if x is greater than y, consider the rest of the elements, and we don't consider x to be a part of our final solution.
第三行(otherwise捕获所有命中的情况，就像其他语言中if/elseif/else条件块中的else).如果到了这一点，我们知道x > y是不正确的，因此我们考虑其余的值(xs)并包含x，但现在已经完成了x的操作.
The third line (otherwise catches all cases if hit, and is like an else in an if/elseif/else conditional block in other languages). If we get to this point, we know that it is not true that x > y so we consider the rest of our values (xs) and we include x, but we're done with x for now.
现在，这种方法可以正常工作，但是有一种更简单的方法:
Now, this approach works decently, but there is a simpler one:
方法2:列表理解
使用列表理解，我们可以构建一个非常简单，功能强大的解决方案:
Using list comprehensions we can build a very simple, powerful solution:
remove xs y = [x | x <- xs, not (x > y)]
如果您曾经学习过设置理论(尤其是
If you have ever studied set-theory (specifically set-builder notation) this should look oddly familiar to you. Let's walk through what each part means.
-
[...]-方括号中的内容仅表示我们正在构建列表
[...]- Something in brackets simply means we are constructing a list
x |...-表示我们的列表中将包含x，这样(|的意思是诸如")...
x |... - Means that our list will contain xs such that (the | means "such that")...
x <- xs,-x是xs的元素，并且(逗号表示和")...
x <- xs, - x is an element of xs and (the comma means "and")...
not (y > x)-y大于x
如您所见，第二种方法几乎完全模仿了问题的描述.这确实是Haskell的强大功能，单词和抽象趋向于几乎直接映射到Haskell代码中.
As you can see, this second approach almost exactly imitates your problem's description. This is truly the power of Haskell, words and abstraction tend to, nearly, map directly into Haskell code.
方法3:使用filter
Approach 3: Using filter
如下面的评论所述，第三个选择是将其定义为:
As the below comment states a third alternative would be to define it as such:
remove y = filter (<=y)
其中过滤器将仅保留小于或等于y的元素. (这种方法要感谢Daniel Wagner).
Where filter will only keep elements that are less than or equal to y. (Credit to Daniel Wagner for this approach).
这篇关于如何在Haskell中编写递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
