Home > Net >  Manual gcd function in Haskell using pattern matching
Manual gcd function in Haskell using pattern matching

Time:03-01


Haskell beginner here! I'm solving a practice problem where I'm trying to make a manual gcd function using the pattern matching concept so far I've tried the following:

myGcdPM :: Int -> Int -> Int
myGcdPM x 0 = x
myGcdPM x y = myGcdPM y (mod x y)

The code seems to work but I'm trying to understand if this is a proper PM and a valid solution?

CodePudding user response:

If you look up the source of the standard implementation (if you didn't know where to find that: ask Hoogle), you'll find that it's almost the same as yours:

gcd x y         =  gcd' (abs x) (abs y)
                   where gcd' a 0  =  a
                         gcd' a b  =  gcd' b (a `rem` b)

Well, the definition of interest is really gcd':

gcd' a 0  =  a
gcd' a b  =  gcd' b (a `rem` b)

The only difference to yours is that it uses rem instead of mod (but on positive inputs these behave the same) and that it writes this in infix notation (a `rem` b is the same as rem a b).

Then, gcd x y = gcd' (abs x) (abs y) just wraps the whole thing, ensuring that the inputs are nonnegative.

  • Related