在haskell中使用foldr進行搜索而不是foldl

因此，我在閱讀"Learn You A Haskell"，並在chapter about modules中定義了一個名爲search的函數，該函數檢查列表是否包含子列表。現在在haskell中使用foldr進行搜索而不是foldl

my_search :: Eq a => [a] -> [a] -> Bool 
my_search sub l = 
    let 
    len = length sub 
    eqTest = (\acc x -> if take len x == sub then True else acc) 
    in foldl eqTest False $ tails l

，我不知道爲什麼不能使用這是本章前面提到的foldl'，並且運行速度更快：

my_search' :: Eq a => [a] -> [a] -> Bool 
my_search' sub l = 
    let 
    len = length sub 
    eqTest = (\acc x -> if take len x == sub then True else acc) 
    in foldl' eqTest False $ tails l 


*Main> my_search [10^6,10^6+1] [1..10^7] 
True 
(7.76 secs, 3,197,168,792 bytes) 

*Main> my_search' [10^6,10^6+1] [1..10^7] 
True 
(4.53 secs, 2,964,986,352 bytes)

更妙的是，有一個小的調整，我們可以使用foldr也可以處理短路無限列表。

my_searchr :: Eq a => [a] -> [a] -> Bool 
my_searchr sub l = 
    let 
    len = length sub 
    eqTest = (\x acc -> if take len x == sub then True else acc) 
    in foldr eqTest False $ tails l

綜觀isInfixOf的definition，我看到它與any，它使用foldr實現。

我錯過了什麼，或者在這種情況下使用foldr更好嗎？

來源

2016-05-04 dimid

這可能是因爲作者不關心性能，而是關於這裏的模塊（？）... – Carsten

有關各種摺疊之間差異的更多詳細信息：https：//wiki.haskell.org/Foldr_Foldl_Foldl' – ErikR

@ ErikR。謝謝，我讀過維基，AFAIU，'foldl'幾乎從未使用過。 – dimid

我錯過了什麼，或者在這種情況下使用foldr更好嗎？

不，你沒有遺漏任何東西，你的分析是正確的; foldl這裏不是正確的工具，甚至foldl'是可疑的;當前的任務固然會從懶惰中受益，因此應使用foldr。

來源

2016-05-04 10:28:01

謝謝，在「所以foldl應該使用。」，你的意思是'foldr'？ – dimid

當然......：] –

在haskell中使用foldr進行搜索而不是foldl

回答

相關問題