如何使用Haskell中的foldr函數在無限列表中查找元素？

Question

我正在嘗試使用foldr函數在Haskell中創建elem函數的新實現。

到目前爲止，我有這樣的：

count :: Eq a => a -> [a] -> Integer 
count x (y:ys) = foldl (\counter y -> if y == x then counter + 1 else counter) 0 ys 
count _ [] = 0 

elem' :: Eq a => a -> [a] -> Bool 
elem' x (y:ys) = foldr (\i elem-> if (count x (y:ys)) > 0 then True else False) False ys 
elem' _ [] = False 

的count功能的計時x的occurances的使用foldl數（函數我寫的）。這對於有限列表來說工作得很好，但問題是我想利用foldr無限列表的延遲計算。如果我嘗試使用無限列表作爲輸入，程序將永遠掛起。

基本上我想「爆發」，一旦我找到列表中的任何實例並返回true，否則返回false。

感謝您的幫助。

Answer 1

讓我們開始對foldr模式的基本框架：

elem :: Eq a => [a] -> Bool 
elem x xs = foldr kons knil xs 

當foldr看到[]，它將返回knil。因爲沒有什麼是空列表的元素，我們的結論是

knil = False 

當foldr kons False看到一個列表a : as，它返回kons a (foldr kons False as)。我們可以假設電感是foldr kons False as = elem x as，所以我們尋求

elem x (a : as) = kons a (elem x as) 

來解決kons我敢打賭，你可以想出的kons定義完成了。注意布爾短路行爲，以使其高效並避免無限列表中的問題。