Utils.hs

module Data.Integer.Presburger.Utils
  ( module Data.Integer.Presburger.Utils
  , module PP
  ) where

import Text.PrettyPrint.HughesPJ as PP




lcms :: Integral a => [a] -> a
lcms xs = foldr lcm 1 xs


groupEither :: [Either a b] -> ([a],[b])
groupEither xs = foldr cons ([],[]) xs
  where cons (Left a)  (as,bs) = (a:as,bs)
        cons (Right b) (as,bs) = (as,b:bs)

mapEither :: (a -> Either x y) -> [a] -> ([x],[y])
mapEither f xs = groupEither (map f xs)


-- | let (p,q,r) = extended_gcd x y
--   in (x * p + y * q = r)  &&  (gcd x y = r)
extended_gcd :: Integral a => a -> a -> (a,a,a)
extended_gcd arg1 arg2 = loop arg1 arg2 0 1 1 0
  where loop a b x lastx y lasty
          | b /= 0    = let (q,b') = divMod a b
                            x'     = lastx - q * x
                            y'     = lasty - q * y
                        in x' `seq` y' `seq` loop b b' x' x y' y
          | otherwise = (lastx,lasty,a)


-- We define: "d | a" as "exists y. d * y = a"
divides :: Integral a => a -> a -> Bool
0 `divides` 0 = True
0 `divides` _ = False
x `divides` y = mod y x == 0


class PP a where
  pp :: a -> Doc