{-# LANGUAGE MultiParamTypeClasses,FlexibleInstances #-}

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

This module provides the Matroid typeclass.

-}

module Data.Matroid.Typeclass where
  
import Data.Matroid.Ops

import qualified Data.Matroid.Typeclass.Defaults as D
    
import Data.Set (Set)
-- import qualified Data.Set as S

import Data.Matroid.Internal.Helpers
    
{-| 
    Typeclass that provides the full matroid interface.
    
    The type parameter @a@ is the type of the elements of the matroid,
    it is most commonly used in a @Set a@ type.
    
    In this typeclass, we assume that every set of matroid elements
    passed to any of the routines is actually a subset of (groundset m).
    Behaviour for other sets shall be considered undefined.
    
    In order to keep things DRY, the default implementations are fumbled through
    the (AMatroid a) instance definition below through wrapUp and setting the
    corresponding record value to Nothing.
     
-}
class (Ord a, Show a) => Matroid m a 
    where
    
    {--- I. The routines in this section are worth to look at in 
            your implementation of a Matroid instance ---}
            
    {-# MINIMAL groundset, (rk | indep | basis) #-}
    
    -- | The ground set of the matroid, its elements are usually called edges. This set is finite.
    groundset :: m a -> Set a
    
    -- | name of the matroid, may be used for show
    showName :: m a -> String
    showName m a
m = AMatroid a -> String
forall (m :: * -> *) a. Matroid m a => m a -> String
showName (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_showName :: Maybe String
w_showName = Maybe String
forall a. Maybe a
Nothing }
    
    -- | returns the rank of the set
    rk :: m a -- ^ the matroid 
      -> Set a -- ^ set of matroid elements
      -> Int
    rk m a
m = AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_rk :: Maybe (Set a -> Int)
w_rk = Maybe (Set a -> Int)
forall a. Maybe a
Nothing }
    
    -- | tests whether a given set is independent
    indep :: m a -- ^ the matroid 
      -> Set a -- ^ set of matroid elements
      -> Bool
    indep m a
m = AMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_indep :: Maybe (Set a -> Bool)
w_indep = Maybe (Set a -> Bool)
forall a. Maybe a
Nothing }
    
    -- | obtains an independent subset with maximal cardinality
    basis :: m a -- ^ the matroid
      -> Set a -- ^ set of matroid elements
      -> Set a
    basis m a
m = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_basis :: Maybe (Set a -> Set a)
w_basis = Maybe (Set a -> Set a)
forall a. Maybe a
Nothing }
                   
    -- | computes the closure of a given set
    cl :: m a -- ^ the matroid
      -> Set a -- ^ set of matroid elements 
      -> Set a
    cl m a
m = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_cl :: Maybe (Set a -> Set a)
w_cl = Maybe (Set a -> Set a)
forall a. Maybe a
Nothing }
               
    {--- II. We provide standard implementations of these operations, 
             but you probably want to roll your own,
             in order to improve performance ---}
             
    -- | returns this matroid as abstract matroid object
    abstract :: m a {- ^ matroid -} -> AMatroid a
    abstract m a
m = m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
wrapUp m a
m
    
    -- | returns the dual of this matroid as abstract matroid object
    dual :: m a {- ^ matroid -} -> AMatroid a
    dual m a
m = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_dual :: Maybe (AMatroid a)
w_dual = Maybe (AMatroid a)
forall a. Maybe a
Nothing }
             
    -- | returns the restricted matroid M|X as result of the unary matroid operation *|X
    restriction :: m a {- ^ the matroid -} -> Set a {- ^ restricts the ground set to this set-}
       -> AMatroid a
    restriction m a
m = AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
restriction (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_restriction :: Maybe (Set a -> AMatroid a)
w_restriction = Maybe (Set a -> AMatroid a)
forall a. Maybe a
Nothing }
    
    -- | returns the contracted matroid M.X as a result of the unary matroid operation *.X
    contraction :: m a {- ^ the matroid -} -> Set a {- ^ contracts the ground set onto this set -}
       -> AMatroid a
    contraction m a
