import Data.List

{-

Try the following in GHCi:

  printEuclid 3042 4485
  
and

  printBezout 3042 4485

-}

----------------------------------------------------------------
-- Euclid's method

-- This function generates the table you compute when you
-- calculate the gcd using Euclid's method.

euclid :: Integer -> Integer -> [(Integer,Integer)]
euclid x y = takeUntil done (iterate step (x,y))
 where
  -- we are done when one side is 0;
  -- the other side will be the gcd
  done (x,y) = x == 0 || y == 0

  -- we subtract the smaller value from the larger value
  step (x,y)
    | x <= y    = (x,y-x)
    | otherwise = (x-y,y)

printEuclid :: Integer -> Integer -> IO ()
printEuclid x y =
  do printTable ["x","y"] [ [a,b] | (a,b) <- xys ]
     putStrLn ("So, gcd(" ++ show x ++ "," ++ show y ++") = " ++ show d)
 where
  xys   = euclid x y
  (a,b) = last xys  
  d     = if a == 0 then b else a

----------------------------------------------------------------
-- Bezout's method

-- This function generates the table you compute when you
-- calculate Bezout's identity.
-- The table has a lot in common with the table from Euclid;
-- if you do this by hand, first compute Euclid's table, and
-- then fill in the rest.

bezout :: Integer -> Integer -> [(Integer,Integer,Integer,Integer,Integer,Integer)]
bezout x y = takeUntil done (iterate step (1,0,x,y,0,1))
 where
  -- we could compute this using Euclid's method as well
  d = gcd x y
 
  -- we are done when one side is d (the gcd of x and y);
  -- the u and v on that side are the answer we are looking for
  done (_,_,x,y,_,_) = x == d || y == d

  -- we subtract the smaller value from the larger value,
  -- and also subtract the respective (u,v)-pair from each other
  step (u,v,x,y,u',v')
    | x <= y    = (u,   v,    x,   y-x, u'-u,v'-v)
    | otherwise = (u-u',v-v', x-y, y,   u',  v')

printBezout :: Integer -> Integer -> IO ()
printBezout x y =
  do printTable ["u","v","x","y","u","v"]
                [ [u,v,a,b,u',v'] | (u,v,a,b,u',v') <- uvxyuvs ]
     putStrLn ("So, " ++ show x ++ "u + " ++ show y ++ "v = " ++ show d
                      ++ ", when u=" ++ show u ++ " and v=" ++ show v)
 where
  uvxyuvs           = bezout x y
  (u1,v1,a,b,u2,v2) = last uvxyuvs 
  d                 = gcd x y
  (u,v)             = if a ==d then (u1,v1) else (u2,v2)

----------------------------------------------------------------
-- helper functions

-- like takeWhile, but returns one more element
takeUntil :: (a -> Bool) -> [a] -> [a]
takeUntil p [] = []
takeUntil p (x:xs)
  | p x        = [x]
  | otherwise  = x : takeUntil p xs

-- prints a nice table with headings and columns
printTable :: Show a => [String] -> [[a]] -> IO ()
printTable hs xss = putStr (unlines (map row tss))
 where
  tss     = hs : map (map show) xss
  n       = maximum (1 : [ length t | ts <- tss, t <- ts ])
  row     = concat . intersperse " | " . map align
  align t = replicate (n - length t) ' ' ++ t