{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

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

This module provides implementations of common operations on matroids
and an abstract matroid data type.

-}

module Data.Matroid.Ops where 

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

import Control.Monad
    

{- | abstract matroid data type with elements of a given type

  Its purpose is to hide the underlying type from the type system.
  The records resemble the typeclass 'Matroid', where everything except for the
  groundset has been placed inside the 'Maybe'-Monad. A value of 'Nothing'
  indicates that the default implementation of the typeclass should be used.
  
-}
data AMatroid a = WMatroid {
  {--- I. ---}
    AMatroid a -> Set a
w_groundset :: Set a 
  , AMatroid a -> Maybe String
w_showName :: Maybe (String)
  , AMatroid a -> Maybe (Set a -> Int)
w_rk :: Maybe (Set a -> Int)
  , AMatroid a -> Maybe (Set a -> Bool)
w_indep :: Maybe (Set a -> Bool)
  , AMatroid a -> Maybe (Set a -> Set a)
w_basis :: Maybe (Set a -> Set a)
  , AMatroid a -> Maybe (Set a -> Set a)
w_cl :: Maybe (Set a -> Set a)
  {--- II. ---}
  , AMatroid a -> Maybe (AMatroid a)
w_abstract :: Maybe (AMatroid a)
  , AMatroid a -> Maybe (AMatroid a)
w_dual :: Maybe (AMatroid a)
  , AMatroid a -> Maybe (Set a -> AMatroid a)
w_restriction :: Maybe (Set a -> AMatroid a)
  , AMatroid a -> Maybe (Set a -> AMatroid a)
w_contraction :: Maybe (Set a -> AMatroid a)
  {--- III. ---}
  ,  AMatroid a -> Maybe (Set a)
w_loops ::  Maybe (Set a)
  ,  AMatroid a -> Maybe (Set a -> Int)
w_coRk :: Maybe (Set a -> Int)
  ,  AMatroid a -> Maybe (Set a)
w_coloops ::  Maybe (Set a)
}

instance Show a => Show (AMatroid a) where
  show :: AMatroid a -> String
show AMatroid a
x = String -> ShowS -> Maybe String -> String
forall b a. b -> (a -> b) -> Maybe a -> b
maybe String
defShow ShowS
forall a. a -> a
id (Maybe String -> String) -> Maybe String -> String
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Maybe String
forall a. AMatroid a -> Maybe String
w_showName AMatroid a
x
    where defShow :: String
defShow = String
"WMatroid (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Set a -> String
forall a. Show a => a -> String
show (AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset AMatroid a
x) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") (...)"
    


-- | default values for 'WMatroid'
wrappedMatroid :: AMatroid a
wrappedMatroid :: AMatroid a
wrappedMatroid = WMatroid :: forall a.
Set a
-> Maybe String
-> Maybe (Set a -> Int)
-> Maybe (Set a -> Bool)
-> Maybe (Set a -> Set a)
-> Maybe (Set a -> Set a)
-> Maybe (AMatroid a)
-> Maybe (AMatroid a)
-> Maybe (Set a -> AMatroid a)
-> Maybe (Set a -> AMatroid a)
-> Maybe (Set a)
-> Maybe (Set a -> Int)
-> Maybe (Set a)
-> AMatroid a
WMatroid {
  {--- I. ---}
    w_groundset :: Set a
w_groundset = Set a
forall a. Set a
S.empty
  , w_showName :: Maybe String
w_showName = Maybe String
forall a. Maybe a
Nothing
  , w_rk :: Maybe (Set a -> Int)
w_rk = Maybe (Set a -> Int)
forall a. Maybe a
Nothing
  , w_indep :: Maybe (Set a -> Bool)
w_indep = Maybe (Set a -> Bool)
forall a. Maybe a
Nothing
  , w_basis :: Maybe (Set a -> Set a)
w_basis = Maybe (Set a -> Set a)
forall a. Maybe a
Nothing
  , w_cl :: Maybe (Set a -> Set a)
w_cl = Maybe (Set a -> Set a)
forall a. Maybe a
Nothing
  {--- II. ---}
  , w_abstract :: Maybe (AMatroid a)
w_abstract = Maybe (AMatroid a)
forall a. Maybe a
Nothing
  , w_dual :: Maybe (AMatroid a)
w_dual = Maybe (AMatroid a)
forall a. Maybe a
Nothing
  , w_restriction :: Maybe (Set a -> AMatroid a)
w_restriction = Maybe (Set a -> AMatroid a)
forall a. Maybe a
Nothing
  , w_contraction :: Maybe (Set a -> AMatroid a)
w_contraction = Maybe (Set a -> AMatroid a)
forall a. Maybe a
Nothing
  {--- III. ---}
  , w_loops :: Maybe (Set a)
w_loops = Maybe (Set a)
forall a. Maybe a
Nothing
  , w_coRk :: Maybe (Set a -> Int)
w_coRk = Maybe (Set a -> Int)
forall a. Maybe a
Nothing
  , w_coloops :: Maybe (Set a)
w_coloops = Maybe (Set a)
forall a. Maybe a
Nothing
}


