{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

{-|
Module      : Data.Matroid.Uniform
Description : 
Copyright   : (c) Immanuel Albrecht, 2020-202x
License     : BSD-3
Maintainer  : mail@immanuel-albrecht.de
Stability   : experimental
Portability : POSIX

This module provides implementations of uniform matroids.

-}

module Data.Matroid.Uniform
    (
      UniformMatroid
     , uniformOn
     , uniform
     , FreeMatroid
     , freeOn
    ) where

import Data.Set (Set)
import qualified Data.Set as S

import Data.Matroid.Typeclass

-- | data type representing a uniform matroid over a given ground set
data UniformMatroid a = U -- ^ uniform matroid constructor
                        (Set a) -- ^ ground set of the uniform matroid
                        Int -- ^ rank of the uniform matroid (provided that groundset is big enough), must be >= 0.   
                    deriving (UniformMatroid a -> UniformMatroid a -> Bool
(UniformMatroid a -> UniformMatroid a -> Bool)
-> (UniformMatroid a -> UniformMatroid a -> Bool)
-> Eq (UniformMatroid a)
forall a. Eq a => UniformMatroid a -> UniformMatroid a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: UniformMatroid a -> UniformMatroid a -> Bool
$c/= :: forall a. Eq a => UniformMatroid a -> UniformMatroid a -> Bool
== :: UniformMatroid a -> UniformMatroid a -> Bool
$c== :: forall a. Eq a => UniformMatroid a -> UniformMatroid a -> Bool
Eq, Eq (UniformMatroid a)
Eq (UniformMatroid a)
-> (UniformMatroid a -> UniformMatroid a -> Ordering)
-> (UniformMatroid a -> UniformMatroid a -> Bool)
-> (UniformMatroid a -> UniformMatroid a -> Bool)
-> (UniformMatroid a -> UniformMatroid a -> Bool)
-> (UniformMatroid a -> UniformMatroid a -> Bool)
-> (UniformMatroid a -> UniformMatroid a -> UniformMatroid a)
-> (UniformMatroid a -> UniformMatroid a -> UniformMatroid a)
-> Ord (UniformMatroid a)
UniformMatroid a -> UniformMatroid a -> Bool
UniformMatroid a -> UniformMatroid a -> Ordering
UniformMatroid a -> UniformMatroid a -> UniformMatroid a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (UniformMatroid a)
forall a. Ord a => UniformMatroid a -> UniformMatroid a -> Bool
forall a. Ord a => UniformMatroid a -> UniformMatroid a -> Ordering
forall a.
Ord a =>
UniformMatroid a -> UniformMatroid a -> UniformMatroid a
min :: UniformMatroid a -> UniformMatroid a -> UniformMatroid a
$cmin :: forall a.
Ord a =>
UniformMatroid a -> UniformMatroid a -> UniformMatroid a
max :: UniformMatroid a -> UniformMatroid a -> UniformMatroid a
$cmax :: forall a.
Ord a =>
UniformMatroid a -> UniformMatroid a -> UniformMatroid a
>= :: UniformMatroid a -> UniformMatroid a -> Bool
$c>= :: forall a. Ord a => UniformMatroid a -> UniformMatroid a -> Bool
> :: UniformMatroid a -> UniformMatroid a -> Bool
$c> :: forall a. Ord a => UniformMatroid a -> UniformMatroid a -> Bool
<= :: UniformMatroid a -> UniformMatroid a -> Bool
$c<= :: forall a. Ord a => UniformMatroid a -> UniformMatroid a -> Bool
< :: UniformMatroid a -> UniformMatroid a -> Bool
$c< :: forall a. Ord a => UniformMatroid a -> UniformMatroid a -> Bool
compare :: UniformMatroid a -> UniformMatroid a -> Ordering
$ccompare :: forall a. Ord a => UniformMatroid a -> UniformMatroid a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (UniformMatroid a)
Ord)
                    
instance Show a => Show (UniformMatroid a) where
  show :: UniformMatroid a -> String
show (U Set a
e Int
r) = String
"uniformOn (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Set a -> String
forall a. Show a => a -> String
show Set a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
r
                    
instance (Ord a, Show a) => Matroid UniformMatroid a where
    groundset :: UniformMatroid a -> Set a
groundset (U Set a
e Int
_) = Set a
e
    rk :: UniformMatroid a -> Set a -> Int
rk (U Set a
_ Int
r) Set a
x = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
r (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Set a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Set a
x 
    indep :: UniformMatroid a -> Set a -> Bool
indep (U Set a
_ Int
r) Set a
x = Set a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Set a
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
r 
    basis :: UniformMatroid a -> Set a -> Set a
basis (U Set a
_ Int
r) = Int -> Set a -> Set a
forall a. Int -> Set a -> Set a
S.take Int
r 
    cl :: UniformMatroid a -> Set a -> Set a
cl (U Set a
e Int
r) Set a
x
      | Set a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Set a
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r = Set a
x 
      | Bool
otherwise = Set a
e

-- | returns a uniform matroid on the intergers from 1..n of rank r
uniform :: 
 Int -- ^ size of the uniform matroid (number of edges, n)
 -> Int -- ^ rank of the uniform matroid (r)
 -> UniformMatroid Int
uniform :: Int -> Int -> UniformMatroid Int
uniform Int
n Int
r
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = String -> UniformMatroid Int
forall a. HasCallStack => String -> a
error String
"The cardinality of a matroid must be non-negative."
  | Bool
otherwise = Set Int -> Int -> UniformMatroid Int
forall a. Ord a => Set a -> Int -> UniformMatroid a
uniformOn ([Int] -> Set Int
forall a. Ord a => [a] -> Set a
S.fromList [Int
1..Int
n]) Int
r

-- | returns a uniform matroid on a given ground set of rank r
uniformOn :: Ord a => 
 Set a -- ^ ground set of the uniform matroid
 -> Int -- ^ rank of the uniform matroid (r)
 -> UniformMatroid a
uniformOn :: Set a -> Int -> UniformMatroid a
uniformOn Set a
e Int
r
  | Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = String -> UniformMatroid a
forall a. HasCallStack => String -> a
error String
"The rank of a matroid must be non-negative."
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r = String -> UniformMatroid a
forall a. HasCallStack => String -> a
error String
"The cardinality of the groundset of the matroid must be at least its rank."
  | Bool
otherwise = Set a -> Int -> UniformMatroid a
forall a. Set a -> Int -> UniformMatroid a
U Set a
e Int
r
  where n :: Int
n = Set a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Set a
e

-- | data type that represents a free matroid over a given set (free matroids are of course uniform)
data FreeMatroid a = Free (Set a) -- ^ ground set
                   deriving (FreeMatroid a -> FreeMatroid a -> Bool
(FreeMatroid a -> FreeMatroid a -> Bool)
-> (FreeMatroid a -> FreeMatroid a -> Bool) -> Eq (FreeMatroid a)
forall a. Eq a => FreeMatroid a -> FreeMatroid a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FreeMatroid a -> FreeMatroid a -> Bool
$c/= :: forall a. Eq a => FreeMatroid a -> FreeMatroid a -> Bool
== :: FreeMatroid a -> FreeMatroid a -> Bool
$c== :: forall a. Eq a => FreeMatroid a -> FreeMatroid a -> Bool
Eq, Eq (FreeMatroid a)
Eq (FreeMatroid a)
-> (FreeMatroid a -> FreeMatroid a -> Ordering)
-> (FreeMatroid a -> FreeMatroid a -> Bool)
-> (FreeMatroid a -> FreeMatroid a -> Bool)
-> (FreeMatroid a -> FreeMatroid a -> Bool)
-> (FreeMatroid a -> FreeMatroid a -> Bool)
-> (FreeMatroid a -> FreeMatroid a -> FreeMatroid a)
-> (FreeMatroid a -> FreeMatroid a -> FreeMatroid a)
-> Ord (FreeMatroid a)
FreeMatroid a -> FreeMatroid a -> Bool
FreeMatroid a -> FreeMatroid a -> Ordering
FreeMatroid a -> FreeMatroid a -> FreeMatroid a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (FreeMatroid a)
forall a. Ord a => FreeMatroid a -> FreeMatroid a -> Bool
forall a. Ord a => FreeMatroid a -> FreeMatroid a -> Ordering
forall a. Ord a => FreeMatroid a -> FreeMatroid a -> FreeMatroid a
min :: FreeMatroid a -> FreeMatroid a -> FreeMatroid a
$cmin :: forall a. Ord a => FreeMatroid a -> FreeMatroid a -> FreeMatroid a
max :: FreeMatroid a -> FreeMatroid a -> FreeMatroid a
$cmax :: forall a. Ord a => FreeMatroid a -> FreeMatroid a -> FreeMatroid a
>= :: FreeMatroid a -> FreeMatroid a -> Bool
$c>= :: forall a. Ord a => FreeMatroid a -> FreeMatroid a -> Bool
> :: FreeMatroid a -> FreeMatroid a -> Bool
$c> :: forall a. Ord a => FreeMatroid a -> FreeMatroid a -> Bool
<= :: FreeMatroid a -> FreeMatroid a -> Bool
$c<= :: forall a. Ord a => FreeMatroid a -> FreeMatroid a -> Bool
< :: FreeMatroid a -> FreeMatroid a -> Bool
$c< :: forall a. Ord a => FreeMatroid a -> FreeMatroid a -> Bool
compare :: FreeMatroid a -> FreeMatroid a -> Ordering
$ccompare :: forall a. Ord a => FreeMatroid a -> FreeMatroid a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (FreeMatroid a)
Ord)
                   
instance (Ord a, Show a) => Matroid FreeMatroid a where
  groundset :: FreeMatroid a -> Set a
groundset (Free Set a
e) = Set a
e
  rk :: FreeMatroid a -> Set a -> Int
rk FreeMatroid a
_ = Set a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length
  indep :: FreeMatroid a -> Set a -> Bool
indep FreeMatroid a
_ Set a
_ = Bool
True
  basis :: FreeMatroid a -> Set a -> Set a
basis FreeMatroid a
_ = Set a -> Set a
forall a. a -> a
id
  cl :: FreeMatroid a -> Set a -> Set a
cl FreeMatroid a
_ = Set a -> Set a
forall a. a -> a
id
  
instance Show a => Show (FreeMatroid a) where
  show :: FreeMatroid a -> String
show (Free Set a
e) = String
"freeOn (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Set a -> String
forall a. Show a => a -> String
show Set a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
  
-- | returns a free matroid on a given ground set (where every subset of the groundset is independent)
freeOn :: Ord a => 
 Set a -- ^ ground set of the free matroid
 -> FreeMatroid a
freeOn :: Set a -> FreeMatroid a
freeOn = Set a -> FreeMatroid a
forall a. Set a -> FreeMatroid a
Free