GCF/LCM in Haskell

Question

I'm extremely new to Haskell.

Is there a simple way to find the GCF or LCM (Least Common Multiple) in Haskell?

Answer 1

By GCF, do you mean the greatest common factor, or greatest common divisor? That's gcd, avaliable from the prelude, as is lcm, the least common multiple.

Answer 2

I'm not sure what the LCF is but the GCF is a Haskell favorite. Using the Euclidean Algroithm you can really get a sense of how Haskell works. http://en.wikipedia.org/wiki/Euclidean_algorithm There is a great explanation of how the algorithm is set up here http://en.literateprograms.org/Euclidean_algorithm_(Haskell) .

This type of recursion is common in Haskell and it shows how expressive the language can be.

gcd a 0 = a
gcd a b = gcd b (a `mod` b)

This uses pattern matching on the arguments to say the greatest common factor of any number and 0 is the first number. If the numbers are both non-zero, then look for the greatest common factor of the second and the first mod the second. Eventually this will reach 0 in the second argument. This will trigger the first pattern and return the first argument which is the answer.

[EDIT]

The function should actually be:

gcd a 0 = a
gcd a b = b `seq` gcd b (a `mod` b) where

This will force the evaluation of the previous recursion step's (a mod b) and will prevent a huge thunk being built in memory if, say, you are GCDing 1243235452 and 6095689787662. Seq forces the argument into its "Weak Head Normal Form" or evaluates the outer most data structure of the argument.