하스켈 (Haskell) 두 목록 합치기 합치기

Question

하스켈 501의 첫 번째 삼각형 수를 계산하려고합니다. 나는 이미 두 개의 목록 내포를 만들었고 하나는 모든 삼각형 수를 나열하고 하나는 주어진 수의 모든 수를 표시합니다. 이제 각 삼각형 수의 모든 값 나누기로 하나의 큰 목록을 만들고 싶습니다. (예 : [[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의 대신 Integrals의이 포함되어 있습니다. 따라서 정확한 나눗셈 계산을 수행하는 것이 더욱 번거로 롭습니다. 그래서 우리는 더 나은이를 수정 : 우리는 지능형리스트의 머리에 표현을 쓸 수

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

참고. div을 / 이상으로 사용하면 div은 정수로 나뉩니다. a 또는 a+1이 짝수이고 짝수의 숫자가 항상 짝수이기 때문에 정수 나누기를 수행하여 데이터가 손실되지 않는다는 것을 알고 있습니다. 결과는 다음과 같습니다.

이제는 약수에 숫자를 매핑하는 기능이 필요합니다.

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 모든 요소 여기서 숫자 x에 대한 hasAtLeastLengh 501 (divisors 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,... 

즉 대답을 생성합니다. 이것은 단순히 열거하는 것보다 더 똑똑한 것을 생각해 내야한다는 것을 의미합니다.