如何的每一個元素與另一個列表中的每個元素在Haskell劃分在一個列表

Question

假設我有一個無限列表A = [1..]我想每個元素在A在列表B = [1..10]所有元素劃分如果在列表A任何元素除盡所有B中的元素需要打印。 我需要繼續這個，直到我得到10個這樣的數字。

下嘗試沒有工作：

print(minimum([x | x <- [1..], y <- [1..10], rem x y == 0])) 

Answer 1

你嘗試

您寫道：

print(minimum([x | x <- [1..], y <- [1..10], rem x y == 0])) 

現在，這不會有以下幾個原因工作：

1. 它會將x添加到列表理解列表中，因爲有任何元素y在[1..10]中除以x。此外，對於任何此類y，我們將一次添加x。所以給定x是6，它會將它添加三次四次，因爲6可以被1,2,3和6除盡;
2. 結果將是一個無限列表，因此無法計算該列表的最小值。這是因爲Haskell不知道列表已經被排序，因此最小值只是第一個元素。你可以採取第一個元素head;
3. minimum只會產生一個元素，但你要第10

暴力方法

首先，我們可以使用列表解析生成所有這些數字（任意名單as和bs）：

divide_all as bs = [a | a <- as, all ((0 ==) . mod a) bs] 

所以這裏的名單理解迭代as環節都分配給a。接下來我們有一個過濾器all ((0 ==) . mod a) bs，這是一個緊湊的形式all (\b -> mod a b == 0) bs。因此它檢查是否b中的所有成員bs,mod a b == 0（因此a可由b分割）。如果過濾器得到滿足，則我們將a（在列表理解的頭部）添加到結果中。請注意，這樣的列表是懶散地構建的，因此as具有無限數量的元素的事實不是問題。

現在我們可以使用take :: Int -> [a] -> [a]採取這些數字的第一個10，從而打印這些：

mapM_ print (take 10 $ divide_all [1..] [1..10]) 

它打印：

Prelude> mapM_ print (take 10 $ divide_all [1..] [1..10]) 
2520 
5040 
7560 
10080 
12600 
15120 
17640 
20160 
22680 
25200 

最小公倍數

上述方法效率不高：對於a的每個元素，我們需要檢查它是否可以用b的每個元素進行分割。我的機器用了2.16秒來計算這個列表的第1000個元素，用了10.21秒找到第5000個元素。

可加快我們的最後一個，通過計算最小公倍數（LCM）的b所有的元素，並檢查是否一個數是由LCM可分：所以現在

divide_all as bs = [a | a <- as, mod a lcmb == 0] -- optimized version 
    where lcmb = foldr1 lcm bs 

我們只需要執行一次支票。現在計算第1000個元素需要0.95秒，計算第5000個元素需要4.54秒。

如果as = [1..]

如果as被稱爲是[1..]我們可以顯着提升該代碼，因爲我們知道，a的元素是lcmb倍數。因此，我們可以放下as參數，並使用：

divide_all bs = [lcmb*a | a <- [1..]] -- optimized version 
    where lcmb = foldr1 lcm bs 

現在計算的第1000個元素需要0.01秒，並計算第5000元0.03秒。但當然這隻有在假設的情況下才有效。

Answer 2

let divcheck = (take 10 .) . filter . flip (all . ((0 ==) .) . mod) 

divcheck [1..10] [1..] 
-- [2520,5040,7560,10080,12600,15120,17640,20160,22680,25200] 

divcheck [1,2,3] [1..] 
-- [6,12,18,24,30,36,42,48,54,60]