m  = AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
contraction (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_contraction :: Maybe (Set a -> AMatroid a)
w_contraction = Maybe (Set a -> AMatroid a)
forall a. Maybe a
Nothing }
    
    {--- III. There is generally less to gain from implementing the following 
              routines in your own Matroid instances. ---}
    
    -- | returns the loops in the matroid
    loops :: m a {- ^ the matroid -} -> Set a
    loops m a
m = AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_loops :: Maybe (Set a)
w_loops = Maybe (Set a)
forall a. Maybe a
Nothing }
    
    -- | rank function of the dual matroid
    coRk :: m a {- ^ the matroid -} -> Set a {- ^ set of matroid elements -} -> Int
    coRk m a
m = AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_coRk :: Maybe (Set a -> Int)
w_coRk = Maybe (Set a -> Int)
forall a. Maybe a
Nothing }
       
    -- | returns the coloops in the matroid
    coloops :: m a {- ^ the matroid -} -> Set a
    coloops m a
m = AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
abstract m a
m) { w_coloops :: Maybe (Set a)
w_coloops = Maybe (Set a)
forall a. Maybe a
Nothing }


-- | takes an object of a type that implements the Matroid typeclass, and turns it into an AMatroid record.
wrapUp :: (Matroid m a) => m a -> AMatroid a
wrapUp :: m a -> AMatroid a
wrapUp m a
m = AMatroid Any
forall a. AMatroid a
wrappedMatroid {
  {--- I. ---}  
    w_groundset :: Set a
w_groundset = m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
  , w_showName :: Maybe String
w_showName = String -> Maybe String
forall a. a -> Maybe a
Just (String -> Maybe String) -> String -> Maybe String
forall a b. (a -> b) -> a -> b
$ String
"abstract $ " String -> String -> String
forall a. [a] -> [a] -> [a]
++ m a -> String
forall (m :: * -> *) a. Matroid m a => m a -> String
showName m a
m
  , w_rk :: Maybe (Set a -> Int)
w_rk = (Set a -> Int) -> Maybe (Set a -> Int)
forall a. a -> Maybe a
Just ((Set a -> Int) -> Maybe (Set a -> Int))
-> (Set a -> Int) -> Maybe (Set a -> Int)
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m
  , w_indep :: Maybe (Set a -> Bool)
w_indep = (Set a -> Bool) -> Maybe (Set a -> Bool)
forall a. a -> Maybe a
Just ((Set a -> Bool) -> Maybe (Set a -> Bool))
-> (Set a -> Bool) -> Maybe (Set a -> Bool)
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m
  , w_basis :: Maybe (Set a -> Set a)
w_basis = (Set a -> Set a) -> Maybe (Set a -> Set a)
forall a. a -> Maybe a
Just ((Set a -> Set a) -> Maybe (Set a -> Set a))
-> (Set a -> Set a) -> Maybe (Set a -> Set a)
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m
  , w_cl :: Maybe (Set a -> Set a)
w_cl = (Set a -> Set a) -> Maybe (Set a -> Set a)
forall a. a -> Maybe a
Just ((Set a -> Set a) -> Maybe (Set a -> Set a))
-> (Set a -> Set a) -> Maybe (Set a -> Set a)
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m
  {--- II. ---}
  , w_abstract :: Maybe (AMatroid a)
w_abstract = Maybe (AMatroid a)
forall a. Maybe a
Nothing -- abstract shall be idempotent
  , w_dual :: Maybe (AMatroid a)
w_dual = AMatroid a -> Maybe (AMatroid a)
forall a. a -> Maybe a
Just (AMatroid a -> Maybe (AMatroid a))
-> AMatroid a -> Maybe (AMatroid a)
forall a b. (a -> b) -> a -> b
$ m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m
  , w_restriction :: Maybe (Set a -> AMatroid a)
w_restriction = (Set a -> AMatroid a) -> Maybe (Set a -> AMatroid a)
forall a. a -> Maybe a
Just ((Set a -> AMatroid a) -> Maybe (Set a -> AMatroid a))
-> (Set a -> AMatroid a) -> Maybe (Set a -> AMatroid a)
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
restriction m a
m
  , w_contraction :: Maybe (Set a -> AMatroid a)
w_contraction = (Set a -> AMatroid a) -> Maybe (Set a -> AMatroid a)
forall a. a -> Maybe a
Just ((Set a -> AMatroid a) -> Maybe (Set a -> AMatroid a))
-> (Set a -> AMatroid a) -> Maybe (Set a -> AMatroid a)
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
contraction m a
m
  {--- III. ---}
  , w_loops :: Maybe (Set a)
w_loops = Set a -> Maybe (Set a)
forall a. a -> Maybe a
Just (Set a -> Maybe (Set a)) -> Set a -> Maybe (Set a)
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops m a
m
  , w_coRk :: Maybe (Set a -> Int)
w_coRk = (Set a -> Int) -> Maybe (Set a -> Int)
forall a. a -> Maybe a
Just ((Set a -> Int) -> Maybe (Set a -> Int))
-> (Set a -> Int) -> Maybe (Set a -> Int)
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk m a
m
  , w_coloops :: Maybe (Set a)
w_coloops = Set a -> Maybe (Set a)
forall a. a -> Maybe a
Just (Set a -> Maybe (Set a)) -> Set a -> Maybe (Set a)
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops m a
m
  
  }
                

  