{- | returns the restriction of a given matroid

  Note that this routine implements the correct routines provided that the prerequisite members
  in the input matroid are defined. Routines which have missing prerequisite members in the input
  matroid will be left to 'Nothing'. 'Data.Matroid.Typeclass.wrapUp' fills all 'AMatroid' record members.
-}
a_restriction :: (Show a, Ord a) => AMatroid a {- ^ input matroid -} -> Set a {- ^ restriction of ground set -} -> AMatroid a
a_restriction :: AMatroid a -> Set a -> AMatroid a
a_restriction AMatroid a
m Set a
x0 = String -> AMatroid a -> Set a -> AMatroid a
forall a. Ord a => String -> AMatroid a -> Set a -> AMatroid a
a_namedRestriction String
name AMatroid a
m Set a
x0
            where e :: Set a
e = Set a
x0 Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` (AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset AMatroid a
m)
                  name :: String
name = String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
m_name String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") `restriction` (" 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
")"
                  m_name :: String
m_name = String -> ShowS -> Maybe String -> String
forall b a. b -> (a -> b) -> Maybe a -> b
maybe String
"M" ShowS
forall a. a -> a
id (Maybe String -> String) -> Maybe String -> String
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Maybe String
forall a. AMatroid a -> Maybe String
w_showName AMatroid a
m
                  
{- | returns the restriction of a given matroid, named

  Note that this routine implements the correct routines provided that the prerequisite members
  in the input matroid are defined. Routines which have missing prerequisite members in the input
  matroid will be left to 'Nothing'. 'Data.Matroid.Typeclass.wrapUp' fills all 'AMatroid' record members.
-}
a_namedRestriction :: Ord a => String {- ^ name -} -> AMatroid a {- ^ input matroid -} -> Set a {- ^ restriction of ground set -} -> AMatroid a
a_namedRestriction :: String -> AMatroid a -> Set a -> AMatroid a
a_namedRestriction String
name AMatroid a
m Set a
x0 = AMatroid a
forall a. AMatroid a
wrappedMatroid {
    w_groundset :: Set a
w_groundset = Set a
e
  , w_showName :: Maybe String
w_showName = String -> Maybe String
forall a. a -> Maybe a
Just String
name
  , w_rk :: Maybe (Set a -> Int)
w_rk = AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m
  , w_indep :: Maybe (Set a -> Bool)
w_indep = AMatroid a -> Maybe (Set a -> Bool)
forall a. AMatroid a -> Maybe (Set a -> Bool)
w_indep AMatroid a
m
  , w_basis :: Maybe (Set a -> Set a)
w_basis = AMatroid a -> Maybe (Set a -> Set a)
forall a. AMatroid a -> Maybe (Set a -> Set a)
w_basis AMatroid a
m
  , w_cl :: Maybe (Set a -> Set a)
w_cl = Maybe ((Set a -> Set a) -> Set a -> Set a)
forall t. Maybe ((t -> Set a) -> t -> Set a)
intersectWithE Maybe ((Set a -> Set a) -> Set a -> Set a)
-> Maybe (Set a -> Set a) -> Maybe (Set a -> Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> AMatroid a -> Maybe (Set a -> Set a)
forall a. AMatroid a -> Maybe (Set a -> Set a)
w_cl AMatroid a
m
  , w_loops :: Maybe (Set a)
w_loops = (Set a -> Set a) -> Maybe (Set a -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.intersection Set a
e) Maybe (Set a -> Set a) -> Maybe (Set a) -> Maybe (Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> AMatroid a -> Maybe (Set a)
forall a. AMatroid a -> Maybe (Set a)
w_loops AMatroid a
m
  , w_coRk :: Maybe (Set a -> Int)
w_coRk = ((Set a -> Int) -> Set a -> Int)
-> Maybe ((Set a -> Int) -> Set a -> Int)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Int
rk_ -> (Set a -> Int) -> Set a -> Set a -> Int
forall a. Ord a => (Set a -> Int) -> Set a -> Set a -> Int
D.coRk Set a -> Int
rk_ Set a
e) Maybe ((Set a -> Int) -> Set a -> Int)
-> Maybe (Set a -> Int) -> Maybe (Set a -> Int)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m)
  , w_coloops :: Maybe (Set a)
w_coloops = ((Set a -> Int) -> Set a) -> Maybe ((Set a -> Int) -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Int
rk_ -> (Set a -> Int) -> Set a -> Set a
forall a. Ord a => (Set a -> Int) -> Set a -> Set a
D.coloops Set a -> Int
rk_ Set a
e) Maybe ((Set a -> Int) -> Set a)
-> Maybe (Set a -> Int) -> Maybe (Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m)
  , w_restriction :: Maybe (Set a -> AMatroid a)
w_restriction = AMatroid a -> Maybe (Set a -> AMatroid a)
forall a. AMatroid a -> Maybe (Set a -> AMatroid a)
w_restriction AMatroid a
m -- (M|X0)|X1 = M|X1 whenever defined.
} where e :: Set a
e = Set a
x0 Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` (AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset AMatroid a
m)
        intersectWithE :: Maybe ((t -> Set a) -> t -> Set a)
