使用遞歸或更高階函數編寫函數

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