Combinaison de deux listes de compréhension Haskell

Question

J'essaye de calculer le premier nombre de triangle avec 501 divisorsin Haskell. J'ai déjà fait deux compréhensions de liste, une énumérant tous les nombres de triangle et une énumérant tous les diviseurs d'un nombre donné. Maintenant, je veux faire une grande liste avec toutes les diviseurs de valeurs de chaque numéro de triangle. (par exemple [[1], [1,3], [1,2,3,6], [1,2,5,10] etc.)

Comment puis-je utiliser ma liste triangleNumbers dans mon liste des diviseurs? Mon code est ci-dessous.

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

Tout d'abord, votre triangleNumbers est un peu bizarre: il contient Fractional s, au lieu de Integrals s. Cela rend plus difficile d'effectuer des calculs de division précis. Donc, nous ferions mieux de modifier ceci:

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

Notez que nous pouvons écrire l'expression dans la tête de la compréhension de la liste. Nous utilisons également div sur / puisque div est une division entière. Nous savons avec certitude que nous ne perdrons pas de données en effectuant une division entière, puisque a ou a+1 est pair, et la multiplication d'un nombre avec un nombre pair est toujours pair. Cela résulte dans la liste suivante:

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

Maintenant, nous voulons une fonction qui mappe des nombres sur les diviseurs. Nous pouvons faire une fonction générique:

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

Maintenant, nous pouvons utiliser map, pour mapper une liste de numéros à une liste de listes où chaque liste contient les diviseurs du nombre initial. Alors:

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]] 

On peut cependant aussi donner la map divisors la (liste infinie) de triangleNumbers. Par exemple, pour la première 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]] 

Maintenant, nous ne devons filtrer les chiffres qui ont 501 ou plusieurs éléments. Nous pouvons le faire en vérifiant que si nous avons drop 500 éléments, nous avons toujours une liste qui contient au moins un élément. Donc, avec:

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

Alors maintenant, nous pouvons filter tous les éléments où le hasAtLeastLengh 501 (divisors x) pour un certain nombre x. Cela produira donc la liste de tous ces chiffres:

filter (hasAtLeastLength 501 . divisors) triangleNumbers 

Cela produira une liste infinie de tous les triangleNumbers qui ont au moins 501 diviseurs. Nous pouvons utiliser head pour finalement obtenir le premier élément:

head $ filter (hasAtLeastLengh 501 . divisors) triangleNumbers 

Cela prend beaucoup de temps. Le code fonctionne cependant assez rapidement si nous travaillons avec 10 diviseurs:

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,... 

ce qui signifie qu'il produit une réponse. Cela signifie cependant que vous devrez trouver quelque chose de plus intelligent que de simplement énumérer.