{-# 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 of the input subset, which has maximal cardinality among all such subsets.
    
      Please note that this routine returns a basis of the input subset wrt. the matroid, which is not necessarily
      also a basis of the matroid itself. You can obtain at least one basis of the matroid via
      
        > basis m $ groundset m
      
    -}
    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)