haskell中的無限列表與fold *結合*不會計算

Question

假設我想要得到指數爲n的所有primepowers的已分類無限列表。

我有一個函數來合併兩個排序列表和一個函數，讓我素數。

merge :: Ord t => [t] -> [t] -> [t] 
merge (x:xs) (y:ys) 
    | (x <= y) = x : merge xs (y:ys) 
    | otherwise = y : merge (x:xs) ys 
merge xs [] = xs 
merge [] ys = ys 

primes :: [Integer] 
primes = sieve [2..] 
    where 
     sieve [] = [] 
     sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) 

我有listOfPrimepowers函數的兩個版本：

primepowers :: Integer -> [Integer] 
primepowers n = foldr (merge) [] (listOfPrimepowers n)  

-- terminating 
listOfPrimepowers' n = map(\x -> (map(\y -> y^x) primes)) [1..n] 

-- non terminating  
listOfPrimepowers'' n = map(\x -> (map(\y -> x^y) [1..n])) primes 

提供一個正確的結果，另一個沒有。唯一的區別在於，第一個版本以[[2,3,5,7, ...],[4,9,25,...]]的方式映射了primepowers，第二個版本映射了像[[2,4,8],[3,9,27],[5,25,125], ...]這樣的primepowers。你看，無窮大在列表中的另一層。

你有解釋爲什麼第二個函數不會產生任何輸出嗎？

Answer 1

它是由具有貫穿所有列表看foldr merge找到的最小元素在其中一個名單的頭上。如果給予foldr merge有限列表的一個無限列表，foldr merge永遠不能計算列表的第一個元素 - 它會繼續查找列表中其餘列表的最小元素，然後才能將其與第一個元素進行比較列表 - 2。另一方面，如果foldr merge被給定了無限列表的有限列表，foldr merge可以確定合併列表的第一個元素，然後轉到下一個元素。這樣，您可以在第一種情況下生成任意數量的元素，但在第二種情況下不能生成任意數量的元素。

---

讓我們擴展foldr merge []：

foldr merge [] (xs0:xs1:xs2:...:[]) = 
merge xs0 (merge xs1 (merge xs2 (merge xs3 ... []))) 

顯然，如果(xs0:xs1:xs2:...:[])是無限的，在 「嵌套」 調用合併將形成一個無限鏈。但是，哈斯克爾是「懶惰」呢？ primes也是根據其本身來定義的，但它會產生輸出嗎？那麼，實際上有一個規則foldr：它只有在傳遞給foldr的函數在第二個參數中不嚴格時纔可以產生無限列表的輸出 - 即有時它可以產生輸出，而不必評估foldr的結果，列表。

的merge圖案相匹配的第二個參數 - 單獨可引起非終止 - 並使用嚴格功能<=，所以merge是在第二個參數嚴格，與無限鏈將必須評估的每一個所述第一元件在頂級merge之前的列表可以產生任何結果。

因爲merge是嚴格的，因爲merge是關聯的，你可以 - 也應該 - 使用foldl'代替foldr合併無限列表的有限列表。

Answer 2

你的功能亦不會終止

的第一件事是，primes是一個無限的列表。這意味着該項目的理解在其懶惰的評價

住的第一個功能

primepowers :: Integer -> [Integer] 
primepowers n = foldr (merge) [] (listOfPrimepowers n)  

listOfPrimepowers n = map (\x -> (map (\y -> y^x) primes)) [1..n] 

不會因爲終止。即使外部地圖適用於有限列表[1..n]，每個\x消耗的內部map適用於無限列表primes。

第二個功能

primepowers :: Integer -> [Integer] 
primepowers n = foldl (merge) [] (listOfPrimepowers n) 

listOfPrimepowers n = map(\x -> (map(\y -> x^y) [1..n])) primes 

不會終止，因爲外部map直接申請一個無限名單上primes

Answer 3

第二個版本不會給你任何輸出，因爲輸入是無限列表。如果您仔細考慮，foldr merge []會從列表中創建一個排序的列表，因此結果列表的頭元素將是列表的所有頭元素的最小值。自然地，獲取無限列表的最小值是非終止的，所以當結果的第一個元素變爲可用時，該函數甚至沒有達到該點。

Answer 4

你可以很容易地使兩個變體的工作。涉及的技術值得了解。

您的代碼就相當於

primepowers n = 
    foldr merge [] 
     -- terminating: 
-- [[p^k | p <- primes] | k <- [1..n]] -- n infinite lists 

     -- non terminating: 
     [[p^k | k <- [1..n]] | p <- primes] -- infinite list of n-length lists 

"Naturally, taking the minimum of an infinite list is non-terminating"是真理，只有真理，但不是全部的真相，在這裏。

在這裏，無限列表primes是按照其元素的升序排序。因此，列表[p^k | k <- [1..n]]的頭部被排序並且增加，並且列表本身也被排序並且增加。 僅根據這一知識，我們馬上可以產生合併流的頭元素—最小的所有名單的頭無限名單—在O（1）時間，而無需實際檢查它們中的任何，除了第一個（本身就是答案）。從而

你的問題就解決了通過使用以下函數代替merge，在foldr表達：

imerge (x:xs) ys = x : merge xs ys 

（如在the article by Melissa O'Neill在代碼視爲由理查德伯德）。現在兩種變體都可以工作。 imerge在其第二個參數中是非嚴格的，並且自然與foldr一起使用，即使是有限列表也是如此。

使用foldl而不是foldr顯然與第二個變體不符，因爲無限列表上的foldl不是終止的。

使用foldl與第一個變體雖然可能（因爲列表本身是有限的），但在這裏是次優的：它會將更頻繁產生的流放置在整個合併鏈的底部，即它會運行得更慢比使用foldr的那個要好。請參閱：folds on wikipedia