{-# LANGUAGE DatatypeContexts #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE UndecidableSuperClasses #-}

import Data.List
import Data.Kind
import Control.Applicative

-- sorry
newtype (a x) => FuncOf a f x = FuncOf { getFuncOf :: f x }
                                deriving (Show, Functor, Applicative, Monad)

class Always a
instance Always a

class ConsFunctor a f | f -> a where
    fmapC :: (a x, a y) => (x -> y) -> f x -> f y

instance Functor f => ConsFunctor Always (FuncOf Always f) where
    fmapC = fmap

infixr 4 <*?>
class ConsFunctor a f => ConsApplicative a f | f -> a where
    {-# MINIMAL pureC, ((<*?>) | liftA2C) #-}
    pureC :: (a x) => x -> f x
    
    -- unfortunately these constraints ask too much
    -- I was able to reduce these to only
    --     (<*?>) :: (a x, a (x -> y)) => ...
    -- and liftA2C :: (a x, a y, a (y -> z)) -> ...
    -- but I could not get rid of a (x -> y) (and conversely a (y -> z))
    -- so ConsFunctor might be at fault here?
    
    (<*?>) :: (a x, a y, a (x -> y)) => f (x -> y) -> f x -> f y
    (<*?>) = liftA2C id

    liftA2C :: (a x, a y, a z, a (y -> z)) => (x -> y -> z) -> f x -> f y -> f z
    liftA2C f x = (<*?>) (fmapC f x)
    
instance Applicative f => ConsApplicative Always (FuncOf Always f) where
    pureC = pure
    (<*?>) = (<*>)
    liftA2C = liftA2

infixr 4 >>=?
class ConsApplicative a f => ConsMonad a f | f -> a where
    (>>=?) :: (a x, a y) => f x -> (x -> f y) -> f y

instance Monad f => ConsMonad Always (FuncOf Always f) where
    (>>=?) = (>>=)

-- example (though bad): invariance
newtype UniqList a = UniqList [a]
                     deriving (Show)

intoUniqList = UniqList . nub
mapUniqList f (UniqList l) = UniqList (nub $ map f l)

instance ConsFunctor Eq (FuncOf Eq UniqList) where
    fmapC f = FuncOf . mapUniqList f . getFuncOf

main = do
    -- putStrLn "input a list of integers\ne.g. [4,9,6,3,1,8,5,4,0,9,5]"
    -- a <- getLine
    let a = "[4,9,6,3,1,8,5,4,0,9,5]"
    -- putStrLn "input modulo\ne.g. 5"
    -- b <- getLine
    let b = "5"

    let a' = (FuncOf $ intoUniqList $ sort (read a)) :: FuncOf Eq UniqList Integer
    let n  = read b

    print $ fmapC (`mod` n) a'