intersectWithE = ((t -> Set a) -> t -> Set a) -> Maybe ((t -> Set a) -> t -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\t -> Set a
f -> \t
x -> Set a
e Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` t -> Set a
f t
x)

{- | returns the contraction of a given matroid

  Note that this routine implements the correct routines provided that the prerequisite members
  in the input matroid are defined. Routines which have missing prerequisite members in the input
  matroid will be left to 'Nothing'. 'Data.Matroid.Typeclass.wrapUp' fills all 'AMatroid' record members.
-}
a_contraction :: (Show a, Ord a) => AMatroid a {- ^ input matroid -} -> Set a {- ^ contract the ground set onto this set -} -> AMatroid a
a_contraction :: AMatroid a -> Set a -> AMatroid a
a_contraction AMatroid a
m Set a
x0 = String -> AMatroid a -> Set a -> AMatroid a
forall a. Ord a => String -> AMatroid a -> Set a -> AMatroid a
a_namedContraction String
name AMatroid a
m Set a
x0
            where e :: Set a
e = Set a
x0 Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` (AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset AMatroid a
m)
                  name :: String
name = String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
m_name String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") `contraction` (" 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
")"
                  m_name :: String
m_name = String -> ShowS -> Maybe String -> String
forall b a. b -> (a -> b) -> Maybe a -> b
maybe String
"M" ShowS
forall a. a -> a
id (Maybe String -> String) -> Maybe String -> String
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Maybe String
forall a. AMatroid a -> Maybe String
w_showName AMatroid a
m
                  
{- | returns the contraction of a given matroid, named

  Note that this routine implements the correct routines provided that the prerequisite members
  in the input matroid are defined. Routines which have missing prerequisite members in the input
  matroid will be left to 'Nothing'. 'Data.Matroid.Typeclass.wrapUp' fills all 'AMatroid' record members.
-}
a_namedContraction :: Ord a => String {- ^ name -} -> AMatroid a {- ^ input matroid -} -> Set a {- ^ contract the ground set onto this set -} -> AMatroid a
a_namedContraction :: String -> AMatroid a -> Set a -> AMatroid a
a_namedContraction String
name AMatroid a
m Set a
x0 = AMatroid a
forall a. AMatroid a
wrappedMatroid {
    w_groundset :: Set a
w_groundset = Set a
e
  , w_showName :: Maybe String
w_showName = String -> Maybe String
forall a. a -> Maybe a
Just String
name
  , w_rk :: Maybe (Set a -> Int)
w_rk =    Maybe (Set a -> Int)
new_rk
  , w_indep :: Maybe (Set a -> Bool)
w_indep = Maybe (Set a -> Bool)
new_indep
  , w_basis :: Maybe (Set a -> Set a)
w_basis = ((Set a -> Bool) -> Set a -> Set a)
-> Maybe ((Set a -> Bool) -> Set a -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Bool
indep_ -> (Set a -> Bool) -> Set a -> Set a
forall a. Ord a => (Set a -> Bool) -> Set a -> Set a
D.basis Set a -> Bool
indep_) Maybe ((Set a -> Bool) -> Set a -> Set a)
-> Maybe (Set a -> Bool) -> Maybe (Set a -> Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe (Set a -> Bool)
new_indep
  , w_cl :: Maybe (Set a -> Set a)
w_cl =    ((Set a -> Set a) -> Set a -> Set a)
-> Maybe ((Set a -> Set a) -> Set a -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Set a
cl_ -> \Set a
x -> (Set a -> Set a
cl_ (Set a
x Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set a
t)) Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` Set a
e) Maybe ((Set a -> Set a) -> Set a -> Set a)
-> Maybe (Set a -> Set a) -> Maybe (Set a -> Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (AMatroid a -> Maybe (Set a -> Set a)
forall a. AMatroid a -> Maybe (Set a -> Set a)
w_cl AMatroid a
m)
  , w_loops :: Maybe (Set a)
w_loops = ((Set a -> Set a) -> Set a) -> Maybe ((Set a -> Set a) -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Set a
cl_ -> (Set a -> Set a
cl_ Set a
t) Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` Set a
e)                     Maybe ((Set a -> Set a) -> Set a)
-> Maybe (Set a -> Set a) -> Maybe (Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (AMatroid a -> Maybe (Set a -> Set a)
forall a. AMatroid a -> Maybe (Set a -> Set a)
w_cl AMatroid a
m)
  , w_coRk :: Maybe (Set a -> Int)
w_coRk =  ((Set a -> Int) -> Set a -> Int)
-> Maybe ((Set a -> Int) -> Set a -> Int)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Int
rk_ -> (Set a -> Int) -> Set a -> Set a -> Int
forall a. Ord a => (Set a -> Int) -> Set a -> Set a -> Int
D.coRk Set a -> Int
rk_ Set a
e) Maybe ((Set a -> Int) -> Set a -> Int)
-> Maybe (Set a -> Int) -> Maybe (Set a -> Int)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe (Set a -> Int)
new_rk
  , w_coloops :: Maybe (Set a)
w_coloops = (Set a -> Set a) -> Maybe (Set a -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.intersection Set a
e) Maybe (Set a -> Set a) -> Maybe (Set a) -> Maybe (Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (AMatroid a -> Maybe (Set a)
forall a. AMatroid a -> Maybe (Set a)
w_coloops AMatroid a
m)
  , w_contraction :: Maybe (Set a -> AMatroid a)
w_contraction = AMatroid a -> Maybe (Set a -> AMatroid a)
forall a. AMatroid a -> Maybe (Set a -> AMatroid a)
w_contraction AMatroid a
m -- (M.X0).X1 = M.X1 whenever defined.
} where e :: Set a
e = Set a
x0 Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` (AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset AMatroid a
m)
        t :: Set a
t = (AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset AMatroid a
m) Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.difference` Set a
e -- deleted edges
        bt :: Maybe (Set a)
bt = AMatroid a -> Maybe (Set a -> Set a)
forall a. AMatroid a -> Maybe (Set a -> Set a)
w_basis AMatroid a
m Maybe (Set a -> Set a) -> Maybe (Set a) -> Maybe (Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Set a -> Maybe (Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Set a
t -- maybe the basis of deleted edges
        rt :: Maybe Int
rt = AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m Maybe (Set a -> Int) -> Maybe (Set a) -> Maybe Int
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Set a -> Maybe (Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Set a
t -- maybe the rank of t
        new_rk :: Maybe (Set a -> Int)
new_rk = ((Set a -> Int) -> Int -> Set a -> Int)
-> Maybe ((Set a -> Int) -> Int -> Set a -> Int)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Int
rk_ -> \Int
rt_ -> \Set a
x -> Set a -> Int
rk_ (Set a
x Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set a
t) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
rt_ ) Maybe ((Set a -> Int) -> Int -> Set a -> Int)
-> Maybe (Set a -> Int) -> Maybe (Int -> Set a -> Int)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m)    Maybe (Int -> Set a -> Int) -> Maybe Int -> Maybe (Set a -> Int)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe Int
rt
        new_indep :: Maybe (Set a -> Bool)
new_indep = ((Set a -> Bool) -> Set a -> Set a -> Bool)
-> Maybe ((Set a -> Bool) -> Set a -> Set a -> Bool)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Bool
indep_ -> \Set a
bt_ -> \Set a
x -> Set a -> Bool
indep_ (Set a
x Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set a
bt_))  Maybe ((Set a -> Bool) -> Set a -> Set a -> Bool)
-> Maybe (Set a -> Bool) -> Maybe (Set a -> Set a -> Bool)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (AMatroid a -> Maybe (Set a -> Bool)
forall a. AMatroid a -> Maybe (Set a -> Bool)
w_indep AMatroid a
m) Maybe (Set a -> Set a -> Bool)
-> Maybe (Set a) -> Maybe (Set a -> Bool)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe (Set a)
bt

        
{- | returns the contraction of a given matroid

  Note that this routine implements the correct routines provided that the prerequisite members
  in the input matroid are defined. Routines which have missing prerequisite members in the input
  matroid will be left to 'Nothing'. 'Data.Matroid.Typeclass.wrapUp' fills all 'AMatroid' record members.
-}
a_dual :: (Show a, Ord a) => AMatroid a {- ^ input matroid -} -> AMatroid a
a_dual :: AMatroid a -> AMatroid a
a_dual AMatroid a
m  = String -> AMatroid a -> AMatroid a
forall a. Ord a => String -> AMatroid a -> AMatroid a
a_namedDual String
name AMatroid a
m 
            where name :: String
name = String
"dual (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
m_name String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
                  m_name :: String
m_name = String -> ShowS -> Maybe String -> String
forall b a. b -> (a -> b) -> Maybe a -> b
maybe String
"M" ShowS
forall a. a -> a
id (Maybe String -> String) -> Maybe String -> String
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Maybe String
forall a. AMatroid a -> Maybe String
w_showName AMatroid a
m
                  
{- | returns the contraction of a given matroid, named

  Note that this routine implements the correct routines provided that the prerequisite members
  in the input matroid are defined. Routines which have missing prerequisite members in the input
  matroid will be left to 'Nothing'. 'Data.Matroid.Typeclass.wrapUp' fills all 'AMatroid' record members.
-}
a_namedDual :: Ord a => String {- ^ name -} -> AMatroid a {- ^ input matroid -} -> AMatroid a
a_namedDual :: String -> AMatroid a -> AMatroid a
a_namedDual String
name AMatroid a
m = AMatroid a
forall a. AMatroid a
wrappedMatroid {
    w_groundset :: Set a
w_groundset = Set a
e
  , w_showName :: Maybe String
w_showName = String -> Maybe String
forall a. a -> Maybe a
Just String
name
  , w_rk :: Maybe (Set a -> Int)
w_rk = Maybe (Set a -> Int)
new_rk
  , w_indep :: Maybe (Set a -> Bool)
w_indep = Maybe (Set a -> Bool)
new_indep
  , w_basis :: Maybe (Set a -> Set a)
w_basis = ((Set a -> Bool) -> Set a -> Set a)
-> Maybe ((Set a -> Bool) -> Set a -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Bool
indep_ -> (Set a -> Bool) -> Set a -> Set a
forall a. Ord a => (Set a -> Bool) -> Set a -> Set a
D.basis Set a -> Bool
indep_) Maybe ((Set a -> Bool) -> Set a -> Set a)
-> Maybe (Set a -> Bool) -> Maybe (Set a -> Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe (Set a -> Bool)
new_indep
  , w_cl :: Maybe (Set a -> Set a)
w_cl =    ((Set a -> Int) -> Set a -> Set a)
-> Maybe ((Set a -> Int) -> Set a -> Set a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Int
rk_ -> (Set a -> Int) -> Set a -> Set a -> Set a
forall a. Ord a => (Set a -> Int) -> Set a -> Set a -> Set a
D.cl Set a -> Int
rk_ Set a
e) Maybe ((Set a -> Int) -> Set a -> Set a)
-> Maybe (Set a -> Int) -> Maybe (Set a -> Set a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe (Set a -> Int)
new_rk
  , w_loops :: Maybe (Set a)
w_loops = AMatroid a -> Maybe (Set a)
forall a. AMatroid a -> Maybe (Set a)
w_coloops AMatroid a
m
  , w_coRk :: Maybe (Set a -> Int)
w_coRk = AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m
  , w_coloops :: Maybe (Set a)
w_coloops = AMatroid a -> Maybe (Set a)
forall a. AMatroid a -> Maybe (Set a)
w_loops AMatroid a
m
  , w_dual :: Maybe (AMatroid a)
w_dual = AMatroid a -> Maybe (AMatroid a)
forall a. a -> Maybe a
Just AMatroid a
m -- bounce back to the original matroid
} where e :: Set a
e = (AMatroid a -> Set a
forall a. AMatroid a -> Set a
w_groundset AMatroid a
m)
        new_rk :: Maybe (Set a -> Int)
new_rk = (AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_coRk AMatroid a
m) Maybe (Set a -> Int)
-> Maybe (Set a -> Int) -> Maybe (Set a -> Int)
forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
`mplus` (((Set a -> Int) -> Set a -> Int)
-> Maybe ((Set a -> Int) -> Set a -> Int)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Int
rk_ -> (Set a -> Int) -> Set a -> Set a -> Int
forall a. Ord a => (Set a -> Int) -> Set a -> Set a -> Int
D.coRk Set a -> Int
rk_ Set a
e) Maybe ((Set a -> Int) -> Set a -> Int)
-> Maybe (Set a -> Int) -> Maybe (Set a -> Int)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> AMatroid a -> Maybe (Set a -> Int)
forall a. AMatroid a -> Maybe (Set a -> Int)
w_rk AMatroid a
m)
        new_indep :: Maybe (Set a -> Bool)
new_indep = ((Set a -> Int) -> Set a -> Bool)
-> Maybe ((Set a -> Int) -> Set a -> Bool)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (\Set a -> Int
rk_ -> (Set a -> Int) -> Set a -> Bool
forall a. (Set a -> Int) -> Set a -> Bool
D.indep Set a -> Int
rk_) Maybe ((Set a -> Int) -> Set a -> Bool)
-> Maybe (Set a -> Int) -> Maybe (Set a -> Bool)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe (Set a -> Int)
new_rk