{- |
Description: Greatest common divisor
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P32" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P32 (myGCD) where

-- | Determine the greatest common divisor of two positive integer numbers.
-- Use [Euclid's algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm).
myGCD :: Integral a => a -> a -> a
myGCD :: forall a. Integral a => a -> a -> a
myGCD a
a a
b
  | a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0    = a
forall a. HasCallStack => a
undefined
  | a
b a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0    = a
forall a. HasCallStack => a
undefined
  | a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0     = a -> a -> a
forall a. Integral a => a -> a -> a
myGCD (-a
a) a
b
  | a
b a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0     = a -> a -> a
forall a. Integral a => a -> a -> a
myGCD a
a (-a
b)
  | a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
b     = a -> a -> a
forall a. Integral a => a -> a -> a
positiveGcd a
b a
a
  | Bool
otherwise = a -> a -> a
forall a. Integral a => a -> a -> a
positiveGcd a
a a
b
  where positiveGcd :: t -> t -> t
positiveGcd t
x t
y
          | t
y t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0    = t
x
          | Bool
otherwise = t -> t -> t
positiveGcd t
y (t
x t -> t -> t
forall a. Integral a => a -> a -> a
`mod` t
y)