-- | This instance contains the default implementations of the members of the Matroid typeclass.
instance (Ord a, Show a) => Matroid AMatroid a where
  {--- I. ---}                              --   vv. default Matroid implementations go here .vv
  groundset :: AMatroid a -> Set a
groundset = AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset
  showName :: AMatroid a -> String
showName AMatroid a
m = (AMatroid a -> Maybe String) -> AMatroid a -> String -> String
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe String
forall a. AMatroid a -> Maybe String
w_showName AMatroid a
m          (String -> String) -> String -> String
forall a b. (a -> b) -> a -> b
$ String
"Matroid instance"
  rk :: AMatroid a -> Set a -> Int
rk AMatroid a
m = (AMatroid a -> Maybe (Set a -> Int))
-> AMatroid a -> (Set a -> Int) -> Set a -> Int
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m                      ((Set a -> Int) -> Set a -> Int) -> (Set a -> Int) -> Set a -> Int
forall a b. (a -> b) -> a -> b
$ (Set a -> Set a) -> Set a -> Int
forall a. (Set a -> Set a) -> Set a -> Int
D.rk (AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis AMatroid a
m)
  indep :: AMatroid a -> Set a -> Bool
indep AMatroid a
m = (AMatroid a -> Maybe (Set a -> Bool))
-> AMatroid a -> (Set a -> Bool) -> Set a -> Bool
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a -> Bool)
forall a. AMatroid a -> Maybe (Set a -> Bool)
w_indep AMatroid a
m                ((Set a -> Bool) -> Set a -> Bool)
-> (Set a -> Bool) -> Set a -> Bool
forall a b. (a -> b) -> a -> b
$ (Set a -> Int) -> Set a -> Bool
forall a. (Set a -> Int) -> Set a -> Bool
D.indep (AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
m)
  basis :: AMatroid a -> Set a -> Set a
