如何在haskell中编写递归函数

Question

如何在Haskell中编写一个函数,它接受一个列表和一个数字,并删除大于该数字的所有元素并返回列表.

删除[5,4,3,9,1] 5应该返回[5,4,3,1]

我编写了以下方法,当它达到大于给定数字时,它变成无限循环.我出去了[5,4,3然后程序没有结束.

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程序,请告诉我这里我做错了什么.

谢谢

Answer 1

好吧,你有一个不错的开始,但重要的是要注意你没有采取最"Haskell"的方法.

让我向您展示一些解决此问题的方法:

方法1:递归函数

首先,我们可以编写一个递归函数(就像你一样)来解决这个问题.

为此,我们首先考虑一个基本情况(在正常情况下不允许无限循环的情况).这应该工作:

remove [] _ = []

这简单地说,如果我们要从空列表中删除元素,我们最终得到一个空列表.就这么简单.这_意味着我们不关心什么是价值x.

现在我们必须定义其他案例.为此,我会使用警卫(我确定还有其他方法,基础案例也为完成添加):

remove [] _ = []
remove (x:xs) y
 | x > y     = remove xs y
 | otherwise = x : remove xs y

所以,第一行(remove (x:xs) y)表示我们的函数将采用一个列表(其中x是head/first值,xs其余是).

第二行是说,如果x大于y,考虑其余的元素,我们不认为x是我们最终解决方案的一部分.

第三行(otherwise如果被击中则捕获所有情况,就像在其他语言else中的if/elseif/else条件块中一样).如果我们达到这一点,我们就知道x > y我们考虑其余的值(xs)并且包括在内是不正确的x,但我们现在已经完成了x.

现在,这种方法运行得很好,但有一个更简单的方法:

方法2:列表理解

使用列表推导,我们可以构建一个非常简单,强大的解决方案:

remove xs y = [x | x <- xs, not (x > y)]

如果你曾经研究过set-theory(特别是set-builder符号),那么你应该看起来很奇怪.让我们来看看每个部分的含义.

• [...] 括号中的东西只是意味着我们正在构建一个列表

• x |...- 意味着我们的列表将包含xs(这|意味着"这样")......

• x <- xs,- x是xs和(逗号表示"和")的元素...

• not (y > x)- y大于的不是真的x

如您所见,第二种方法几乎完全模仿了您的问题描述.这确实是Haskell的强大功能,单词和抽象往往直接映射到Haskell代码中.

方法3:使用 filter

正如下面的评论所述,第三种选择是将其定义为:

remove y = filter (<=y)

过滤器只保留小于或等于y的元素.(感谢Daniel Wagner采用这种方法).

Answer 2

您可以在函数args中使用模式匹配,并使用警卫进行过滤:

remove []    x = []
remove (h:t) x | h > x = remove t x
               | otherwise = h : remove t x

您也可以使用功能filter,它可以满足您的需求:

remove l x = filter (<= x) l