結合兩個列表解析Haskell

Question

我想用501 divisorsin Haskell計算第一個三角形數字。我已經提出了兩個列表解析，其中一個列出了所有三角形數字，另一個列出了給定數字的所有除數。現在我想用每個三角形數字的所有值除數製作一個大列表。 （例如[[1]，[1,3]，[1,2,3,6]，[1,2,5,10]等）。

我怎樣才能使用我的triangleNumbers列表除數列表？ 我的代碼如下。

triangleNumbers = [t | a <- [0..], let t = a*(a+1)/2] 
divisors triangleNumbers = [d | d <- [1..triangleNumbers], triangleNumbers 
`mod` d == 0] 
numDivisors = takeWhile(<501) length . divisors 
answer = divisors !! numDivisors 

Answer 1

首先，你triangleNumbers是有點怪異：它包含Fractional S，而不是Integrals秒。這使得執行精確的分割計算更麻煩。所以我們最好修改此：

triangleNumbers = [ div (a*(a+1)) 2 | a <- [0..]] 

請注意，我們可以在列表理解的頭寫的表達。因爲div是整數除法，所以我們也使用div而不是/。我們確實知道，我們不會因執行整數除法而丟失數據，因爲a或a+1是偶數，並且數字與偶數的乘法總是偶數。這會產生以下列表：

Prelude> take 10 triangleNumbers 
[0,1,3,6,10,15,21,28,36,45] 

現在我們需要一個映射除數的數字的函數。我們可以做一個通用的功能：

divisors x = [d | d <- [1..x], mod x d == 0] 

現在我們可以使用map，以數字列表映射到列表中的一個列表，其中每個列表包含原數的約數。所以：

Prelude> map divisors [1,2,3,5,8,13,21] 
[[1],[1,2],[1,3],[1,5],[1,2,4,8],[1,13],[1,3,7,21]] 

我們然而，也給出triangleNumbers的map divisors的（無限列表）。例如，對於第10 triangleNumbers：

Prelude> take 10 $ map divisors $ triangleNumbers 
[[],[1],[1,3],[1,2,3,6],[1,2,5,10],[1,3,5,15],[1,3,7,21],[1,2,4,7,14,28],[1,2,3,4,6,9,12,18,36],[1,3,5,9,15,45]] 

現在，我們只需要篩選有501元以上的數字。我們可以通過檢查如果我們drop 500元素來做到這一點，我們仍然有一個包含至少一個元素的列表。因此，與：

hasAtLeastLength :: Int -> [a] -> Bool 
hasAtLeastLength n = not . null . drop (n-1) 

所以，現在我們可以filter所有元素，其中hasAtLeastLengh 501 (divisors x)了許多x。因此，這將產生所有這些數字的列表：

filter (hasAtLeastLength 501 . divisors) triangleNumbers 

這將產生至少501個除數所有triangleNumbers的無限名單。我們可以用head最終獲得第一個元素：

head $ filter (hasAtLeastLengh 501 . divisors) triangleNumbers 

這需要大量的時間。代碼工作卻相當快，如果我們使用10個除數工作：

Prelude> filter (hasAtLeastLength 10 . divisors) triangleNumbers 
[120,210,276,300,378,496,528,630,666,780,820,990,1035,1128,1176,1275,1326,1485,1540,1596,1770,1830,1953,2016,2080,2145,2346,2415,2556,2628,2775,2850,2926,3003,3160,3240,3321,3486,3570,3828,3916,4005,4095,4186,4278,4560,4656,4851,4950,5050,5356,5460,5565,5778,5886,6105,6216,6328,6555,6670,6786,6903,7140,7260,7626,7750,7875,8001,8128,8256,8385,8646,8778,9045,9180,9316,9730,9870,10296,10440,10731,10878,11175,11325,11476,11628,11781,11935,12090,12246,12720,12880,13041,13203,13530,13695,14028,14196,14365,14535,14706,15225,15400,15576,16110,16290,16653,16836,17020,17205,17391,17578,17766,17955,18336,18528,18915,19110,19306,19503,19701,19900,20100,20706,20910,21321,21528,21736,21945,22155,22578,23220,23436,24090,24310,24531,24976,25200,25425,25878,26106,26565,26796,27028,27261,27495,27730,27966,28203,28680,28920,29403,29646,29890,30135,30381,30628,30876,31125,31626,31878,32385,32640,32896,33411,33670,33930,34191,34716,34980,35245,35511,35778,36315,36585,36856,37128,37401,37675,37950,38226,38781,39060,39340,40470,40755,41041,41328,41616,41905,42195,42486,43071,43365,43660,43956,44253,44850,45150,46056,46360,46665,46971,47278,47586,47895,48516,48828,49455,49770,50721,51040,51360,51681,52003,52326,52650,... 

，這意味着它會產生一個答案。這意味着你不得不拿出比簡單枚舉更聰明的東西。