basis AMatroid a
m = (AMatroid a -> Maybe (Set a -> Set a))
-> AMatroid a -> (Set a -> Set a) -> Set a -> Set a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a -> Set a)
forall a. AMatroid a -> Maybe (Set a -> Set a)
w_basis AMatroid a
m                ((Set a -> Set a) -> Set a -> Set a)
-> (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ (Set a -> Bool) -> Set a -> Set a
forall a. Ord a => (Set a -> Bool) -> Set a -> Set a
D.basis (AMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep AMatroid a
m)
  cl :: AMatroid a -> Set a -> Set a
cl AMatroid a
m = (AMatroid a -> Maybe (Set a -> Set a))
-> AMatroid a -> (Set a -> Set a) -> Set a -> Set a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a -> Set a)
forall a. AMatroid a -> Maybe (Set a -> Set a)
w_cl AMatroid a
m                      ((Set a -> Set a) -> Set a -> Set a)
-> (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ (Set a -> Int) -> Set a -> Set a -> Set a
forall a. Ord a => (Set a -> Int) -> Set a -> Set a -> Set a
D.cl (AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
m) (AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset AMatroid a
m)
  {--- II. ---}
  abstract :: AMatroid a -> AMatroid a
abstract AMatroid a
m = (AMatroid a -> Maybe (AMatroid a))
-> AMatroid a -> AMatroid a -> AMatroid a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (AMatroid a)
forall a. AMatroid a -> Maybe (AMatroid a)
w_abstract AMatroid a
m          (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ AMatroid a
m -- it has been wrapped before
  dual :: AMatroid a -> AMatroid a
dual AMatroid a
m = (AMatroid a -> Maybe (AMatroid a))
-> AMatroid a -> AMatroid a -> AMatroid a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (AMatroid a)
forall a. AMatroid a -> Maybe (AMatroid a)
w_dual   AMatroid a
m                (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ AMatroid a -> AMatroid a
forall a. (Show a, Ord a) => AMatroid a -> AMatroid a
a_dual AMatroid a
m
  restriction :: AMatroid a -> Set a -> AMatroid a
restriction AMatroid a
m = (AMatroid a -> Maybe (Set a -> AMatroid a))
-> AMatroid a -> (Set a -> AMatroid a) -> Set a -> AMatroid a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a -> AMatroid a)
forall a. AMatroid a -> Maybe (Set a -> AMatroid a)
w_restriction AMatroid a
m    ((Set a -> AMatroid a) -> Set a -> AMatroid a)
-> (Set a -> AMatroid a) -> Set a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> AMatroid a
forall a. (Show a, Ord a) => AMatroid a -> Set a -> AMatroid a
a_restriction AMatroid a
m    
  contraction :: AMatroid a -> Set a -> AMatroid a
contraction AMatroid a
m = (AMatroid a -> Maybe (Set a -> AMatroid a))
-> AMatroid a -> (Set a -> AMatroid a) -> Set a -> AMatroid a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a -> AMatroid a)
forall a. AMatroid a -> Maybe (Set a -> AMatroid a)
w_contraction AMatroid a
m    ((Set a -> AMatroid a) -> Set a -> AMatroid a)
-> (Set a -> AMatroid a) -> Set a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> AMatroid a
forall a. (Show a, Ord a) => AMatroid a -> Set a -> AMatroid a
a_contraction AMatroid a
m   
  {--- III. ---}
  loops :: AMatroid a -> Set a
loops AMatroid a
m = (AMatroid a -> Maybe (Set a)) -> AMatroid a -> Set a -> Set a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a)
forall a. AMatroid a -> Maybe (Set a)
w_loops AMatroid a
m                (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ (Set a -> Set a) -> Set a
forall a. (Set a -> Set a) -> Set a
D.loops (AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m)
  coRk :: AMatroid a -> Set a -> Int
coRk AMatroid a
m = (AMatroid a -> Maybe (Set a -> Int))
-> AMatroid a -> (Set a -> Int) -> Set a -> Int
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_coRk AMatroid a
m                  ((Set a -> Int) -> Set a -> Int) -> (Set a -> Int) -> Set a -> Int
forall a b. (a -> b) -> a -> b
$ (Set a -> Int) -> Set a -> Set a -> Int
forall a. Ord a => (Set a -> Int) -> Set a -> Set a -> Int
D.coRk (AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
m) (AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset AMatroid a
m)
  coloops :: AMatroid a -> Set a
coloops AMatroid a
m = (AMatroid a -> Maybe (Set a)) -> AMatroid a -> Set a -> Set a
forall a0 a1. (a0 -> Maybe a1) -> a0 -> a1 -> a1
defaultsTo AMatroid a -> Maybe (Set a)
forall a. AMatroid a -> Maybe (Set a)
w_coloops AMatroid a
m            (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ (Set a -> Int) -> Set a -> Set a
forall a. Ord a => (Set a -> Int) -> Set a -> Set a
D.coloops (AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
m) (AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset AMatroid a
m)