import Data.List

{-

Try the following in GHCi:

  printEuclid 3042 4485
  
and

  printPulverizer 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 a b = takeUntil done (iterate step (a,b))
 where
  -- we are done when one side is 0;
  -- the other side will be the gcd
  done (a,b) = a == 0 || b == 0

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

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

----------------------------------------------------------------
-- Pulverizer (Bezout's method)

-- This function generates the table you compute when you
-- calculate the Pulverizer / 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.

pulverizer :: Integer -> Integer -> [(Integer,Integer,Integer,Integer,Integer,Integer)]
pulverizer a b = takeUntil done (iterate step (1,0,a,b,0,1))
 where
  -- we could compute this using Euclid's method as well
  d = gcd a b
 
  -- 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 (_,_,a,b,_,_) = a == d || b == d

  -- we subtract the smaller value from the larger value,
  -- and also subtract the respective (u,v)-pair from each other
  step (u1,v1,a,b,u2,v2)
    | a <= b    = (u1    , v1    , a   , b-a , u2-u1 , v2-v1)
    | otherwise = (u1-u2 , v1-v2 , a-b , b   , u2    , v2   )

printPulverizer :: Integer -> Integer -> IO ()
printPulverizer a b =
  do printTable ["u","v","a","b","u","v"]
                [ [u,v,a,b,u',v'] | (u,v,a,b,u',v') <- uvabuvs ]
     putStrLn ("So, " ++ show a ++ "u + " ++ show b ++ "v = " ++ show d
                      ++ ", when u=" ++ show u ++ " and v=" ++ show v)
 where
  uvabuvs           = pulverizer a b
  (u1,v1,p,q,u2,v2) = last uvabuvs 
  d                 = gcd p q
  (u,v)             = if p == 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