module Math.RootLoci.Misc.Common where
import Data.List
import Data.Monoid
import Data.Ratio
import Control.Monad
import Math.Combinat.Numbers
import Math.Combinat.Sign
import Math.Combinat.Partitions.Integer
import Math.Combinat.Partitions.Set
import Math.Combinat.Sets
import qualified Data.Map.Strict as Map
import Data.Map (Map)
data Pair a
= Pair a a
deriving (Eq,Ord,Show,Functor)
unique :: Ord a => [a] -> [a]
unique = map head . group . sort
count :: Ord b => [b] -> Map b Integer
count = histogram
histogram :: Ord b => [b] -> Map b Integer
histogram xs = foldl' f Map.empty xs where
f old x = Map.insertWith (+) x 1 old
deleteLookup :: Ord a => a -> Map a b -> (Maybe b, Map a b)
deleteLookup k table = (Map.lookup k table, Map.delete k table)
unsafeDeleteLookup :: Ord a => a -> Map a b -> (b, Map a b)
unsafeDeleteLookup k table = (fromJust (Map.lookup k table), Map.delete k table) where
fromJust mb = case mb of
Just y -> y
Nothing -> error "unsafeDeleteLookup: key not found"
aut :: Partition -> Integer
aut part = product $ map factorial es where
es = map snd $ toExponentialForm part
defaultSetPartition :: Partition -> SetPartition
defaultSetPartition = SetPartition . linearIndices
linearIndices :: Partition -> [[Int]]
linearIndices (Partition ps) = go 0 ps where
go _ [] = []
go !k (a:as) = [k+1..k+a] : go (k+a) as
class IsSigned a where
signOf :: a -> Maybe Sign
signOfNum :: (Ord a, Num a) => a -> Maybe Sign
signOfNum x = case compare x 0 of
LT -> Just Minus
GT -> Just Plus
EQ -> Nothing
instance IsSigned Int where signOf = signOfNum
instance IsSigned Integer where signOf = signOfNum
instance IsSigned Rational where signOf = signOfNum
fromRat :: Rational -> Integer
fromRat r = case denominator r of
1 -> numerator r
_ -> error "fromRat: not an integer"
safeDiv :: Integer -> Integer -> Integer
safeDiv a b = case divMod a b of
(q,0) -> q
(q,r) -> error $ "saveDiv: " ++ show a ++ " = " ++ show b ++ " * " ++ show q ++ " + " ++ show r
chooseN1 :: [a] -> [[a]]
chooseN1 = go where
go (x:xs) = xs : map (x:) (go xs)
go [] = []
symPolyNum :: Num a => Int -> [a] -> a
symPolyNum k xs = sum' (map prod' $ choose k xs) where
sum' = foldl' (+) 0
prod' = foldl' (*) 1