Existe-t-il un moyen plus propre et plus élégant pour écrire cette fonction LCM?

Question

Je commence juste avec Haskell et ai martelé cet algo récursif simple pour trouver le LCM pour chaque nombre dans une liste. Cela fonctionne, mais c'est en désordre et j'espérais un examen par les pairs sur la façon de le rendre plus élégant, lisible et Haskell-y.

lcms list 
    | length list > 1 = lcms (lcm (head list) (head (tail list)):(tail (tail list))) 
    | otherwise = list 

Alors qui prend une liste et fait LCM des deux premiers éléments, prepends ensuite à la liste moins ces deux éléments. Fondamentalement, le psudocode que je vais pour est comme ceci:

lcms [a,b,c] = lcm (a, (lcm (b, c)) 

Des suggestions, quelqu'un? Je suis impatient de m'améliorer chez Haskell et d'écrire des choses que les gens peuvent réellement lire. Les conseils d'efficacité sont les bienvenus aussi!

Merci à tous!

Answer 1

Il est un pli:

import Data.List 

lcms :: [Int] -> Int 
lcms xs = foldl' lcm 1 xs 

où lcm calculer le PPCM de seulement deux numéros:

lcm :: Int -> Int -> Int 

Answer 2

Vous pouvez écrire avec presque la syntaxe que vous suggérez, ainsi:

lcms (a:b:c) = lcms (lcm a b:c) 
lcms list = list 

Je trouve la deuxième clause un peu étrange, mais pas terrible: elle gère gracieusement les listes vides, Bien que renvoyer une liste quand vous savez que vous retournerez au plus un élément pourrait être vu par certains hasochistes comme étant un peu imprécis avec vos types. Vous pouvez également envisager d'utiliser Maybe, le type d'élément canonique 0 ou 1:

lcms (a:b:c) = lcms (lcm a b:c) 
lcms [answer] = Just answer 
lcms []  = Nothing 

Un autre bon choix serait d'identifier un cas de base sain d'esprit. Pour les opérations binaires, l'unité de l'opération est généralement un bon choix, donc pour lcm, je choisirais 1, ainsi:

lcms (a:b:c) = lcms (lcm a b:c) 
lcms [answer] = answer 
lcms []  = 1 

En général, on essaie d'éviter la récursivité explicite lorsque cela est possible; l'autre réponse montre comment faire ce pas. Dans ce cas, il y a une transformation intermédiaire qui rend les cas de base légèrement plus esthétiques: au lieu de garder votre accumulateur en tête de liste - ce qui ne fonctionne qu'incidemment parce que votre accumulateur est du même type que les éléments de la liste - peut rendre l'accumulation plus explicite ou moins. Ainsi, l'un de ces:

lcms (x:xs) = lcm x (lcm xs) 
lcms []  = 1 

-- OR 

lcms = go 1 where 
    go acc (x:xs) = go (lcm acc x) xs 
    go acc []  = acc 

Ces deux implémentations correspondent à choisir foldr ou foldl pour éliminer la récursion explicite; foldl' serait similaire à la seconde, mais avec un seq supplémentaire:

lcms = go 1 where 
    go acc (x:xs) = let acc' = lcm acc x in acc' `seq` go acc' xs 
    go acc []  = acc