使用递归或更高阶函数编写函数

Question

如何编写一个函数，其中需要一个谓词f和一个列表xx，如果fx对于某些x∈xs为真，则会重新生成一个函数？

例如：

ghci>exists (>2) [1,2,3] 
    True 

这是我写的函数：

exists :: (t->Bool)->[t]->Bool 
    exists f a []=error 
    exists f a (x:xs) 
       |if x∈f a =True 
       |otherwise= x:f a xs 

我知道这是不对的，但我不知道为什么。我是否需要先编写谓词函数f，然后在函数exists内使用它。因为我真的不知道如何比较列表xs中的一个元素与该函数。

Answer 1

如果我们看看你的定义，

exists :: (t -> Bool) -> [t] -> Bool 
exists f a []=error 
exists f a (x:xs) 
      |if x∈f a =True 
      |otherwise= x:f a xs 

我们看到你的类型是

exists :: (t -> Bool) -> [t] -> Bool 

所以exists必须带两个参数，一个类型为(t -> Bool)的谓词函数和一个类型为[t]的列表。它返回一个Bool。根据我们的规范意图，这看起来没问题。

让我们看看你的条件的第一行：

exists f a [] = error 

此功能突然有三个参数。 f和空列表构造函数[]看起来没问题，但在类型说明中未提及a。因此，我们删除它：

exists f [] = error 

现在，返回的error不是布尔值。但规范说它一定是。让我们假设我们要求exists (<2) []。那么问题的自然答案是True或False？或换言之，是否有任何元素x in []满足谓词f x？

到下一行，

exists f a (x:xs) 
     |if x∈f a =True 
     |otherwise= x:f a xs 

我们了解到，a具有由类型规范中去，所以让我们修剪它。由于我们现在对a自然不喜欢，所以为什么不在发生的任何地方修剪它。此外，由于if会产生一个语法错误，让我们摆脱这种过于自我：

exists f (x:xs) 
     | x∈f = True 
     | otherwise = x:f xs 

的x∈f没有多大意义，但f x一样。如果f x返回true，则将采取后卫变体。现在，这里返回的True听起来是正确的。它表示我们已经在列表中找到与谓词相匹配的元素 - 并且看到了，可能是x！

所以我们把注意力转向最后一行。 otherwise表示后卫f x未返回True。因此，x不满足谓词，所以我们必须搜索列表的其余部分。

右边x : f xs是特有的。 :表示我们将尝试返回一个列表，但函数的返回类型是Bool。如果我们尝试这种方式，类型检查器不会喜欢我们。此外，我们没有理由再看x，因为我们只是确定它不符合谓词。

你缺少的关键是我们需要递归在这一点上。我们需要以某种方式搜索列表的尾部xs - 递归意味着调用尾部的exists函数。

您的一般轨道是正确的，但再次询问是否有不清楚的地方。一种诀窍可能是按照递归情况的类型：“我需要提供exists才能返回Bool值？”。

Answer 2

而是采用fx，采用f x只适用于f作为x谓词if语句。您的otherwise子句也应返回Bool：列表中其余部分的exists的结果。

Answer 3

我想你想的已经存在的功能 - any：

Prelude> :t any 
any :: (a -> Bool) -> [a] -> Bool 
Prelude> any (<3) [1, 2, 3, 4] 
True 
Prelude> any (<3) [3, 4, 5, 6] 
False 

，然后在你的问题的精神 - 不只是得到一个工作的功能，但工作了它是如何做 - 我们可以查阅定义中拉开序幕：

any p xs = or (map p xs) 

我们map功能在列表上获得一个新的[Bool]列表，然后用or检查，看看是否任何人都True，WHI根据需要感谢懒评价短路的方式由CH：

Prelude> any (<3) [1, 2..] 
True 

Answer 4

你所需的示例性的使用是本

ghci>exists (>2) [1,2,3] 
True 

停止。 Hoogle时间。 （< ------这应该是哈斯克尔座右铭）

你想要一个带有两个参数的函数（“存在”）。第一个是一元函数(a -> Bool)，第二个是列表[a]。期望的结果是一个Bool

Hoogling that type signature，(a -> Bool) -> [a] -> Bool，顶部命中是any，all，和find。正如Andrew指出的那样，any就像“存在”功能一样。

作为一个附注，我的第一个想法是使用find，它返回Maybe a，然后模式匹配。如果它返回Nothing，那么结果将是False，否则为True。

另一方面，actual implementation只是any p = or . map p。

第三方说明可能是您的实际问题的答案。 map如何定义？ Hoogle再次成为你的朋友。搜索方法的名称，您可以找到链接到源的页面。我建议你为map和or这样做，但这里只会显示map。

map _ []  = [] 
map f (x:xs) = f x : map f xs 

这是递归列表的基本方法。 recursiveCall f (x:xs) = f x : recursiveCall f xs但是，如果可以使用map,filter或foldl/foldr来编写，那么您应该使用这些递归方法来完成。 （Stop。Hoogle时间，搜索这些方法名称并查看源代码;它非常简单。）

Answer 5

实际上，您的原始版本并没有太多的工作。要修复它，请写：

exists :: (t -> Bool) -> [t] -> Bool 
exists _ [] = False 
exists f (x:xs) 
      | f x = True 
      | otherwise = exists f xs