{-# LANGUAGE NoMonomorphismRestriction, DeriveFunctor #-}
module Math.Combinatorics.Matroid where
import Math.Core.Utils
import Math.Core.Field hiding (f7)
import Math.Common.ListSet as LS
import Math.Algebra.LinearAlgebra hiding (rank)
import qualified Math.Combinatorics.Graph as G
import Math.Combinatorics.FiniteGeometry
import Math.Combinatorics.GraphAuts
import Math.Algebra.Group.PermutationGroup hiding (closure)
import Math.Algebras.VectorSpace hiding (dual)
import Math.Algebras.Structures
import Math.Algebras.Commutative
import Data.List as L
import qualified Data.Map as M
import qualified Data.Set as S
implies :: Bool -> Bool -> Bool
implies p :: Bool
p q :: Bool
q = Bool
q Bool -> Bool -> Bool
|| Bool -> Bool
not Bool
p
exists :: t a -> Bool
exists = Bool -> Bool
not (Bool -> Bool) -> (t a -> Bool) -> t a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null
unique :: [a] -> a
unique [x :: a
x] = a
x
shortlex :: t a -> t a -> Ordering
shortlex xs :: t a
xs ys :: t a
ys = case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (t a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length t a
xs) (t a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length t a
ys) of
LT -> Ordering
LT
EQ -> t a -> t a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare t a
xs t a
ys
GT -> Ordering
GT
isShortlex :: [t a] -> Bool
isShortlex xs :: [t a]
xs = (t a -> t a -> Bool) -> [t a] -> Bool
forall b. (b -> b -> Bool) -> [b] -> Bool
foldcmpl (\x1 :: t a
x1 x2 :: t a
x2 -> t a -> t a -> Ordering
forall (t :: * -> *) a.
(Foldable t, Ord (t a)) =>
t a -> t a -> Ordering
shortlex t a
x1 t a
x2 Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
/= Ordering
GT) [t a]
xs
toShortlex :: [t a] -> [t a]
toShortlex xs :: [t a]
xs = ((Int, t a) -> t a) -> [(Int, t a)] -> [t a]
forall a b. (a -> b) -> [a] -> [b]
map (Int, t a) -> t a
forall a b. (a, b) -> b
snd ([(Int, t a)] -> [t a]) -> [(Int, t a)] -> [t a]
forall a b. (a -> b) -> a -> b
$ [(Int, t a)] -> [(Int, t a)]
forall a. Ord a => [a] -> [a]
L.sort [(t a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length t a
x, t a
x) | t a
x <- [t a]
xs]
isClutter :: [[a]] -> Bool
isClutter ss :: [[a]]
ss = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ ([a]
s1 [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
s2) Bool -> Bool -> Bool
`implies` ([a]
s1 [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
s2) | [a]
s1 <- [[a]]
ss, [a]
s2 <- [[a]]
ss ]
deletions :: [a] -> [[a]]
deletions xs :: [a]
xs = ([a] -> [a] -> [a]) -> [[a]] -> [[a]] -> [[a]]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
(++) ([a] -> [[a]]
forall a. [a] -> [[a]]
inits [a]
xs) ([[a]] -> [[a]]
forall a. [a] -> [a]
tail ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [a] -> [[a]]
forall a. [a] -> [[a]]
tails [a]
xs)
closedUnderSubsets :: [[a]] -> Bool
closedUnderSubsets xss :: [[a]]
xss = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [[a]
xs' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set [a]
xss' | [a]
xs <- [[a]]
xss, [a]
xs' <- [a] -> [[a]]
forall a. [a] -> [[a]]
deletions [a]
xs]
where xss' :: Set [a]
xss' = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [[a]]
xss
data TrieSet a = TS [(a, TrieSet a)] deriving (TrieSet a -> TrieSet a -> Bool
(TrieSet a -> TrieSet a -> Bool)
-> (TrieSet a -> TrieSet a -> Bool) -> Eq (TrieSet a)
forall a. Eq a => TrieSet a -> TrieSet a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: TrieSet a -> TrieSet a -> Bool
$c/= :: forall a. Eq a => TrieSet a -> TrieSet a -> Bool
== :: TrieSet a -> TrieSet a -> Bool
$c== :: forall a. Eq a => TrieSet a -> TrieSet a -> Bool
Eq,Eq (TrieSet a)
Eq (TrieSet a) =>
(TrieSet a -> TrieSet a -> Ordering)
-> (TrieSet a -> TrieSet a -> Bool)
-> (TrieSet a -> TrieSet a -> Bool)
-> (TrieSet a -> TrieSet a -> Bool)
-> (TrieSet a -> TrieSet a -> Bool)
-> (TrieSet a -> TrieSet a -> TrieSet a)
-> (TrieSet a -> TrieSet a -> TrieSet a)
-> Ord (TrieSet a)
TrieSet a -> TrieSet a -> Bool
TrieSet a -> TrieSet a -> Ordering
TrieSet a -> TrieSet a -> TrieSet 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 (TrieSet a)
forall a. Ord a => TrieSet a -> TrieSet a -> Bool
forall a. Ord a => TrieSet a -> TrieSet a -> Ordering
forall a. Ord a => TrieSet a -> TrieSet a -> TrieSet a
min :: TrieSet a -> TrieSet a -> TrieSet a
$cmin :: forall a. Ord a => TrieSet a -> TrieSet a -> TrieSet a
max :: TrieSet a -> TrieSet a -> TrieSet a
$cmax :: forall a. Ord a => TrieSet a -> TrieSet a -> TrieSet a
>= :: TrieSet a -> TrieSet a -> Bool
$c>= :: forall a. Ord a => TrieSet a -> TrieSet a -> Bool
> :: TrieSet a -> TrieSet a -> Bool
$c> :: forall a. Ord a => TrieSet a -> TrieSet a -> Bool
<= :: TrieSet a -> TrieSet a -> Bool
$c<= :: forall a. Ord a => TrieSet a -> TrieSet a -> Bool
< :: TrieSet a -> TrieSet a -> Bool
$c< :: forall a. Ord a => TrieSet a -> TrieSet a -> Bool
compare :: TrieSet a -> TrieSet a -> Ordering
$ccompare :: forall a. Ord a => TrieSet a -> TrieSet a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (TrieSet a)
Ord,a -> TrieSet b -> TrieSet a
(a -> b) -> TrieSet a -> TrieSet b
(forall a b. (a -> b) -> TrieSet a -> TrieSet b)
-> (forall a b. a -> TrieSet b -> TrieSet a) -> Functor TrieSet
forall a b. a -> TrieSet b -> TrieSet a
forall a b. (a -> b) -> TrieSet a -> TrieSet b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> TrieSet b -> TrieSet a
$c<$ :: forall a b. a -> TrieSet b -> TrieSet a
fmap :: (a -> b) -> TrieSet a -> TrieSet b
$cfmap :: forall a b. (a -> b) -> TrieSet a -> TrieSet b
Functor)
tsshow :: TrieSet a -> [Char]
tsshow (TS xts :: [(a, TrieSet a)]
xts) = "TS [" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ ((a, TrieSet a) -> [Char]) -> [(a, TrieSet a)] -> [Char]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\(x :: a
x,t :: TrieSet a
t) -> "(" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ a -> [Char]
forall a. Show a => a -> [Char]
show a
x [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ "," [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ TrieSet a -> [Char]
tsshow TrieSet a
t [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ ")") [(a, TrieSet a)]
xts [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ "]"
instance Show a => Show (TrieSet a) where
show :: TrieSet a -> [Char]
show = [[a]] -> [Char]
forall a. Show a => a -> [Char]
show ([[a]] -> [Char]) -> (TrieSet a -> [[a]]) -> TrieSet a -> [Char]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet a -> [[a]]
forall a. TrieSet a -> [[a]]
tstolist
tsempty :: TrieSet a
tsempty = [(a, TrieSet a)] -> TrieSet a
forall a. [(a, TrieSet a)] -> TrieSet a
TS []
tsinsert :: [a] -> TrieSet a -> TrieSet a
tsinsert (x :: a
x:xs :: [a]
xs) (TS ts :: [(a, TrieSet a)]
ts) =
case a -> [(a, TrieSet a)] -> Maybe (TrieSet a)
forall a b. Eq a => a -> [(a, b)] -> Maybe b
L.lookup a
x [(a, TrieSet a)]
ts of
Nothing -> let t :: TrieSet a
t = [a] -> TrieSet a -> TrieSet a
tsinsert [a]
xs ([(a, TrieSet a)] -> TrieSet a
forall a. [(a, TrieSet a)] -> TrieSet a
TS [])
in [(a, TrieSet a)] -> TrieSet a
forall a. [(a, TrieSet a)] -> TrieSet a
TS ([(a, TrieSet a)] -> TrieSet a) -> [(a, TrieSet a)] -> TrieSet a
forall a b. (a -> b) -> a -> b
$ (a, TrieSet a) -> [(a, TrieSet a)] -> [(a, TrieSet a)]
forall a. Ord a => a -> [a] -> [a]
L.insert (a
x,TrieSet a
t) [(a, TrieSet a)]
ts
Just t :: TrieSet a
t -> let t' :: TrieSet a
t' = [a] -> TrieSet a -> TrieSet a
tsinsert [a]
xs TrieSet a
t
in [(a, TrieSet a)] -> TrieSet a
forall a. [(a, TrieSet a)] -> TrieSet a
TS ([(a, TrieSet a)] -> TrieSet a) -> [(a, TrieSet a)] -> TrieSet a
forall a b. (a -> b) -> a -> b
$ (a, TrieSet a) -> [(a, TrieSet a)] -> [(a, TrieSet a)]
forall a. Ord a => a -> [a] -> [a]
L.insert (a
x,TrieSet a
t') ([(a, TrieSet a)] -> [(a, TrieSet a)])
-> [(a, TrieSet a)] -> [(a, TrieSet a)]
forall a b. (a -> b) -> a -> b
$ (a, TrieSet a) -> [(a, TrieSet a)] -> [(a, TrieSet a)]
forall a. Eq a => a -> [a] -> [a]
L.delete (a
x,TrieSet a
t) [(a, TrieSet a)]
ts
tsinsert [] t :: TrieSet a
t = TrieSet a
t
tsmember :: [a] -> TrieSet a -> Bool
tsmember (x :: a
x:xs :: [a]
xs) (TS ts :: [(a, TrieSet a)]
ts) =
case a -> [(a, TrieSet a)] -> Maybe (TrieSet a)
forall a b. Eq a => a -> [(a, b)] -> Maybe b
lookup a
x [(a, TrieSet a)]
ts of
Nothing -> Bool
False
Just t :: TrieSet a
t -> [a] -> TrieSet a -> Bool
tsmember [a]
xs TrieSet a
t
tsmember [] (TS []) = Bool
True
tsmember [] _ = Bool
False
tssubmember :: [a] -> TrieSet a -> Bool
tssubmember (x :: a
x:xs :: [a]
xs) (TS ts :: [(a, TrieSet a)]
ts) = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
or [ case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
LT -> Bool
False
EQ -> [a] -> TrieSet a -> Bool
tssubmember [a]
xs TrieSet a
t
GT -> [a] -> TrieSet a -> Bool
tssubmember (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) TrieSet a
t
| (y :: a
y,t :: TrieSet a
t) <- [(a, TrieSet a)]
ts ]
tssubmember [] _ = Bool
True
tstolist :: TrieSet a -> [[a]]
tstolist (TS []) = [[]]
tstolist (TS xts :: [(a, TrieSet a)]
xts) = ((a, TrieSet a) -> [[a]]) -> [(a, TrieSet a)] -> [[a]]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\(x :: a
x,t :: TrieSet a
t) -> ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (TrieSet a -> [[a]]
tstolist TrieSet a
t)) [(a, TrieSet a)]
xts
tsfromlist :: t [a] -> TrieSet a
tsfromlist = (TrieSet a -> [a] -> TrieSet a) -> TrieSet a -> t [a] -> TrieSet a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (([a] -> TrieSet a -> TrieSet a) -> TrieSet a -> [a] -> TrieSet a
forall a b c. (a -> b -> c) -> b -> a -> c
flip [a] -> TrieSet a -> TrieSet a
forall a. Ord a => [a] -> TrieSet a -> TrieSet a
tsinsert) TrieSet a
forall a. TrieSet a
tsempty
data Matroid a = M [a] (TrieSet a) deriving (Matroid a -> Matroid a -> Bool
(Matroid a -> Matroid a -> Bool)
-> (Matroid a -> Matroid a -> Bool) -> Eq (Matroid a)
forall a. Eq a => Matroid a -> Matroid a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Matroid a -> Matroid a -> Bool
$c/= :: forall a. Eq a => Matroid a -> Matroid a -> Bool
== :: Matroid a -> Matroid a -> Bool
$c== :: forall a. Eq a => Matroid a -> Matroid a -> Bool
Eq,Int -> Matroid a -> [Char] -> [Char]
[Matroid a] -> [Char] -> [Char]
Matroid a -> [Char]
(Int -> Matroid a -> [Char] -> [Char])
-> (Matroid a -> [Char])
-> ([Matroid a] -> [Char] -> [Char])
-> Show (Matroid a)
forall a. Show a => Int -> Matroid a -> [Char] -> [Char]
forall a. Show a => [Matroid a] -> [Char] -> [Char]
forall a. Show a => Matroid a -> [Char]
forall a.
(Int -> a -> [Char] -> [Char])
-> (a -> [Char]) -> ([a] -> [Char] -> [Char]) -> Show a
showList :: [Matroid a] -> [Char] -> [Char]
$cshowList :: forall a. Show a => [Matroid a] -> [Char] -> [Char]
show :: Matroid a -> [Char]
$cshow :: forall a. Show a => Matroid a -> [Char]
showsPrec :: Int -> Matroid a -> [Char] -> [Char]
$cshowsPrec :: forall a. Show a => Int -> Matroid a -> [Char] -> [Char]
Show,a -> Matroid b -> Matroid a
(a -> b) -> Matroid a -> Matroid b
(forall a b. (a -> b) -> Matroid a -> Matroid b)
-> (forall a b. a -> Matroid b -> Matroid a) -> Functor Matroid
forall a b. a -> Matroid b -> Matroid a
forall a b. (a -> b) -> Matroid a -> Matroid b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Matroid b -> Matroid a
$c<$ :: forall a b. a -> Matroid b -> Matroid a
fmap :: (a -> b) -> Matroid a -> Matroid b
$cfmap :: forall a b. (a -> b) -> Matroid a -> Matroid b
Functor)
elements :: Matroid t -> [t]
elements :: Matroid t -> [t]
elements (M es :: [t]
es bs :: TrieSet t
bs) = [t]
es
indeps :: (Ord a) => Matroid a -> [[a]]
indeps :: Matroid a -> [[a]]
indeps m :: Matroid a
m = [([a], [a])] -> [[a]]
bfs [ ([],[a]
es) ]
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
bfs :: [([a], [a])] -> [[a]]
bfs ( (ls :: [a]
ls,rs :: [a]
rs) : nodes :: [([a], [a])]
nodes ) =
let ls' :: [a]
ls' = [a] -> [a]
forall a. [a] -> [a]
reverse [a]
ls in
if Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isIndependent Matroid a
m [a]
ls'
then [a]
ls' [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: [([a], [a])] -> [[a]]
bfs ( [([a], [a])]
nodes [([a], [a])] -> [([a], [a])] -> [([a], [a])]
forall a. [a] -> [a] -> [a]
++ ([a], [a]) -> [([a], [a])]
forall a. ([a], [a]) -> [([a], [a])]
successors ([a]
ls,[a]
rs) )
else [([a], [a])] -> [[a]]
bfs [([a], [a])]
nodes
bfs [] = []
successors :: ([a], [a]) -> [([a], [a])]
successors (ls :: [a]
ls,rs :: [a]
rs) = [ (a
ra -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ls, [a]
rs') | r :: a
r:rs' :: [a]
rs' <- [a] -> [[a]]
forall a. [a] -> [[a]]
L.tails [a]
rs ]
isIndependent :: (Ord a) => Matroid a -> [a] -> Bool
isIndependent :: Matroid a -> [a] -> Bool
isIndependent (M es :: [a]
es bs :: TrieSet a
bs) xs :: [a]
xs = [a]
xs [a] -> TrieSet a -> Bool
forall a. Ord a => [a] -> TrieSet a -> Bool
`tssubmember` TrieSet a
bs
isDependent :: (Ord a) => Matroid a -> [a] -> Bool
isDependent :: Matroid a -> [a] -> Bool
isDependent m :: Matroid a
m = Bool -> Bool
not (Bool -> Bool) -> ([a] -> Bool) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isIndependent Matroid a
m
isMatroidIndeps :: (Ord a) => [[a]] -> Bool
isMatroidIndeps :: [[a]] -> Bool
isMatroidIndeps is :: [[a]]
is =
[] [a] -> [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [[a]]
is Bool -> Bool -> Bool
&&
[[a]] -> Bool
forall a. Ord a => [[a]] -> Bool
closedUnderSubsets [[a]]
is Bool -> Bool -> Bool
&&
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ (Int
l1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
l2) Bool -> Bool -> Bool
`implies` [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
exists [a
e | a
e <- [a]
i2 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
i1, a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
e [a]
i1 [a] -> [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [[a]]
is]
| [a]
i1 <- [[a]]
is, let l1 :: Int
l1 = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
i1, [a]
i2 <- [[a]]
is, let l2 :: Int
l2 = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
i2 ]
fromIndeps :: (Ord a) => [a] -> [[a]] -> Matroid a
fromIndeps :: [a] -> [[a]] -> Matroid a
fromIndeps es :: [a]
es is :: [[a]]
is = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
where bs :: [[a]]
bs = [[a]] -> [([a], [a])] -> [[a]]
dfs [] [([],[a]
es)]
dfs :: [[a]] -> [([a], [a])] -> [[a]]
dfs bs :: [[a]]
bs ( node :: ([a], [a])
node@(ls :: [a]
ls,rs :: [a]
rs) : nodes :: [([a], [a])]
nodes ) =
let succs :: [([a], [a])]
succs = ([a], [a]) -> [([a], [a])]
successors ([a], [a])
node
in if [([a], [a])] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [([a], [a])]
succs then [[a]] -> [([a], [a])] -> [[a]]
dfs ([a]
ls[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
bs) [([a], [a])]
nodes else [[a]] -> [([a], [a])] -> [[a]]
dfs [[a]]
bs ([([a], [a])]
succs [([a], [a])] -> [([a], [a])] -> [([a], [a])]
forall a. [a] -> [a] -> [a]
++ [([a], [a])]
nodes)
dfs ls :: [[a]]
ls [] = let r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> [a] -> Int
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall a. [a] -> a
last [[a]]
ls
in ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> [a]
forall a. [a] -> [a]
reverse ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
filter (\b :: [a]
b -> [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r) [[a]]
ls
successors :: ([a], [a]) -> [([a], [a])]
successors (ls :: [a]
ls,rs :: [a]
rs) = [ (a
ra -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ls, [a]
rs') | r :: a
r:rs' :: [a]
rs' <- [a] -> [[a]]
forall a. [a] -> [[a]]
L.tails [a]
rs, (a
ra -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ls) [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set [a]
is' ]
is' :: Set [a]
is' = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList ([[a]] -> Set [a]) -> [[a]] -> Set [a]
forall a b. (a -> b) -> a -> b
$ ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> [a]
forall a. [a] -> [a]
reverse [[a]]
is
fromIndeps1 :: [a] -> [[a]] -> Matroid a
fromIndeps1 es :: [a]
es is :: [[a]]
is = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
where b :: [a]
b = [a] -> [a] -> [a]
greedy [] [a]
es
greedy :: [a] -> [a] -> [a]
greedy ls :: [a]
ls (r :: a
r:rs :: [a]
rs) = if (a
ra -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ls) [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set [a]
ris'
then [a] -> [a] -> [a]
greedy (a
ra -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ls) [a]
rs
else [a] -> [a] -> [a]
greedy [a]
ls [a]
rs
greedy ls :: [a]
ls [] = [a] -> [a]
forall a. [a] -> [a]
reverse [a]
ls
ris' :: Set [a]
ris' = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList ([[a]] -> Set [a]) -> [[a]] -> Set [a]
forall a b. (a -> b) -> a -> b
$ ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> [a]
forall a. [a] -> [a]
reverse [[a]]
is
bs :: [[a]]
bs = Set [a] -> Set [a] -> [[a]]
closure Set [a]
forall a. Set a
S.empty ([a] -> Set [a]
forall a. a -> Set a
S.singleton [a]
b)
closure :: Set [a] -> Set [a] -> [[a]]
closure interior :: Set [a]
interior boundary :: Set [a]
boundary =
if Set [a] -> Bool
forall a. Set a -> Bool
S.null Set [a]
boundary
then Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
interior
else let interior' :: Set [a]
interior' = Set [a]
interior Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set [a]
boundary
boundary' :: Set [a]
boundary' = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [ [a]
b' | [a]
b <- Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
boundary,
a
x <- [a]
b, a
y <- [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b,
let b' :: [a]
b' = a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
y (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
x [a]
b),
[a]
b' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set [a]
interior',
[a]
b' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set [a]
is' ]
in Set [a] -> Set [a] -> [[a]]
closure Set [a]
interior' Set [a]
boundary'
is' :: Set [a]
is' = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [[a]]
is
vectorMatroid :: (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid :: [[k]] -> Matroid Int
vectorMatroid = [[k]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' ([[k]] -> Matroid Int) -> ([[k]] -> [[k]]) -> [[k]] -> Matroid Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[k]] -> [[k]]
forall a. [[a]] -> [[a]]
L.transpose
vectorMatroid' :: (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' :: [[k]] -> Matroid Int
vectorMatroid' vs :: [[k]]
vs = [Int] -> [[Int]] -> Matroid Int
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases (((Int, [k]) -> Int) -> [(Int, [k])] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int, [k]) -> Int
forall a b. (a, b) -> a
fst [(Int, [k])]
forall a. (Num a, Enum a) => [(a, [k])]
vs') [[Int]]
forall a. (Enum a, Num a) => [[a]]
bs
where vs' :: [(a, [k])]
vs' = [a] -> [[k]] -> [(a, [k])]
forall a b. [a] -> [b] -> [(a, b)]
zip [1..] [[k]]
vs
bs :: [[a]]
bs = [[a]] -> [([a], [[k]], [(a, [k])])] -> [[a]]
forall a a.
(Eq a, Fractional a) =>
[[a]] -> [([a], [[a]], [(a, [a])])] -> [[a]]
dfs [] [([],[],[(a, [k])]
forall a. (Num a, Enum a) => [(a, [k])]
vs')]
dfs :: [[a]] -> [([a], [[a]], [(a, [a])])] -> [[a]]
dfs ls :: [[a]]
ls (r :: ([a], [[a]], [(a, [a])])
r@(i :: [a]
i,ref :: [[a]]
ref,es :: [(a, [a])]
es) : rs :: [([a], [[a]], [(a, [a])])]
rs) =
let succs :: [([a], [[a]], [(a, [a])])]
succs = ([a], [[a]], [(a, [a])]) -> [([a], [[a]], [(a, [a])])]
forall a a.
(Eq a, Fractional a) =>
([a], [[a]], [(a, [a])]) -> [([a], [[a]], [(a, [a])])]
successors ([a], [[a]], [(a, [a])])
r in
if [([a], [[a]], [(a, [a])])] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [([a], [[a]], [(a, [a])])]
succs then [[a]] -> [([a], [[a]], [(a, [a])])] -> [[a]]
dfs ([a]
i[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
ls) ([([a], [[a]], [(a, [a])])]
succs [([a], [[a]], [(a, [a])])]
-> [([a], [[a]], [(a, [a])])] -> [([a], [[a]], [(a, [a])])]
forall a. [a] -> [a] -> [a]
++ [([a], [[a]], [(a, [a])])]
rs) else [[a]] -> [([a], [[a]], [(a, [a])])] -> [[a]]
dfs [[a]]
ls ([([a], [[a]], [(a, [a])])]
succs [([a], [[a]], [(a, [a])])]
-> [([a], [[a]], [(a, [a])])] -> [([a], [[a]], [(a, [a])])]
forall a. [a] -> [a] -> [a]
++ [([a], [[a]], [(a, [a])])]
rs)
dfs ls :: [[a]]
ls [] = let r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> [a] -> Int
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall a. [a] -> a
last [[a]]
ls
in ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> [a]
forall a. [a] -> [a]
reverse ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
filter (\b :: [a]
b -> [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r) [[a]]
ls
successors :: ([a], [[a]], [(a, [a])]) -> [([a], [[a]], [(a, [a])])]
successors (i :: [a]
i,ref :: [[a]]
ref,es :: [(a, [a])]
es) = [([a]
i',[[a]]
ref',[(a, [a])]
es') | (j :: a
j,e :: [a]
e):es' :: [(a, [a])]
es' <- [(a, [a])] -> [[(a, [a])]]
forall a. [a] -> [[a]]
L.tails [(a, [a])]
es,
Bool -> Bool
not ([[a]] -> [a] -> Bool
forall a. (Eq a, Num a) => [[a]] -> [a] -> Bool
inSpanRE [[a]]
ref [a]
e),
let ref' :: [[a]]
ref' = [[a]] -> [[a]]
forall a. (Eq a, Fractional a) => [[a]] -> [[a]]
rowEchelonForm ([[a]]
ref [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]
e]),
let i' :: [a]
i' = a
j a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
i ]
cycleMatroid :: (Ord a) => [[a]] -> Matroid Int
cycleMatroid :: [[a]] -> Matroid Int
cycleMatroid es :: [[a]]
es = [Int] -> [[Int]] -> Matroid Int
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases (((Int, [a]) -> Int) -> [(Int, [a])] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int, [a]) -> Int
forall a b. (a, b) -> a
fst [(Int, [a])]
forall a. (Num a, Enum a) => [(a, [a])]
es') [[Int]]
forall a. (Num a, Enum a) => [[a]]
bs
where es' :: [(a, [a])]
es' = [a] -> [[a]] -> [(a, [a])]
forall a b. [a] -> [b] -> [(a, b)]
zip [1..] [[a]]
es
bs :: [[a]]
bs = [[a]] -> [([a], Map a a, [(a, [a])])] -> [[a]]
forall k a. Ord k => [[a]] -> [([a], Map k k, [(a, [k])])] -> [[a]]
dfs [] [([], Map a a
forall k a. Map k a
M.empty, [(a, [a])]
forall a. (Num a, Enum a) => [(a, [a])]
es')]
dfs :: [[a]] -> [([a], Map k k, [(a, [k])])] -> [[a]]
dfs ls :: [[a]]
ls (r :: ([a], Map k k, [(a, [k])])
r@(i :: [a]
i,ref :: Map k k
ref,es :: [(a, [k])]
es) : rs :: [([a], Map k k, [(a, [k])])]
rs) =
let succs :: [([a], Map k k, [(a, [k])])]
succs = ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
forall k a.
Ord k =>
([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors ([a], Map k k, [(a, [k])])
r
in if [([a], Map k k, [(a, [k])])] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [([a], Map k k, [(a, [k])])]
succs then [[a]] -> [([a], Map k k, [(a, [k])])] -> [[a]]
dfs ([a]
i[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
ls) ([([a], Map k k, [(a, [k])])]
succs [([a], Map k k, [(a, [k])])]
-> [([a], Map k k, [(a, [k])])] -> [([a], Map k k, [(a, [k])])]
forall a. [a] -> [a] -> [a]
++ [([a], Map k k, [(a, [k])])]
rs) else [[a]] -> [([a], Map k k, [(a, [k])])] -> [[a]]
dfs [[a]]
ls ([([a], Map k k, [(a, [k])])]
succs [([a], Map k k, [(a, [k])])]
-> [([a], Map k k, [(a, [k])])] -> [([a], Map k k, [(a, [k])])]
forall a. [a] -> [a] -> [a]
++ [([a], Map k k, [(a, [k])])]
rs)
dfs ls :: [[a]]
ls [] = let r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> [a] -> Int
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall a. [a] -> a
last [[a]]
ls
in ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> [a]
forall a. [a] -> [a]
reverse ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
filter (\b :: [a]
b -> [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r) [[a]]
ls
successors :: ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors (i :: [a]
i, reps :: Map k k
reps, (j :: a
j,[u :: k
u,v :: k
v]):es' :: [(a, [k])]
es' ) =
if k
u k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
v
then ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors ([a]
i, Map k k
reps, [(a, [k])]
es')
else case (k -> Map k k -> Maybe k
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup k
u Map k k
reps, k -> Map k k -> Maybe k
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup k
v Map k k
reps) of
(Nothing, Nothing) -> (a
ja -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
i, k -> k -> Map k k -> Map k k
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert k
u k
u (Map k k -> Map k k) -> Map k k -> Map k k
forall a b. (a -> b) -> a -> b
$ k -> k -> Map k k -> Map k k
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert k
v k
u Map k k
reps, [(a, [k])]
es') ([a], Map k k, [(a, [k])])
-> [([a], Map k k, [(a, [k])])] -> [([a], Map k k, [(a, [k])])]
forall a. a -> [a] -> [a]
: ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors ([a]
i, Map k k
reps, [(a, [k])]
es')
(Just u' :: k
u', Nothing) -> (a
ja -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
i, k -> k -> Map k k -> Map k k
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert k
v k
u' Map k k
reps, [(a, [k])]
es') ([a], Map k k, [(a, [k])])
-> [([a], Map k k, [(a, [k])])] -> [([a], Map k k, [(a, [k])])]
forall a. a -> [a] -> [a]
: ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors ([a]
i, Map k k
reps, [(a, [k])]
es')
(Nothing, Just v' :: k
v') -> (a
ja -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
i, k -> k -> Map k k -> Map k k
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert k
u k
v' Map k k
reps, [(a, [k])]
es') ([a], Map k k, [(a, [k])])
-> [([a], Map k k, [(a, [k])])] -> [([a], Map k k, [(a, [k])])]
forall a. a -> [a] -> [a]
: ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors ([a]
i, Map k k
reps, [(a, [k])]
es')
(Just u' :: k
u', Just v' :: k
v') -> if k
u' k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
v'
then ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors ([a]
i,Map k k
reps,[(a, [k])]
es')
else (a
ja -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
i, (k -> k) -> Map k k -> Map k k
forall a b k. (a -> b) -> Map k a -> Map k b
M.map (\w :: k
w -> if k
w k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
v' then k
u' else k
w) Map k k
reps, [(a, [k])]
es') ([a], Map k k, [(a, [k])])
-> [([a], Map k k, [(a, [k])])] -> [([a], Map k k, [(a, [k])])]
forall a. a -> [a] -> [a]
: ([a], Map k k, [(a, [k])]) -> [([a], Map k k, [(a, [k])])]
successors ([a]
i, Map k k
reps, [(a, [k])]
es')
successors (_, _, []) = []
cycleMatroid' :: [[a]] -> Matroid [a]
cycleMatroid' es :: [[a]]
es = (Int -> [a]) -> Matroid Int -> Matroid [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Int -> [a]
forall k. (Ord k, Num k, Enum k) => k -> [a]
lookupEdge (Matroid Int -> Matroid [a]) -> Matroid Int -> Matroid [a]
forall a b. (a -> b) -> a -> b
$ [[a]] -> Matroid Int
forall a. Ord a => [[a]] -> Matroid Int
cycleMatroid [[a]]
es
where table :: Map k [a]
table = [(k, [a])] -> Map k [a]
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(k, [a])] -> Map k [a]) -> [(k, [a])] -> Map k [a]
forall a b. (a -> b) -> a -> b
$ [k] -> [[a]] -> [(k, [a])]
forall a b. [a] -> [b] -> [(a, b)]
zip [1..] [[a]]
es
lookupEdge :: k -> [a]
lookupEdge = Map k [a] -> k -> [a]
forall k a. Ord k => Map k a -> k -> a
(M.!) Map k [a]
forall k. (Ord k, Num k, Enum k) => Map k [a]
table
to1n :: (Ord a) => Matroid a -> Matroid Int
to1n :: Matroid a -> Matroid Int
to1n m :: Matroid a
m = (a -> Int) -> Matroid a -> Matroid Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Int
forall a. (Num a, Enum a) => a -> a
to1n' Matroid a
m
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
table :: Map a a
table = [(a, a)] -> Map a a
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(a, a)] -> Map a a) -> [(a, a)] -> Map a a
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [(a, a)]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
es [1..]
to1n' :: a -> a
to1n' = Map a a -> a -> a
forall k a. Ord k => Map k a -> k -> a
(M.!) Map a a
forall a. (Num a, Enum a) => Map a a
table
incidenceGraphB :: Matroid t -> Graph (Either t [t])
incidenceGraphB m :: Matroid t
m = [Either t [t]] -> [[Either t [t]]] -> Graph (Either t [t])
forall a. [a] -> [[a]] -> Graph a
G.G [Either t [t]]
vs' [[Either t [t]]]
es'
where es :: [t]
es = Matroid t -> [t]
forall t. Matroid t -> [t]
elements Matroid t
m
bs :: [[t]]
bs = Matroid t -> [[t]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid t
m
vs' :: [Either t [t]]
vs' = (t -> Either t [t]) -> [t] -> [Either t [t]]
forall a b. (a -> b) -> [a] -> [b]
map t -> Either t [t]
forall a b. a -> Either a b
Left [t]
es [Either t [t]] -> [Either t [t]] -> [Either t [t]]
forall a. [a] -> [a] -> [a]
++ ([t] -> Either t [t]) -> [[t]] -> [Either t [t]]
forall a b. (a -> b) -> [a] -> [b]
map [t] -> Either t [t]
forall a b. b -> Either a b
Right [[t]]
bs
es' :: [[Either t [t]]]
es' = [[Either t [t]]] -> [[Either t [t]]]
forall a. Ord a => [a] -> [a]
L.sort [ [t -> Either t [t]
forall a b. a -> Either a b
Left t
e, [t] -> Either t [t]
forall a b. b -> Either a b
Right [t]
b] | [t]
b <- [[t]]
bs, t
e <- [t]
b ]
incidenceGraphC :: Matroid t -> Graph (Either t [t])
incidenceGraphC m :: Matroid t
m = [Either t [t]] -> [[Either t [t]]] -> Graph (Either t [t])
forall a. [a] -> [[a]] -> Graph a
G.G [Either t [t]]
vs' [[Either t [t]]]
es'
where es :: [t]
es = Matroid t -> [t]
forall t. Matroid t -> [t]
elements Matroid t
m
cs :: [[t]]
cs = [[t]] -> [[t]]
forall a. Ord a => [a] -> [a]
L.sort ([[t]] -> [[t]]) -> [[t]] -> [[t]]
forall a b. (a -> b) -> a -> b
$ Matroid t -> [[t]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid t
m
vs' :: [Either t [t]]
vs' = (t -> Either t [t]) -> [t] -> [Either t [t]]
forall a b. (a -> b) -> [a] -> [b]
map t -> Either t [t]
forall a b. a -> Either a b
Left [t]
es [Either t [t]] -> [Either t [t]] -> [Either t [t]]
forall a. [a] -> [a] -> [a]
++ ([t] -> Either t [t]) -> [[t]] -> [Either t [t]]
forall a b. (a -> b) -> [a] -> [b]
map [t] -> Either t [t]
forall a b. b -> Either a b
Right [[t]]
cs
es' :: [[Either t [t]]]
es' = [[Either t [t]]] -> [[Either t [t]]]
forall a. Ord a => [a] -> [a]
L.sort [ [t -> Either t [t]
forall a b. a -> Either a b
Left t
e, [t] -> Either t [t]
forall a b. b -> Either a b
Right [t]
c] | [t]
c <- [[t]]
cs, t
e <- [t]
c ]
incidenceGraphH :: Matroid t -> Graph (Either t [t])
incidenceGraphH m :: Matroid t
m = [Either t [t]] -> [[Either t [t]]] -> Graph (Either t [t])
forall a. [a] -> [[a]] -> Graph a
G.G [Either t [t]]
vs' [[Either t [t]]]
es'
where es :: [t]
es = Matroid t -> [t]
forall t. Matroid t -> [t]
elements Matroid t
m
hs :: [[t]]
hs = [[t]] -> [[t]]
forall a. Ord a => [a] -> [a]
L.sort ([[t]] -> [[t]]) -> [[t]] -> [[t]]
forall a b. (a -> b) -> a -> b
$ Matroid t -> [[t]]
forall a. Ord a => Matroid a -> [[a]]
hyperplanes Matroid t
m
vs' :: [Either t [t]]
vs' = (t -> Either t [t]) -> [t] -> [Either t [t]]
forall a b. (a -> b) -> [a] -> [b]
map t -> Either t [t]
forall a b. a -> Either a b
Left [t]
es [Either t [t]] -> [Either t [t]] -> [Either t [t]]
forall a. [a] -> [a] -> [a]
++ ([t] -> Either t [t]) -> [[t]] -> [Either t [t]]
forall a b. (a -> b) -> [a] -> [b]
map [t] -> Either t [t]
forall a b. b -> Either a b
Right [[t]]
hs
es' :: [[Either t [t]]]
es' = [[Either t [t]]] -> [[Either t [t]]]
forall a. Ord a => [a] -> [a]
L.sort [ [t -> Either t [t]
forall a b. a -> Either a b
Left t
e, [t] -> Either t [t]
forall a b. b -> Either a b
Right [t]
h] | [t]
h <- [[t]]
hs, t
e <- [t]
h ]
matroidIsos :: Matroid a -> Matroid b2 -> [[(a, b2)]]
matroidIsos m1 :: Matroid a
m1 m2 :: Matroid b2
m2 = Graph (Either a [a]) -> Graph (Either b2 [b2]) -> [[(a, b2)]]
forall a b1 b2 b3.
(Ord b2, Ord b3, Ord a, Ord b1) =>
Graph (Either a b1) -> Graph (Either b2 b3) -> [[(a, b2)]]
incidenceIsos (Matroid a -> Graph (Either a [a])
forall t. Ord t => Matroid t -> Graph (Either t [t])
incidenceGraphH Matroid a
m1) (Matroid b2 -> Graph (Either b2 [b2])
forall t. Ord t => Matroid t -> Graph (Either t [t])
incidenceGraphH Matroid b2
m2)
isMatroidIso :: (Ord a, Ord b) => Matroid a -> Matroid b -> Bool
isMatroidIso :: Matroid a -> Matroid b -> Bool
isMatroidIso m1 :: Matroid a
m1 m2 :: Matroid b
m2 = Graph (Either a [a]) -> Graph (Either b [b]) -> Bool
forall p1 b1 p2 b2.
(Ord p1, Ord b1, Ord p2, Ord b2) =>
Graph (Either p1 b1) -> Graph (Either p2 b2) -> Bool
isIncidenceIso (Matroid a -> Graph (Either a [a])
forall t. Ord t => Matroid t -> Graph (Either t [t])
incidenceGraphH Matroid a
m1) (Matroid b -> Graph (Either b [b])
forall t. Ord t => Matroid t -> Graph (Either t [t])
incidenceGraphH Matroid b
m2)
matroidAuts :: (Ord a) => Matroid a -> [Permutation a]
matroidAuts :: Matroid a -> [Permutation a]
matroidAuts m :: Matroid a
m = Graph (Either a [a]) -> [Permutation a]
forall p b. (Ord p, Ord b) => Graph (Either p b) -> [Permutation p]
incidenceAuts (Graph (Either a [a]) -> [Permutation a])
-> Graph (Either a [a]) -> [Permutation a]
forall a b. (a -> b) -> a -> b
$ Matroid a -> Graph (Either a [a])
forall t. Ord t => Matroid t -> Graph (Either t [t])
incidenceGraphH Matroid a
m
isCircuit :: (Ord a) => Matroid a -> [a] -> Bool
isCircuit :: Matroid a -> [a] -> Bool
isCircuit m :: Matroid a
m c :: [a]
c =
Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isDependent Matroid a
m [a]
c Bool -> Bool -> Bool
&&
([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isIndependent Matroid a
m) ([a] -> [[a]]
forall a. [a] -> [[a]]
deletions [a]
c)
circuits :: (Ord a) => Matroid a -> [[a]]
circuits :: Matroid a -> [[a]]
circuits m :: Matroid a
m = [[a]] -> [[a]]
forall (t :: * -> *) a. (Ord (t a), Foldable t) => [t a] -> [t a]
toShortlex ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ Set [a] -> [[a]] -> [[a]]
dfs Set [a]
forall a. Set a
S.empty [a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
e [a]
b | [a]
b <- [[a]]
bs, a
e <- [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b]
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
bs :: [[a]]
bs = Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
dfs :: Set [a] -> [[a]] -> [[a]]
dfs vs :: Set [a]
vs (c :: [a]
c:cs :: [[a]]
cs) | [a]
c [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set [a]
vs = Set [a] -> [[a]] -> [[a]]
dfs Set [a]
vs [[a]]
cs
| Bool
otherwise = let cs' :: [[a]]
cs' = [a] -> [[a]]
successors [a]
c
vs' :: Set [a]
vs' = [a] -> Set [a] -> Set [a]
forall a. Ord a => a -> Set a -> Set a
S.insert [a]
c Set [a]
vs
in if [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [[a]]
cs' then [a]
c [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: Set [a] -> [[a]] -> [[a]]
dfs Set [a]
vs' [[a]]
cs else Set [a] -> [[a]] -> [[a]]
dfs Set [a]
vs' ([[a]]
cs' [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]]
cs)
dfs _ [] = []
successors :: [a] -> [[a]]
successors c :: [a]
c = [[a]
c' | [a]
c' <- [a] -> [[a]]
forall a. [a] -> [[a]]
deletions [a]
c, Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isDependent Matroid a
m [a]
c' ]
isMatroidCircuits :: (Ord a) => [[a]] -> Bool
isMatroidCircuits :: [[a]] -> Bool
isMatroidCircuits cs :: [[a]]
cs =
[] [a] -> [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [[a]]
cs Bool -> Bool -> Bool
&&
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [([a]
c1 [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
c2) Bool -> Bool -> Bool
`implies` ([a]
c1 [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
c2) | [a]
c1 <- [[a]]
cs, [a]
c2 <- [[a]]
cs] Bool -> Bool -> Bool
&&
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
exists [[a]
c3 | [a]
c3 <- [[a]]
cs, [a]
c3 [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
c12']
| [a]
c1 <- [[a]]
cs, [a]
c2 <- [[a]]
cs, [a]
c1 [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
/= [a]
c2,
a
e <- [a]
c1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
c2, let c12' :: [a]
c12' = a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
e ([a]
c1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.union` [a]
c2)]
fromCircuits :: (Ord a) => [a] -> [[a]] -> Matroid a
fromCircuits :: [a] -> [[a]] -> Matroid a
fromCircuits es :: [a]
es cs :: [[a]]
cs = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
where b :: [a]
b = [a] -> [a] -> [a]
greedy [] [a]
es
greedy :: [a] -> [a] -> [a]
greedy ls :: [a]
ls (r :: a
r:rs :: [a]
rs) = let ls' :: [a]
ls' = [a]
ls [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
r] in
if [a] -> Bool
isIndep [a]
ls'
then [a] -> [a] -> [a]
greedy [a]
ls' [a]
rs
else [a] -> [a] -> [a]
greedy [a]
ls [a]
rs
greedy ls :: [a]
ls [] = [a]
ls
bs :: [[a]]
bs = Set [a] -> Set [a] -> [[a]]
closure Set [a]
forall a. Set a
S.empty ([a] -> Set [a]
forall a. a -> Set a
S.singleton [a]
b)
closure :: Set [a] -> Set [a] -> [[a]]
closure interior :: Set [a]
interior boundary :: Set [a]
boundary =
if Set [a] -> Bool
forall a. Set a -> Bool
S.null Set [a]
boundary
then Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
interior
else let interior' :: Set [a]
interior' = Set [a]
interior Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set [a]
boundary
boundary' :: Set [a]
boundary' = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [ [a]
b' | [a]
b <- Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
boundary,
a
x <- [a]
b, a
y <- [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b,
let b' :: [a]
b' = a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
y (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
x [a]
b),
[a]
b' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set [a]
interior',
[a] -> Bool
isIndep [a]
b' ]
in Set [a] -> Set [a] -> [[a]]
closure Set [a]
interior' Set [a]
boundary'
isIndep :: [a] -> Bool
isIndep xs :: [a]
xs = Bool -> Bool
not (([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ([a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
xs) [[a]]
cs)
isLoop :: (Ord a) => Matroid a -> a -> Bool
isLoop :: Matroid a -> a -> Bool
isLoop m :: Matroid a
m e :: a
e = Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isCircuit Matroid a
m [a
e]
isParallel :: (Ord a) => Matroid a -> a -> a -> Bool
isParallel :: Matroid a -> a -> a -> Bool
isParallel m :: Matroid a
m f :: a
f g :: a
g = Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isCircuit Matroid a
m [a
f,a
g]
isSimple :: (Ord a) => Matroid a -> Bool
isSimple :: Matroid a -> Bool
isSimple m :: Matroid a
m = ([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ( (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>2) (Int -> Bool) -> ([a] -> Int) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ) (Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m)
isBase :: (Ord a) => Matroid a -> [a] -> Bool
isBase :: Matroid a -> [a] -> Bool
isBase (M es :: [a]
es bs :: TrieSet a
bs) b :: [a]
b = [a]
b [a] -> TrieSet a -> Bool
forall a. Eq a => [a] -> TrieSet a -> Bool
`tsmember` TrieSet a
bs
bases :: (Ord a) => Matroid a -> [[a]]
bases :: Matroid a -> [[a]]
bases (M es :: [a]
es bs :: TrieSet a
bs) = TrieSet a -> [[a]]
forall a. TrieSet a -> [[a]]
tstolist TrieSet a
bs
isMatroidBases :: (Ord a) => [[a]] -> Bool
isMatroidBases :: [[a]] -> Bool
isMatroidBases bs :: [[a]]
bs =
(Bool -> Bool
not (Bool -> Bool) -> ([[a]] -> Bool) -> [[a]] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null) [[a]]
bs Bool -> Bool -> Bool
&&
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
exists [a
y | a
y <- [a]
b2 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b1, a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
y (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
x [a]
b1) [a] -> [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [[a]]
bs]
| [a]
b1 <- [[a]]
bs, [a]
b2 <- [[a]]
bs, a
x <- [a]
b1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b2 ]
fromBases :: (Ord a) => [a] -> [[a]] -> Matroid a
fromBases :: [a] -> [[a]] -> Matroid a
fromBases es :: [a]
es bs :: [[a]]
bs = [a] -> TrieSet a -> Matroid a
forall a. [a] -> TrieSet a -> Matroid a
M [a]
es ([[a]] -> TrieSet a
forall (t :: * -> *) a. (Foldable t, Ord a) => t [a] -> TrieSet a
tsfromlist [[a]]
bs)
fundamentalCircuit :: (Ord a) => Matroid a -> [a] -> a -> [a]
fundamentalCircuit :: Matroid a -> [a] -> a -> [a]
fundamentalCircuit m :: Matroid a
m b :: [a]
b e :: a
e = [[a]] -> [a]
forall a. [a] -> a
unique [[a]
c | [a]
c <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m, [a]
c [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
be]
where be :: [a]
be = a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
e [a]
b
uniformMatroid :: Int -> Int -> Matroid Int
uniformMatroid m :: Int
m n :: Int
n | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
n = [Int] -> [[Int]] -> Matroid Int
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [Int]
es [[Int]]
bs
where es :: [Int]
es = [1..Int
n]
bs :: [[Int]]
bs = Int -> [Int] -> [[Int]]
forall a. Int -> [a] -> [[a]]
combinationsOf Int
m [Int]
es
u :: Int -> Int -> Matroid Int
u :: Int -> Int -> Matroid Int
u = Int -> Int -> Matroid Int
uniformMatroid
restriction1 :: Matroid a -> [a] -> Matroid a
restriction1 m :: Matroid a
m xs :: [a]
xs = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
xs [[a]]
bs'
where bs :: [[a]]
bs = Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
is' :: [[a]]
is' = [[a]] -> [[a]]
forall (t :: * -> *) a. (Ord (t a), Foldable t) => [t a] -> [t a]
toShortlex [[a]
b [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
xs | [a]
b <- [[a]]
bs]
r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> [a] -> Int
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall a. [a] -> a
last [[a]]
is'
bs' :: [[a]]
bs' = ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile ( (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r) (Int -> Bool) -> ([a] -> Int) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ) [[a]]
is'
restriction :: (Ord a) => Matroid a -> [a] -> Matroid a
restriction :: Matroid a -> [a] -> Matroid a
restriction m :: Matroid a
m@(M es :: [a]
es bs :: TrieSet a
bs) xs :: [a]
xs = [a] -> TrieSet a -> Matroid a
forall a. [a] -> TrieSet a -> Matroid a
M [a]
xs TrieSet a
bs'
where (_,bs' :: TrieSet a
bs') = TrieSet a -> (Integer, TrieSet a)
forall a a. (Ord a, Ord a, Num a) => TrieSet a -> (a, TrieSet a)
balance (TrieSet a -> (Integer, TrieSet a))
-> TrieSet a -> (Integer, TrieSet a)
forall a b. (a -> b) -> a -> b
$ TrieSet a -> TrieSet a
prune TrieSet a
bs
prune :: TrieSet a -> TrieSet a
prune (TS yts :: [(a, TrieSet a)]
yts) = let (ins :: [(a, TrieSet a)]
ins, outs :: [(a, TrieSet a)]
outs) = ((a, TrieSet a) -> Bool)
-> [(a, TrieSet a)] -> ([(a, TrieSet a)], [(a, TrieSet a)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
L.partition (\(y :: a
y,t :: TrieSet a
t) -> a
y a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
xs) [(a, TrieSet a)]
yts
ins' :: [(a, TrieSet a)]
ins' = [(a
y, TrieSet a -> TrieSet a
prune TrieSet a
t) | (y :: a
y,t :: TrieSet a
t) <- [(a, TrieSet a)]
ins]
outs' :: [(a, TrieSet a)]
outs' = [[(a, TrieSet a)]] -> [(a, TrieSet a)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [ [(a, TrieSet a)]
zts | (y :: a
y,t :: TrieSet a
t) <- [(a, TrieSet a)]
outs, let TS zts :: [(a, TrieSet a)]
zts = TrieSet a -> TrieSet a
prune TrieSet a
t ]
in [(a, TrieSet a)] -> TrieSet a
forall a. [(a, TrieSet a)] -> TrieSet a
TS ([(a, TrieSet a)] -> TrieSet a) -> [(a, TrieSet a)] -> TrieSet a
forall a b. (a -> b) -> a -> b
$ [(a, TrieSet a)]
ins' [(a, TrieSet a)] -> [(a, TrieSet a)] -> [(a, TrieSet a)]
forall a. [a] -> [a] -> [a]
++ [(a, TrieSet a)]
outs'
balance :: TrieSet a -> (a, TrieSet a)
balance (TS yts :: [(a, TrieSet a)]
yts) = let dyt's :: [(a, (a, TrieSet a))]
dyt's = [(a
d',(a
y,TrieSet a
t')) | (y :: a
y,t :: TrieSet a
t) <- [(a, TrieSet a)]
yts, let (d' :: a
d',t' :: TrieSet a
t') = TrieSet a -> (a, TrieSet a)
balance TrieSet a
t]
d :: a
d = [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$ 0 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ((a, (a, TrieSet a)) -> a) -> [(a, (a, TrieSet a))] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a, (a, TrieSet a)) -> a
forall a b. (a, b) -> a
fst [(a, (a, TrieSet a))]
dyt's
in (a
da -> a -> a
forall a. Num a => a -> a -> a
+1, [(a, TrieSet a)] -> TrieSet a
forall a. [(a, TrieSet a)] -> TrieSet a
TS ([(a, TrieSet a)] -> TrieSet a) -> [(a, TrieSet a)] -> TrieSet a
forall a b. (a -> b) -> a -> b
$ [(a, TrieSet a)] -> [(a, TrieSet a)]
forall a. Ord a => [a] -> [a]
toSet [(a
y,TrieSet a
t') | (d' :: a
d',(y :: a
y,t' :: TrieSet a
t')) <- [(a, (a, TrieSet a))]
dyt's, a
d' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
d])
rankfun :: (Ord a) => Matroid a -> [a] -> Int
rankfun :: Matroid a -> [a] -> Int
rankfun m :: Matroid a
m xs :: [a]
xs = ([a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> (Matroid a -> [a]) -> Matroid a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[a]] -> [a]
forall a. [a] -> a
head ([[a]] -> [a]) -> (Matroid a -> [[a]]) -> Matroid a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases) (Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
restriction Matroid a
m [a]
xs)
rank :: (Ord a) => Matroid a -> Int
rank :: Matroid a -> Int
rank m :: Matroid a
m = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> [a] -> Int
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall a. [a] -> a
head ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
fromRankfun :: (Ord a) => [a] -> ([a] -> Int) -> Matroid a
fromRankfun :: [a] -> ([a] -> Int) -> Matroid a
fromRankfun es :: [a]
es rkf :: [a] -> Int
rkf = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
where b :: [a]
b = Int -> [a] -> [a] -> [a]
greedy 0 [] [a]
es
greedy :: Int -> [a] -> [a] -> [a]
greedy rk :: Int
rk ls :: [a]
ls (r :: a
r:rs :: [a]
rs) = let ls' :: [a]
ls' = [a]
ls [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
r] in
if [a] -> Int
rkf [a]
ls' Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
rkInt -> Int -> Int
forall a. Num a => a -> a -> a
+1
then Int -> [a] -> [a] -> [a]
greedy (Int
rkInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) [a]
ls' [a]
rs
else Int -> [a] -> [a] -> [a]
greedy Int
rk [a]
ls [a]
rs
greedy _ ls :: [a]
ls [] = [a]
ls
rk :: Int
rk = [a] -> Int
rkf [a]
b
isBasis :: [a] -> Bool
isBasis b' :: [a]
b' = [a] -> Int
rkf [a]
b' Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
rk
bs :: [[a]]
bs = Set [a] -> Set [a] -> Set [a] -> [[a]]
closure Set [a]
forall a. Set a
S.empty ([a] -> Set [a]
forall a. a -> Set a
S.singleton [a]
b) Set [a]
forall a. Set a
S.empty
closure :: Set [a] -> Set [a] -> Set [a] -> [[a]]
closure interior :: Set [a]
interior boundary :: Set [a]
boundary exterior :: Set [a]
exterior =
if Set [a] -> Bool
forall a. Set a -> Bool
S.null Set [a]
boundary
then Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
interior
else let interior' :: Set [a]
interior' = Set [a]
interior Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set [a]
boundary
candidates :: Set [a]
candidates = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [ [a]
b' | [a]
b <- Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
boundary,
a
x <- [a]
b, a
y <- [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b,
let b' :: [a]
b' = a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
y (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
x [a]
b),
[a]
b' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set [a]
interior',
[a]
b' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set [a]
exterior ]
(boundary' :: Set [a]
boundary', exterior' :: Set [a]
exterior') = ([a] -> Bool) -> Set [a] -> (Set [a], Set [a])
forall a. (a -> Bool) -> Set a -> (Set a, Set a)
S.partition [a] -> Bool
isBasis Set [a]
candidates
in Set [a] -> Set [a] -> Set [a] -> [[a]]
closure Set [a]
interior' Set [a]
boundary' (Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
S.union Set [a]
exterior Set [a]
exterior')
closure :: (Ord a) => Matroid a -> [a] -> [a]
closure :: Matroid a -> [a] -> [a]
closure m :: Matroid a
m xs :: [a]
xs = [a
x | a
x <- [a]
es, a
x a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
xs Bool -> Bool -> Bool
|| Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m (a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
x [a]
xs) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
rankxs]
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
rankxs :: Int
rankxs = Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m [a]
xs
fromClosure :: (Ord a) => [a] -> ([a] -> [a]) -> Matroid a
fromClosure :: [a] -> ([a] -> [a]) -> Matroid a
fromClosure es :: [a]
es cl :: [a] -> [a]
cl = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
where b :: [a]
b = [a] -> [a] -> [a] -> [a]
greedy ([a] -> [a]
cl []) [] [a]
es
greedy :: [a] -> [a] -> [a] -> [a]
greedy span :: [a]
span ls :: [a]
ls (r :: a
r:rs :: [a]
rs) = let ls' :: [a]
ls' = [a]
ls [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
r] in
if a
r a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [a]
span
then [a] -> [a] -> [a] -> [a]
greedy ([a] -> [a]
cl [a]
ls') [a]
ls' [a]
rs
else [a] -> [a] -> [a] -> [a]
greedy [a]
span [a]
ls [a]
rs
greedy _ ls :: [a]
ls [] = [a]
ls
rk :: Int
rk = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
b
isBasis :: [a] -> Bool
isBasis b' :: [a]
b' = [a] -> [a]
cl [a]
b' [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
es
bs :: [[a]]
bs = Set [a] -> Set [a] -> Set [a] -> [[a]]
closure Set [a]
forall a. Set a
S.empty ([a] -> Set [a]
forall a. a -> Set a
S.singleton [a]
b) Set [a]
forall a. Set a
S.empty
closure :: Set [a] -> Set [a] -> Set [a] -> [[a]]
closure interior :: Set [a]
interior boundary :: Set [a]
boundary exterior :: Set [a]
exterior =
if Set [a] -> Bool
forall a. Set a -> Bool
S.null Set [a]
boundary
then Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
interior
else let interior' :: Set [a]
interior' = Set [a]
interior Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set [a]
boundary
candidates :: Set [a]
candidates = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [ [a]
b' | [a]
b <- Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
boundary,
a
x <- [a]
b, a
y <- [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b,
let b' :: [a]
b' = a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
y (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
x [a]
b),
[a]
b' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set [a]
interior',
[a]
b' [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set [a]
exterior ]
(boundary' :: Set [a]
boundary', exterior' :: Set [a]
exterior') = ([a] -> Bool) -> Set [a] -> (Set [a], Set [a])
forall a. (a -> Bool) -> Set a -> (Set a, Set a)
S.partition [a] -> Bool
isBasis Set [a]
candidates
in Set [a] -> Set [a] -> Set [a] -> [[a]]
closure Set [a]
interior' Set [a]
boundary' (Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
S.union Set [a]
exterior Set [a]
exterior')
isFlat :: (Ord a) => Matroid a -> [a] -> Bool
isFlat :: Matroid a -> [a] -> Bool
isFlat m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> [a]
forall a. Ord a => Matroid a -> [a] -> [a]
closure Matroid a
m [a]
xs [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
xs
flats1 :: Matroid a -> [[a]]
flats1 m :: Matroid a
m = [[a]
xs | [a]
xs <- [a] -> [[a]]
forall a. [a] -> [[a]]
powersetbfs [a]
es, Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isFlat Matroid a
m [a]
xs]
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
coveringFlats :: Matroid a -> [a] -> [[a]]
coveringFlats m :: Matroid a
m xs :: [a]
xs = [a] -> [[a]]
coveringFlats' ([a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
xs)
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
coveringFlats' :: [a] -> [[a]]
coveringFlats' (y :: a
y:ys :: [a]
ys) = let zs :: [a]
zs = Matroid a -> [a] -> [a]
forall a. Ord a => Matroid a -> [a] -> [a]
closure Matroid a
m (a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
y [a]
xs)
in [a]
zs [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: [a] -> [[a]]
coveringFlats' ([a]
ys [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
zs)
coveringFlats' [] = []
minimalFlat :: Matroid a -> [a]
minimalFlat m :: Matroid a
m = [[a]] -> [a]
forall a. [a] -> a
head ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$ ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
filter (Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isFlat Matroid a
m) ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [a] -> [[a]]
forall a. [a] -> [[a]]
powersetbfs ([a] -> [[a]]) -> [a] -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
flats :: (Ord a) => Matroid a -> [[a]]
flats :: Matroid a -> [[a]]
flats m :: Matroid a
m = Set [a] -> [[a]] -> [[a]]
flats' Set [a]
forall a. Set a
S.empty [Matroid a -> [a]
forall a. Ord a => Matroid a -> [a]
minimalFlat Matroid a
m]
where flats' :: Set [a] -> [[a]] -> [[a]]
flats' ls :: Set [a]
ls (r :: [a]
r:rs :: [[a]]
rs) = if [a]
r [a] -> Set [a] -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set [a]
ls
then Set [a] -> [[a]] -> [[a]]
flats' Set [a]
ls [[a]]
rs
else Set [a] -> [[a]] -> [[a]]
flats' ([a] -> Set [a] -> Set [a]
forall a. Ord a => a -> Set a -> Set a
S.insert [a]
r Set [a]
ls) ([[a]]
rs [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ Matroid a -> [a] -> [[a]]
forall a. Ord a => Matroid a -> [a] -> [[a]]
coveringFlats Matroid a
m [a]
r)
flats' ls :: Set [a]
ls [] = [[a]] -> [[a]]
forall (t :: * -> *) a. (Ord (t a), Foldable t) => [t a] -> [t a]
toShortlex ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
ls
fromFlats :: (Ord a) => [[a]] -> Matroid a
fromFlats :: [[a]] -> Matroid a
fromFlats fs :: [[a]]
fs | [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Ord (t a)) => [t a] -> Bool
isShortlex [[a]]
fs = [[a]] -> Matroid a
forall a. Ord a => [[a]] -> Matroid a
fromFlats' [[a]]
fs
| Bool
otherwise = [Char] -> Matroid a
forall a. HasCallStack => [Char] -> a
error "fromFlats: flats must be in shortlex order"
fromFlats' :: [[a]] -> Matroid a
fromFlats' fs :: [[a]]
fs = [a] -> ([a] -> [a]) -> Matroid a
forall a. Ord a => [a] -> ([a] -> [a]) -> Matroid a
fromClosure [a]
es [a] -> [a]
cl
where es :: [a]
es = [[a]] -> [a]
forall a. [a] -> a
last [[a]]
fs
cl :: [a] -> [a]
cl xs :: [a]
xs = [[a]] -> [a]
forall a. [a] -> a
head [[a]
f | [a]
f <- [[a]]
fs, [a]
xs [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
f]
isSpanning :: (Ord a) => Matroid a -> [a] -> Bool
isSpanning :: Matroid a -> [a] -> Bool
isSpanning m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> [a]
forall a. Ord a => Matroid a -> [a] -> [a]
closure Matroid a
m [a]
xs [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
es
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
isHyperplane :: (Ord a) => Matroid a -> [a] -> Bool
isHyperplane :: Matroid a -> [a] -> Bool
isHyperplane m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isFlat Matroid a
m [a]
xs Bool -> Bool -> Bool
&& Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m [a]
xs Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Matroid a -> Int
forall a. Ord a => Matroid a -> Int
rank Matroid a
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1
hyperplanes1 :: Matroid a -> [[a]]
hyperplanes1 m :: Matroid a
m = [[a]
h | [a]
h <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
flats Matroid a
m, Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m [a]
h Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
rk Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1]
where rk :: Int
rk = Matroid a -> Int
forall a. Ord a => Matroid a -> Int
rank Matroid a
m
hyperplanes :: (Ord a) => Matroid a -> [[a]]
hyperplanes :: Matroid a -> [[a]]
hyperplanes m :: Matroid a
m = [[a]] -> [[a]]
forall (t :: * -> *) a. (Ord (t a), Foldable t) => [t a] -> [t a]
toShortlex ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> [a]
complement ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
cocircuits Matroid a
m
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
complement :: [a] -> [a]
complement cc :: [a]
cc = [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
cc
isMatroidHyperplanes :: (Ord a) => [a] -> [[a]] -> Bool
isMatroidHyperplanes :: [a] -> [[a]] -> Bool
isMatroidHyperplanes es :: [a]
es hs :: [[a]]
hs =
[a]
es [a] -> [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [[a]]
hs Bool -> Bool -> Bool
&&
[[a]] -> Bool
forall a. Ord a => [[a]] -> Bool
isClutter [[a]]
hs Bool -> Bool -> Bool
&&
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
exists [[a]
h3 | [a]
h3 <- [[a]]
hs, [a]
h12e [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
h3] | (h1 :: [a]
h1,h2 :: [a]
h2) <- [[a]] -> [([a], [a])]
forall t. [t] -> [(t, t)]
pairs [[a]]
hs,
a
e <- [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ ([a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.union [a]
h1 [a]
h2),
let h12e :: [a]
h12e = a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
L.insert a
e ([a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.intersect [a]
h1 [a]
h2) ]
fromHyperplanes1 :: [a] -> [[a]] -> Matroid a
fromHyperplanes1 es :: [a]
es hs :: [[a]]
hs = [[a]] -> Matroid a
forall a. Ord a => [[a]] -> Matroid a
fromFlats ([[a]] -> Matroid a) -> [[a]] -> Matroid a
forall a b. (a -> b) -> a -> b
$ Set [a] -> Set [a] -> [[a]]
closure Set [a]
forall a. Set a
S.empty ([[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [[a]]
hs)
where closure :: Set [a] -> Set [a] -> [[a]]
closure interior :: Set [a]
interior boundary :: Set [a]
boundary =
if Set [a] -> Bool
forall a. Set a -> Bool
S.null Set [a]
boundary
then ([[a]] -> [[a]]
forall (t :: * -> *) a. (Ord (t a), Foldable t) => [t a] -> [t a]
toShortlex ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
interior) [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]
es]
else let interior' :: Set [a]
interior' = Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
S.union Set [a]
interior Set [a]
boundary
boundary' :: Set [a]
boundary' = [[a]] -> Set [a]
forall a. Ord a => [a] -> Set a
S.fromList [ [a]
f1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
f2 | (f1 :: [a]
f1,f2 :: [a]
f2) <- [[a]] -> [([a], [a])]
forall t. [t] -> [(t, t)]
pairs (Set [a] -> [[a]]
forall a. Set a -> [a]
S.toList Set [a]
boundary) ]
Set [a] -> Set [a] -> Set [a]
forall a. Ord a => Set a -> Set a -> Set a
S.\\ Set [a]
interior'
in Set [a] -> Set [a] -> [[a]]
closure Set [a]
interior' Set [a]
boundary'
fromHyperplanes :: (Ord a) => [a] -> [[a]] -> Matroid a
fromHyperplanes :: [a] -> [[a]] -> Matroid a
fromHyperplanes es :: [a]
es hs :: [[a]]
hs = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromCocircuits [a]
es ([[a]] -> Matroid a) -> [[a]] -> Matroid a
forall a b. (a -> b) -> a -> b
$ ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> [a]
complement [[a]]
hs
where fromCocircuits :: [a] -> [[a]] -> Matroid a
fromCocircuits es :: [a]
es = Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual (Matroid a -> Matroid a)
-> ([[a]] -> Matroid a) -> [[a]] -> Matroid a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromCircuits [a]
es
complement :: [a] -> [a]
complement xs :: [a]
xs = [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
xs
affineMatroid :: (Eq k, Fractional k) => [[k]] -> Matroid Int
affineMatroid :: [[k]] -> Matroid Int
affineMatroid vs :: [[k]]
vs = [[k]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' ([[k]] -> Matroid Int) -> [[k]] -> Matroid Int
forall a b. (a -> b) -> a -> b
$ ([k] -> [k]) -> [[k]] -> [[k]]
forall a b. (a -> b) -> [a] -> [b]
map (1k -> [k] -> [k]
forall a. a -> [a] -> [a]
:) [[k]]
vs
fromGeoRep :: (Ord a) => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep :: [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep loops :: [[a]]
loops points :: [[a]]
points lines :: [[a]]
lines planes :: [[a]]
planes =
[a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromCircuits [a]
es ([[a]] -> Matroid a) -> [[a]] -> Matroid a
forall a b. (a -> b) -> a -> b
$ [[a]] -> [[a]]
forall a. Ord a => [[a]] -> [[a]]
minimal ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$
[[a]]
loops [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++
([a] -> [[a]]) -> [[a]] -> [[a]]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinationsOf 2) [[a]]
points [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++
([a] -> [[a]]) -> [[a]] -> [[a]]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinationsOf 3) [[a]]
lines [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++
([a] -> [[a]]) -> [[a]] -> [[a]]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinationsOf 4) [[a]]
planes [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++
Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinationsOf 5 [a]
es
where es :: [a]
es = [a] -> [a]
forall a. Ord a => [a] -> [a]
toSet ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[a]]
loops [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[a]]
points [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[a]]
lines [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[a]]
planes
minimal :: [[a]] -> [[a]]
minimal xss :: [[a]]
xss = [[a]] -> [[a]] -> [[a]]
forall a. Ord a => [[a]] -> [[a]] -> [[a]]
minimal' [] [[a]]
xss
where minimal' :: [[a]] -> [[a]] -> [[a]]
minimal' ls :: [[a]]
ls (r :: [a]
r:rs :: [[a]]
rs) = if ([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ([a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
r) [[a]]
ls
then [[a]] -> [[a]] -> [[a]]
minimal' [[a]]
ls [[a]]
rs
else [[a]] -> [[a]] -> [[a]]
minimal' ([a]
r[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
ls) [[a]]
rs
minimal' ls :: [[a]]
ls [] = [[a]] -> [[a]]
forall a. [a] -> [a]
reverse [[a]]
ls
simpleFromGeoRep :: (Ord a) => [[a]] -> [[a]] -> Matroid a
simpleFromGeoRep :: [[a]] -> [[a]] -> Matroid a
simpleFromGeoRep lines :: [[a]]
lines planes :: [[a]]
planes = [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
forall a. Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep [] [] [[a]]
lines [[a]]
planes
isSimpleGeoRep :: [[a]] -> [[a]] -> Bool
isSimpleGeoRep lines :: [[a]]
lines planes :: [[a]]
planes =
([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ( (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 1) (Int -> Bool) -> ([a] -> Int) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ) [ [a]
l1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
l2 | (l1 :: [a]
l1,l2 :: [a]
l2) <- [[a]] -> [([a], [a])]
forall t. [t] -> [(t, t)]
pairs [[a]]
lines ] Bool -> Bool -> Bool
&&
([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ( \i :: [a]
i -> [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 2 Bool -> Bool -> Bool
|| [a]
i [a] -> [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [[a]]
lines ) [ [a]
p1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
p2 | (p1 :: [a]
p1,p2 :: [a]
p2) <- [[a]] -> [([a], [a])]
forall t. [t] -> [(t, t)]
pairs [[a]]
planes ] Bool -> Bool -> Bool
&&
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ ([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ([a]
u [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset`) [[a]]
planes | (l1 :: [a]
l1,l2 :: [a]
l2) <- [[a]] -> [([a], [a])]
forall t. [t] -> [(t, t)]
pairs [[a]]
lines, [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a]
l1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
l2) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1, let u :: [a]
u = [a]
l1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.union` [a]
l2 ] Bool -> Bool -> Bool
&&
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 Bool -> Bool -> Bool
|| [a]
i [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
l | [a]
l <- [[a]]
lines, [a]
p <- [[a]]
planes, let i :: [a]
i = [a]
l [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
p ]
isCircuitHyperplane :: Matroid a -> [a] -> Bool
isCircuitHyperplane m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isCircuit Matroid a
m [a]
xs Bool -> Bool -> Bool
&& Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isHyperplane Matroid a
m [a]
xs
circuitHyperplanes :: (Ord a) => Matroid a -> [[a]]
circuitHyperplanes :: Matroid a -> [[a]]
circuitHyperplanes m :: Matroid a
m = [ [a]
h | [a]
h <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
hyperplanes Matroid a
m, Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isCircuit Matroid a
m [a]
h ]
relaxation :: (Ord a) => Matroid a -> [a] -> Matroid a
relaxation :: Matroid a -> [a] -> Matroid a
relaxation m :: Matroid a
m b :: [a]
b
| Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isCircuitHyperplane Matroid a
m [a]
b = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
| Bool
otherwise = [Char] -> Matroid a
forall a. HasCallStack => [Char] -> a
error "relaxation: not a circuit-hyperplane"
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
bs :: [[a]]
bs = [a]
b [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
ex161 :: [[a]]
ex161 = [ [1,2,6], [3,4,5,6], [2,3], [2,4,6] ]
transversalGraph :: [[a]] -> [(Either a b, Either a b)]
transversalGraph as :: [[a]]
as = [(a -> Either a b
forall a b. a -> Either a b
Left a
x, b -> Either a b
forall a b. b -> Either a b
Right b
i) | (a :: [a]
a,i :: b
i) <- [[a]] -> [b] -> [([a], b)]
forall a b. [a] -> [b] -> [(a, b)]
zip [[a]]
as [1..], a
x <- [a]
a]
partialMatchings :: [(a, a)] -> [[(a, a)]]
partialMatchings es :: [(a, a)]
es = [(Set a, [(a, a)], [(a, a)])] -> [[(a, a)]]
forall a. Ord a => [(Set a, [(a, a)], [(a, a)])] -> [[(a, a)]]
dfs [(Set a
forall a. Set a
S.empty, [], [(a, a)]
es)]
where dfs :: [(Set a, [(a, a)], [(a, a)])] -> [[(a, a)]]
dfs (node :: (Set a, [(a, a)], [(a, a)])
node@(vs :: Set a
vs,ls :: [(a, a)]
ls,rs :: [(a, a)]
rs): nodes :: [(Set a, [(a, a)], [(a, a)])]
nodes) = [(a, a)]
ls [(a, a)] -> [[(a, a)]] -> [[(a, a)]]
forall a. a -> [a] -> [a]
: [(Set a, [(a, a)], [(a, a)])] -> [[(a, a)]]
dfs ((Set a, [(a, a)], [(a, a)]) -> [(Set a, [(a, a)], [(a, a)])]
forall a.
Ord a =>
(Set a, [(a, a)], [(a, a)]) -> [(Set a, [(a, a)], [(a, a)])]
successors (Set a, [(a, a)], [(a, a)])
node [(Set a, [(a, a)], [(a, a)])]
-> [(Set a, [(a, a)], [(a, a)])] -> [(Set a, [(a, a)], [(a, a)])]
forall a. [a] -> [a] -> [a]
++ [(Set a, [(a, a)], [(a, a)])]
nodes)
dfs [] = []
successors :: (Set a, [(a, a)], [(a, a)]) -> [(Set a, [(a, a)], [(a, a)])]
successors (vs :: Set a
vs,ls :: [(a, a)]
ls,rs :: [(a, a)]
rs) = [ (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
u (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
v Set a
vs, (a, a) -> [(a, a)] -> [(a, a)]
forall a. Ord a => a -> [a] -> [a]
L.insert (a, a)
r [(a, a)]
ls, [(a, a)]
rs')
| r :: (a, a)
r@(u :: a
u,v :: a
v):rs' :: [(a, a)]
rs' <- [(a, a)] -> [[(a, a)]]
forall a. [a] -> [[a]]
L.tails [(a, a)]
rs, a
u a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set a
vs, a
v a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set a
vs ]
transversalMatroid :: (Ord a) => [a] -> [[a]] -> Matroid a
transversalMatroid :: [a] -> [[a]] -> Matroid a
transversalMatroid es :: [a]
es as :: [[a]]
as = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
where is :: [[a]]
is@(i :: [a]
i:_) = [[a]] -> [[a]]
forall a. [a] -> [a]
reverse ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [[a]] -> [[a]]
forall (t :: * -> *) a. (Ord (t a), Foldable t) => [t a] -> [t a]
toShortlex ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [[a]] -> [[a]]
forall a. Ord a => [a] -> [a]
toSet ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ (([(Either a Integer, Either a Integer)] -> [a])
-> [[(Either a Integer, Either a Integer)]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (([(Either a Integer, Either a Integer)] -> [a])
-> [[(Either a Integer, Either a Integer)]] -> [[a]])
-> (((Either a Integer, Either a Integer) -> a)
-> [(Either a Integer, Either a Integer)] -> [a])
-> ((Either a Integer, Either a Integer) -> a)
-> [[(Either a Integer, Either a Integer)]]
-> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Either a Integer, Either a Integer) -> a)
-> [(Either a Integer, Either a Integer)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map) (Either a Integer -> a
forall a b. Either a b -> a
unLeft (Either a Integer -> a)
-> ((Either a Integer, Either a Integer) -> Either a Integer)
-> (Either a Integer, Either a Integer)
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Either a Integer, Either a Integer) -> Either a Integer
forall a b. (a, b) -> a
fst) ([[(Either a Integer, Either a Integer)]] -> [[a]])
-> [[(Either a Integer, Either a Integer)]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [(Either a Integer, Either a Integer)]
-> [[(Either a Integer, Either a Integer)]]
forall a. Ord a => [(a, a)] -> [[(a, a)]]
partialMatchings ([[a]] -> [(Either a Integer, Either a Integer)]
forall b a b a.
(Num b, Enum b) =>
[[a]] -> [(Either a b, Either a b)]
transversalGraph [[a]]
as)
unLeft :: Either a b -> a
unLeft (Left x :: a
x) = a
x
l :: Int
l = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
i
bs :: [[a]]
bs = [[a]] -> [[a]]
forall a. [a] -> [a]
reverse ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile ( (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l) (Int -> Bool) -> ([a] -> Int) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ) [[a]]
is
dual :: (Ord a) => Matroid a -> Matroid a
dual :: Matroid a -> Matroid a
dual m :: Matroid a
m = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs'
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
bs :: [[a]]
bs = Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
bs' :: [[a]]
bs' = [[a]] -> [[a]]
forall a. Ord a => [a] -> [a]
L.sort ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map ([a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\) [[a]]
bs
isCoindependent :: Matroid a -> [a] -> Bool
isCoindependent m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isIndependent (Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m) [a]
xs
isCobase :: Matroid a -> [a] -> Bool
isCobase m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isBase (Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m) [a]
xs
isCocircuit :: Matroid a -> [a] -> Bool
isCocircuit m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> Bool
forall a. Ord a => Matroid a -> [a] -> Bool
isCircuit (Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m) [a]
xs
cocircuits :: (Ord a) => Matroid a -> [[a]]
cocircuits :: Matroid a -> [[a]]
cocircuits m :: Matroid a
m = Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits (Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m)
isColoop :: Matroid a -> a -> Bool
isColoop m :: Matroid a
m e :: a
e = Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop (Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m) a
e
isCoparallel :: Matroid a -> a -> a -> Bool
isCoparallel m :: Matroid a
m f :: a
f g :: a
g = Matroid a -> a -> a -> Bool
forall a. Ord a => Matroid a -> a -> a -> Bool
isParallel (Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m) a
f a
g
deletion :: (Ord a) => Matroid a -> [a] -> Matroid a
deletion :: Matroid a -> [a] -> Matroid a
deletion m :: Matroid a
m xs :: [a]
xs = Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
restriction Matroid a
m ([a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
xs)
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
\\\ :: Matroid a -> [a] -> Matroid a
(\\\) = Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
deletion
contraction :: (Ord a) => Matroid a -> [a] -> Matroid a
contraction :: Matroid a -> [a] -> Matroid a
contraction m :: Matroid a
m xs :: [a]
xs = Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual (Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
deletion (Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m) [a]
xs)
/// :: Matroid a -> [a] -> Matroid a
(///) = Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
contraction
isConnected :: (Ord a) => Matroid a -> Bool
isConnected :: Matroid a -> Bool
isConnected m :: Matroid a
m = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ([a]
pair [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset`) [[a]]
cs | [a]
pair <- Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinationsOf 2 [a]
es]
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
cs :: [[a]]
cs = Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m
component :: Matroid a -> a -> [a]
component m :: Matroid a
m x :: a
x = Set a -> Set a -> [a]
closure Set a
forall a. Set a
S.empty (a -> Set a
forall a. a -> Set a
S.singleton a
x)
where cs :: [[a]]
cs = Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m
closure :: Set a -> Set a -> [a]
closure interior :: Set a
interior boundary :: Set a
boundary =
if Set a -> Bool
forall a. Set a -> Bool
S.null Set a
boundary
then Set a -> [a]
forall a. Set a -> [a]
S.toList Set a
interior
else let interior' :: Set a
interior' = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.union Set a
interior Set a
boundary
boundary' :: Set a
boundary' = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList ([[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[a]
c | [a]
c <- [[a]]
cs, (Bool -> Bool
not (Bool -> Bool) -> ([a] -> Bool) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null) ([a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.intersect [a]
c (Set a -> [a]
forall a. Set a -> [a]
S.toList Set a
boundary)) ])
Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.\\ Set a
interior'
in Set a -> Set a -> [a]
closure Set a
interior' Set a
boundary'
dsum :: (Ord a, Ord b) => Matroid a -> Matroid b -> Matroid (Either a b)
dsum :: Matroid a -> Matroid b -> Matroid (Either a b)
dsum m1 :: Matroid a
m1 m2 :: Matroid b
m2 = [Either a b] -> [[Either a b]] -> Matroid (Either a b)
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [Either a b]
es [[Either a b]]
bs
where es :: [Either a b]
es = (a -> Either a b) -> [a] -> [Either a b]
forall a b. (a -> b) -> [a] -> [b]
map a -> Either a b
forall a b. a -> Either a b
Left (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m1) [Either a b] -> [Either a b] -> [Either a b]
forall a. [a] -> [a] -> [a]
++ (b -> Either a b) -> [b] -> [Either a b]
forall a b. (a -> b) -> [a] -> [b]
map b -> Either a b
forall a b. b -> Either a b
Right (Matroid b -> [b]
forall t. Matroid t -> [t]
elements Matroid b
m2)
bs :: [[Either a b]]
bs = [(a -> Either a b) -> [a] -> [Either a b]
forall a b. (a -> b) -> [a] -> [b]
map a -> Either a b
forall a b. a -> Either a b
Left [a]
b1 [Either a b] -> [Either a b] -> [Either a b]
forall a. [a] -> [a] -> [a]
++ (b -> Either a b) -> [b] -> [Either a b]
forall a b. (a -> b) -> [a] -> [b]
map b -> Either a b
forall a b. b -> Either a b
Right [b]
b2 | [a]
b1 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m1, [b]
b2 <- Matroid b -> [[b]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid b
m2]
matroidPG :: (Eq a, Fractional a) => Int -> [a] -> Matroid Int
matroidPG :: Int -> [a] -> Matroid Int
matroidPG n :: Int
n fq :: [a]
fq = [[a]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' ([[a]] -> Matroid Int) -> [[a]] -> Matroid Int
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [[a]]
forall a. Num a => Int -> [a] -> [[a]]
ptsPG Int
n [a]
fq
matroidAG :: (Eq a, Fractional a) => Int -> [a] -> Matroid Int
matroidAG :: Int -> [a] -> Matroid Int
matroidAG n :: Int
n fq :: [a]
fq = [[a]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' ([[a]] -> Matroid Int) -> [[a]] -> Matroid Int
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
ptsAG Int
n [a]
fq
fundamentalCircuitIncidenceMatrix :: (Ord a, Num k) => Matroid a -> [a] -> [[k]]
fundamentalCircuitIncidenceMatrix :: Matroid a -> [a] -> [[k]]
fundamentalCircuitIncidenceMatrix m :: Matroid a
m b :: [a]
b = [[k]] -> [[k]]
forall a. [[a]] -> [[a]]
L.transpose ([[k]] -> [[k]]) -> [[k]] -> [[k]]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [a] -> [[k]]
forall a a. (Ord a, Num a) => Matroid a -> [a] -> [[a]]
fundamentalCircuitIncidenceMatrix' Matroid a
m [a]
b
fundamentalCircuitIncidenceMatrix' :: Matroid a -> [a] -> [[a]]
fundamentalCircuitIncidenceMatrix' m :: Matroid a
m b :: [a]
b =
[ [if a
e a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` Matroid a -> [a] -> a -> [a]
forall a. Ord a => Matroid a -> [a] -> a -> [a]
fundamentalCircuit Matroid a
m [a]
b a
e' then 1 else 0 | a
e <- [a]
b]
| a
e' <- Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b ]
fcim :: Matroid a -> [a] -> [[k]]
fcim = Matroid a -> [a] -> [[k]]
forall a a. (Ord a, Num a) => Matroid a -> [a] -> [[a]]
fundamentalCircuitIncidenceMatrix
fcim' :: Matroid a -> [a] -> [[a]]
fcim' = Matroid a -> [a] -> [[a]]
forall a a. (Ord a, Num a) => Matroid a -> [a] -> [[a]]
fundamentalCircuitIncidenceMatrix'
markNonInitialRCs :: [[a]] -> [[ZeroOneStar]]
markNonInitialRCs mx :: [[a]]
mx = [Bool] -> [[a]] -> [[ZeroOneStar]]
forall a. (Eq a, Num a) => [Bool] -> [[a]] -> [[ZeroOneStar]]
mark (Int -> Bool -> [Bool]
forall a. Int -> a -> [a]
replicate Int
w Bool
False) [[a]]
mx
where w :: Int
w = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> [a] -> Int
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall a. [a] -> a
head [[a]]
mx
mark :: [Bool] -> [[a]] -> [[ZeroOneStar]]
mark cms :: [Bool]
cms (r :: [a]
r:rs :: [[a]]
rs) = let (cms' :: [Bool]
cms', r' :: [ZeroOneStar]
r') = Bool
-> [Bool]
-> [Bool]
-> [ZeroOneStar]
-> [a]
-> ([Bool], [ZeroOneStar])
forall a.
(Eq a, Num a) =>
Bool
-> [Bool]
-> [Bool]
-> [ZeroOneStar]
-> [a]
-> ([Bool], [ZeroOneStar])
mark' Bool
False [] [Bool]
cms [] [a]
r in [ZeroOneStar]
r' [ZeroOneStar] -> [[ZeroOneStar]] -> [[ZeroOneStar]]
forall a. a -> [a] -> [a]
: [Bool] -> [[a]] -> [[ZeroOneStar]]
mark [Bool]
cms' [[a]]
rs
mark _ [] = []
mark' :: Bool
-> [Bool]
-> [Bool]
-> [ZeroOneStar]
-> [a]
-> ([Bool], [ZeroOneStar])
mark' rm :: Bool
rm cms' :: [Bool]
cms' (cm :: Bool
cm:cms :: [Bool]
cms) ys :: [ZeroOneStar]
ys (x :: a
x:xs :: [a]
xs)
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Bool
-> [Bool]
-> [Bool]
-> [ZeroOneStar]
-> [a]
-> ([Bool], [ZeroOneStar])
mark' Bool
rm (Bool
cmBool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
:[Bool]
cms') [Bool]
cms (ZeroOneStar
ZeroZeroOneStar -> [ZeroOneStar] -> [ZeroOneStar]
forall a. a -> [a] -> [a]
:[ZeroOneStar]
ys) [a]
xs
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== 1 = if Bool
rm Bool -> Bool -> Bool
&& Bool
cm
then Bool
-> [Bool]
-> [Bool]
-> [ZeroOneStar]
-> [a]
-> ([Bool], [ZeroOneStar])
mark' Bool
True (Bool
TrueBool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
:[Bool]
cms') [Bool]
cms (ZeroOneStar
StarZeroOneStar -> [ZeroOneStar] -> [ZeroOneStar]
forall a. a -> [a] -> [a]
:[ZeroOneStar]
ys) [a]
xs
else Bool
-> [Bool]
-> [Bool]
-> [ZeroOneStar]
-> [a]
-> ([Bool], [ZeroOneStar])
mark' Bool
True (Bool
TrueBool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
:[Bool]
cms') [Bool]
cms (ZeroOneStar
OneZeroOneStar -> [ZeroOneStar] -> [ZeroOneStar]
forall a. a -> [a] -> [a]
:[ZeroOneStar]
ys) [a]
xs
mark' _ cms' :: [Bool]
cms' [] ys :: [ZeroOneStar]
ys [] = ([Bool] -> [Bool]
forall a. [a] -> [a]
reverse [Bool]
cms', [ZeroOneStar] -> [ZeroOneStar]
forall a. [a] -> [a]
reverse [ZeroOneStar]
ys)
substStars :: [[ZeroOneStar]] -> [a] -> [[[a]]]
substStars mx :: [[ZeroOneStar]]
mx fq :: [a]
fq = [[ZeroOneStar]] -> [[[a]]]
substStars' [[ZeroOneStar]]
mx
where fq' :: [a]
fq' = [a] -> [a]
forall a. [a] -> [a]
tail [a]
fq
substStars' :: [[ZeroOneStar]] -> [[[a]]]
substStars' (r :: [ZeroOneStar]
r:rs :: [[ZeroOneStar]]
rs) = [[a]
r'[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
rs' | [a]
r' <- [ZeroOneStar] -> [[a]]
substStars'' [ZeroOneStar]
r, [[a]]
rs' <- [[ZeroOneStar]] -> [[[a]]]
substStars' [[ZeroOneStar]]
rs]
substStars' [] = [[]]
substStars'' :: [ZeroOneStar] -> [[a]]
substStars'' (Zero:xs :: [ZeroOneStar]
xs) = ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (0a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [ZeroOneStar] -> [[a]]
substStars'' [ZeroOneStar]
xs
substStars'' (One:xs :: [ZeroOneStar]
xs) = ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (1a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [ZeroOneStar] -> [[a]]
substStars'' [ZeroOneStar]
xs
substStars'' (Star:xs :: [ZeroOneStar]
xs) = [a
x'a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs' | a
x' <- [a]
fq', [a]
xs' <- [ZeroOneStar] -> [[a]]
substStars'' [ZeroOneStar]
xs]
substStars'' [] = [[]]
starSubstitutionsV :: [a] -> [ZeroOneStar] -> [[a]]
starSubstitutionsV fq' :: [a]
fq' (Zero:xs :: [ZeroOneStar]
xs) = ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (0a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [a] -> [ZeroOneStar] -> [[a]]
starSubstitutionsV [a]
fq' [ZeroOneStar]
xs
starSubstitutionsV fq' :: [a]
fq' (One:xs :: [ZeroOneStar]
xs) = ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (1a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [a] -> [ZeroOneStar] -> [[a]]
starSubstitutionsV [a]
fq' [ZeroOneStar]
xs
starSubstitutionsV fq' :: [a]
fq' (Star:xs :: [ZeroOneStar]
xs) = [a
x'a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs' | a
x' <- [a]
fq', [a]
xs' <- [a] -> [ZeroOneStar] -> [[a]]
starSubstitutionsV [a]
fq' [ZeroOneStar]
xs]
starSubstitutionsV _ [] = [[]]
representations1 :: [a] -> Matroid a -> [[[a]]]
representations1 fq :: [a]
fq m :: Matroid a
m = [ [[a]] -> [[a]]
forall a. [[a]] -> [[a]]
L.transpose [[a]]
d | [[a]]
d <- [[ZeroOneStar]] -> [a] -> [[[a]]]
forall a. Num a => [[ZeroOneStar]] -> [a] -> [[[a]]]
substStars [[ZeroOneStar]]
dhash [a]
fq, let mx :: [[a]]
mx = [[a]]
forall a. Num a => [[a]]
ir [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]]
d,
Matroid a -> Matroid Int
forall a. Ord a => Matroid a -> Matroid Int
to1n Matroid a
m Matroid Int -> Matroid Int -> Bool
forall a. Eq a => a -> a -> Bool
== ([[a]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' ([[a]] -> Matroid Int) -> [[a]] -> Matroid Int
forall a b. (a -> b) -> a -> b
$ ((a, [a]) -> [a]) -> [(a, [a])] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a, [a]) -> [a]
forall a b. (a, b) -> b
snd ([(a, [a])] -> [[a]]) -> [(a, [a])] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [(a, [a])] -> [(a, [a])]
forall a. Ord a => [a] -> [a]
L.sort ([(a, [a])] -> [(a, [a])]) -> [(a, [a])] -> [(a, [a])]
forall a b. (a -> b) -> a -> b
$ [a] -> [[a]] -> [(a, [a])]
forall a b. [a] -> [b] -> [(a, b)]
zip ([a]
b [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
b') [[a]]
mx) ]
where b :: [a]
b = [[a]] -> [a]
forall a. [a] -> a
head ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
b' :: [a]
b' = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b
r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
b
ir :: [[a]]
ir = Int -> [[a]]
forall a. Num a => Int -> [[a]]
idMx Int
r
dhash :: [[ZeroOneStar]]
dhash = [[Integer]] -> [[ZeroOneStar]]
forall a. (Eq a, Num a) => [[a]] -> [[ZeroOneStar]]
markNonInitialRCs ([[Integer]] -> [[ZeroOneStar]]) -> [[Integer]] -> [[ZeroOneStar]]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [a] -> [[Integer]]
forall a a. (Ord a, Num a) => Matroid a -> [a] -> [[a]]
fcim' Matroid a
m [a]
b
fcig :: Matroid a -> [a] -> [[a]]
fcig m :: Matroid a
m b :: [a]
b = [ [a
e,a
e'] | a
e <- [a]
b, a
e' <- Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b, a
e a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` Matroid a -> [a] -> a -> [a]
forall a. Ord a => Matroid a -> [a] -> a -> [a]
fundamentalCircuit Matroid a
m [a]
b a
e' ]
markedfcim :: Matroid a -> [a] -> [[ZeroOneStar]]
markedfcim m :: Matroid a
m b :: [a]
b = [a] -> [a] -> [[Integer]] -> [[ZeroOneStar]]
forall a. (Num a, Eq a) => [a] -> [a] -> [[a]] -> [[ZeroOneStar]]
mark [a]
b [a]
b' (Matroid a -> [a] -> [[Integer]]
forall a a. (Ord a, Num a) => Matroid a -> [a] -> [[a]]
fcim Matroid a
m [a]
b)
where b' :: [a]
b' = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b
entries :: [[a]]
entries = Matroid a -> [a] -> [[a]]
forall a. Ord a => Matroid a -> [a] -> [[a]]
fcig Matroid a
m [a]
b
ones :: [[a]]
ones = [[[a]]] -> [[a]]
forall a. [a] -> a
head ([[[a]]] -> [[a]]) -> [[[a]]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid [a] -> [[[a]]]
forall a. Ord a => Matroid a -> [[a]]
bases (Matroid [a] -> [[[a]]]) -> Matroid [a] -> [[[a]]]
forall a b. (a -> b) -> a -> b
$ [[a]] -> Matroid [a]
forall a. Ord a => [[a]] -> Matroid [a]
cycleMatroid' [[a]]
entries
stars :: [[a]]
stars = [[a]]
entries [[a]] -> [[a]] -> [[a]]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [[a]]
ones
mark :: [a] -> [a] -> [[a]] -> [[ZeroOneStar]]
mark (i :: a
i:is :: [a]
is) js :: [a]
js (r :: [a]
r:rs :: [[a]]
rs) = (a -> [a] -> [a] -> [ZeroOneStar]
forall a. (Num a, Eq a) => a -> [a] -> [a] -> [ZeroOneStar]
mark' a
i [a]
js [a]
r) [ZeroOneStar] -> [[ZeroOneStar]] -> [[ZeroOneStar]]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [[a]] -> [[ZeroOneStar]]
mark [a]
is [a]
js [[a]]
rs
mark [] _ [] = []
mark' :: a -> [a] -> [a] -> [ZeroOneStar]
mark' i :: a
i (j :: a
j:js :: [a]
js) (x :: a
x:xs :: [a]
xs)
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = ZeroOneStar
Zero ZeroOneStar -> [ZeroOneStar] -> [ZeroOneStar]
forall a. a -> [a] -> [a]
: a -> [a] -> [a] -> [ZeroOneStar]
mark' a
i [a]
js [a]
xs
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== 1 = (if [a
i,a
j] [a] -> [[a]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [[a]]
stars then ZeroOneStar
Star else ZeroOneStar
One) ZeroOneStar -> [ZeroOneStar] -> [ZeroOneStar]
forall a. a -> [a] -> [a]
: a -> [a] -> [a] -> [ZeroOneStar]
mark' a
i [a]
js [a]
xs
mark' _ [] [] = []
representations2 :: [a] -> Matroid a -> [[[a]]]
representations2 fq :: [a]
fq m :: Matroid a
m = [ [[a]] -> [[a]]
forall a. [[a]] -> [[a]]
L.transpose [[a]]
mx | [[a]]
d <- [[ZeroOneStar]] -> [a] -> [[[a]]]
forall a. Num a => [[ZeroOneStar]] -> [a] -> [[[a]]]
substStars [[ZeroOneStar]]
dhash' [a]
fq, let mx :: [[a]]
mx = [[a]]
forall a. Num a => [[a]]
ir [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]]
d,
Matroid Int
m' Matroid Int -> Matroid Int -> Bool
forall a. Eq a => a -> a -> Bool
== ([[a]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' ([[a]] -> Matroid Int) -> [[a]] -> Matroid Int
forall a b. (a -> b) -> a -> b
$ ((a, [a]) -> [a]) -> [(a, [a])] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a, [a]) -> [a]
forall a b. (a, b) -> b
snd ([(a, [a])] -> [[a]]) -> [(a, [a])] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [(a, [a])] -> [(a, [a])]
forall a. Ord a => [a] -> [a]
L.sort ([(a, [a])] -> [(a, [a])]) -> [(a, [a])] -> [(a, [a])]
forall a b. (a -> b) -> a -> b
$ [a] -> [[a]] -> [(a, [a])]
forall a b. [a] -> [b] -> [(a, b)]
zip ([a]
b [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
b') [[a]]
mx) ]
where m' :: Matroid Int
m' = Matroid a -> Matroid Int
forall a. Ord a => Matroid a -> Matroid Int
to1n Matroid a
m
es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
b :: [a]
b = [[a]] -> [a]
forall a. [a] -> a
head ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
b' :: [a]
b' = [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b
r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
b
ir :: [[a]]
ir = Int -> [[a]]
forall a. Num a => Int -> [[a]]
idMx Int
r
dhash' :: [[ZeroOneStar]]
dhash' = [[ZeroOneStar]] -> [[ZeroOneStar]]
forall a. [[a]] -> [[a]]
L.transpose ([[ZeroOneStar]] -> [[ZeroOneStar]])
-> [[ZeroOneStar]] -> [[ZeroOneStar]]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [a] -> [[ZeroOneStar]]
forall a. Ord a => Matroid a -> [a] -> [[ZeroOneStar]]
markedfcim Matroid a
m [a]
b
representations :: (Eq fq, Fractional fq, Ord a) => [fq] -> Matroid a -> [[[fq]]]
representations :: [fq] -> Matroid a -> [[[fq]]]
representations fq :: [fq]
fq m :: Matroid a
m = ([[fq]] -> [[fq]]) -> [[[fq]]] -> [[[fq]]]
forall a b. (a -> b) -> [a] -> [b]
map [[fq]] -> [[fq]]
forall a. [[a]] -> [[a]]
L.transpose ([[[fq]]] -> [[[fq]]]) -> [[[fq]]] -> [[[fq]]]
forall a b. (a -> b) -> a -> b
$ [(a, [fq])] -> [(a, [ZeroOneStar])] -> [[[fq]]]
representations' ([(a, [fq])] -> [(a, [fq])]
forall a. [a] -> [a]
reverse ([(a, [fq])] -> [(a, [fq])]) -> [(a, [fq])] -> [(a, [fq])]
forall a b. (a -> b) -> a -> b
$ [a] -> [[fq]] -> [(a, [fq])]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
b [[fq]]
forall a. Num a => [[a]]
ir) ([a] -> [[ZeroOneStar]] -> [(a, [ZeroOneStar])]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
b' [[ZeroOneStar]]
dhash')
where fq' :: [fq]
fq' = [fq] -> [fq]
forall a. [a] -> [a]
tail [fq]
fq
b :: [a]
b = [[a]] -> [a]
forall a. [a] -> a
head ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m
b' :: [a]
b' = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
b
r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
b
ir :: [[a]]
ir = Int -> [[a]]
forall a. Num a => Int -> [[a]]
idMx Int
r
dhash' :: [[ZeroOneStar]]
dhash' = [[ZeroOneStar]] -> [[ZeroOneStar]]
forall a. [[a]] -> [[a]]
L.transpose ([[ZeroOneStar]] -> [[ZeroOneStar]])
-> [[ZeroOneStar]] -> [[ZeroOneStar]]
forall a b. (a -> b) -> a -> b
$ Matroid a -> [a] -> [[ZeroOneStar]]
forall a. Ord a => Matroid a -> [a] -> [[ZeroOneStar]]
markedfcim Matroid a
m [a]
b
representations' :: [(a, [fq])] -> [(a, [ZeroOneStar])] -> [[[fq]]]
representations' ls :: [(a, [fq])]
ls ((i :: a
i,r :: [ZeroOneStar]
r):rs :: [(a, [ZeroOneStar])]
rs) = [[[[fq]]]] -> [[[fq]]]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat
[ [(a, [fq])] -> [(a, [ZeroOneStar])] -> [[[fq]]]
representations' ((a
i,[fq]
r')(a, [fq]) -> [(a, [fq])] -> [(a, [fq])]
forall a. a -> [a] -> [a]
:[(a, [fq])]
ls) [(a, [ZeroOneStar])]
rs
| [fq]
r' <- [fq] -> [ZeroOneStar] -> [[fq]]
forall a. Num a => [a] -> [ZeroOneStar] -> [[a]]
starSubstitutionsV [fq]
fq' [ZeroOneStar]
r,
let (is :: [a]
is,vs :: [[fq]]
vs) = [(a, [fq])] -> ([a], [[fq]])
forall a b. [(a, b)] -> ([a], [b])
unzip ([(a, [fq])] -> ([a], [[fq]])) -> [(a, [fq])] -> ([a], [[fq]])
forall a b. (a -> b) -> a -> b
$ ((a, [fq]) -> (a, [fq]) -> Ordering) -> [(a, [fq])] -> [(a, [fq])]
forall a. (a -> a -> Ordering) -> [a] -> [a]
L.sortBy (a, [fq]) -> (a, [fq]) -> Ordering
forall a b1 b2. Ord a => (a, b1) -> (a, b2) -> Ordering
cmpfst ((a
i,[fq]
r')(a, [fq]) -> [(a, [fq])] -> [(a, [fq])]
forall a. a -> [a] -> [a]
:[(a, [fq])]
ls),
Matroid a -> Matroid Int
forall a. Ord a => Matroid a -> Matroid Int
to1n (Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
restriction Matroid a
m [a]
is) Matroid Int -> Matroid Int -> Bool
forall a. Eq a => a -> a -> Bool
== ([[fq]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid' [[fq]]
vs) ]
representations' ls :: [(a, [fq])]
ls [] = [((a, [fq]) -> [fq]) -> [(a, [fq])] -> [[fq]]
forall a b. (a -> b) -> [a] -> [b]
map (a, [fq]) -> [fq]
forall a b. (a, b) -> b
snd ([(a, [fq])] -> [[fq]]) -> [(a, [fq])] -> [[fq]]
forall a b. (a -> b) -> a -> b
$ [(a, [fq])] -> [(a, [fq])]
forall a. [a] -> [a]
reverse [(a, [fq])]
ls]
isRepresentable :: (Eq fq, Fractional fq, Ord a) => [fq] -> Matroid a -> Bool
isRepresentable :: [fq] -> Matroid a -> Bool
isRepresentable fq :: [fq]
fq m :: Matroid a
m = (Bool -> Bool
not (Bool -> Bool) -> ([[[fq]]] -> Bool) -> [[[fq]]] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[[fq]]] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null) ([fq] -> Matroid a -> [[[fq]]]
forall fq a.
(Eq fq, Fractional fq, Ord a) =>
[fq] -> Matroid a -> [[[fq]]]
representations [fq]
fq Matroid a
m)
isBinary :: (Ord a) => Matroid a -> Bool
isBinary :: Matroid a -> Bool
isBinary = [F2] -> Matroid a -> Bool
forall fq a.
(Eq fq, Fractional fq, Ord a) =>
[fq] -> Matroid a -> Bool
isRepresentable [F2]
f2
isTernary :: (Ord a) => Matroid a -> Bool
isTernary :: Matroid a -> Bool
isTernary = [F3] -> Matroid a -> Bool
forall fq a.
(Eq fq, Fractional fq, Ord a) =>
[fq] -> Matroid a -> Bool
isRepresentable [F3]
f3
data LMR a b = L a | Mid | R b deriving (LMR a b -> LMR a b -> Bool
(LMR a b -> LMR a b -> Bool)
-> (LMR a b -> LMR a b -> Bool) -> Eq (LMR a b)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a b. (Eq a, Eq b) => LMR a b -> LMR a b -> Bool
/= :: LMR a b -> LMR a b -> Bool
$c/= :: forall a b. (Eq a, Eq b) => LMR a b -> LMR a b -> Bool
== :: LMR a b -> LMR a b -> Bool
$c== :: forall a b. (Eq a, Eq b) => LMR a b -> LMR a b -> Bool
Eq, Eq (LMR a b)
Eq (LMR a b) =>
(LMR a b -> LMR a b -> Ordering)
-> (LMR a b -> LMR a b -> Bool)
-> (LMR a b -> LMR a b -> Bool)
-> (LMR a b -> LMR a b -> Bool)
-> (LMR a b -> LMR a b -> Bool)
-> (LMR a b -> LMR a b -> LMR a b)
-> (LMR a b -> LMR a b -> LMR a b)
-> Ord (LMR a b)
LMR a b -> LMR a b -> Bool
LMR a b -> LMR a b -> Ordering
LMR a b -> LMR a b -> LMR a b
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 b. (Ord a, Ord b) => Eq (LMR a b)
forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> Bool
forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> Ordering
forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> LMR a b
min :: LMR a b -> LMR a b -> LMR a b
$cmin :: forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> LMR a b
max :: LMR a b -> LMR a b -> LMR a b
$cmax :: forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> LMR a b
>= :: LMR a b -> LMR a b -> Bool
$c>= :: forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> Bool
> :: LMR a b -> LMR a b -> Bool
$c> :: forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> Bool
<= :: LMR a b -> LMR a b -> Bool
$c<= :: forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> Bool
< :: LMR a b -> LMR a b -> Bool
$c< :: forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> Bool
compare :: LMR a b -> LMR a b -> Ordering
$ccompare :: forall a b. (Ord a, Ord b) => LMR a b -> LMR a b -> Ordering
$cp1Ord :: forall a b. (Ord a, Ord b) => Eq (LMR a b)
Ord, Int -> LMR a b -> [Char] -> [Char]
[LMR a b] -> [Char] -> [Char]
LMR a b -> [Char]
(Int -> LMR a b -> [Char] -> [Char])
-> (LMR a b -> [Char])
-> ([LMR a b] -> [Char] -> [Char])
-> Show (LMR a b)
forall a.
(Int -> a -> [Char] -> [Char])
-> (a -> [Char]) -> ([a] -> [Char] -> [Char]) -> Show a
forall a b. (Show a, Show b) => Int -> LMR a b -> [Char] -> [Char]
forall a b. (Show a, Show b) => [LMR a b] -> [Char] -> [Char]
forall a b. (Show a, Show b) => LMR a b -> [Char]
showList :: [LMR a b] -> [Char] -> [Char]
$cshowList :: forall a b. (Show a, Show b) => [LMR a b] -> [Char] -> [Char]
show :: LMR a b -> [Char]
$cshow :: forall a b. (Show a, Show b) => LMR a b -> [Char]
showsPrec :: Int -> LMR a b -> [Char] -> [Char]
$cshowsPrec :: forall a b. (Show a, Show b) => Int -> LMR a b -> [Char] -> [Char]
Show)
seriesConnection :: (Matroid a, a) -> (Matroid a, a) -> Matroid (LMR a a)
seriesConnection (m1 :: Matroid a
m1,p1 :: a
p1) (m2 :: Matroid a
m2,p2 :: a
p2)
| Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop Matroid a
m1 a
p1) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isColoop Matroid a
m1 a
p1) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop Matroid a
m2 a
p2) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isColoop Matroid a
m2 a
p2) =
[LMR a a] -> [[LMR a a]] -> Matroid (LMR a a)
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromCircuits [LMR a a]
es [[LMR a a]]
cs
| Bool
otherwise = [Char] -> Matroid (LMR a a)
forall a. HasCallStack => [Char] -> a
error "not yet implemented"
where es :: [LMR a a]
es = (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. a -> LMR a b
L (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a
p1]) [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ [LMR a a
forall a b. LMR a b
Mid] [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. b -> LMR a b
R (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m2 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a
p2])
cs :: [[LMR a a]]
cs = (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]]
forall a b. (a -> b) -> [a] -> [b]
map (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]])
-> ((a -> LMR a a) -> [a] -> [LMR a a])
-> (a -> LMR a a)
-> [[a]]
-> [[LMR a a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map) a -> LMR a a
forall a b. a -> LMR a b
L (Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits (Matroid a -> [[a]]) -> Matroid a -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a
m1 Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
p1]) [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
(([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]]
forall a b. (a -> b) -> [a] -> [b]
map (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]])
-> ((a -> LMR a a) -> [a] -> [LMR a a])
-> (a -> LMR a a)
-> [[a]]
-> [[LMR a a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map) a -> LMR a a
forall a b. b -> LMR a b
R (Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits (Matroid a -> [[a]]) -> Matroid a -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a
m2 Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
p2]) [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
[ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. a -> LMR a b
L (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p1 [a]
c1) [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ [LMR a a
forall a b. LMR a b
Mid] [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. b -> LMR a b
R (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p2 [a]
c2)
| [a]
c1 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m1, a
p1 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c1, [a]
c2 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m2, a
p2 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c2]
parallelConnection :: (Matroid a, a) -> (Matroid a, a) -> Matroid (LMR a a)
parallelConnection (m1 :: Matroid a
m1,p1 :: a
p1) (m2 :: Matroid a
m2,p2 :: a
p2)
| Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop Matroid a
m1 a
p1) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isColoop Matroid a
m1 a
p1) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop Matroid a
m2 a
p2) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isColoop Matroid a
m2 a
p2) =
[LMR a a] -> [[LMR a a]] -> Matroid (LMR a a)
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromCircuits [LMR a a]
es [[LMR a a]]
cs
| Bool
otherwise = [Char] -> Matroid (LMR a a)
forall a. HasCallStack => [Char] -> a
error "not yet implemented"
where es :: [LMR a a]
es = (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. a -> LMR a b
L (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a
p1]) [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ [LMR a a
forall a b. LMR a b
Mid] [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. b -> LMR a b
R (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m2 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a
p2])
cs :: [[LMR a a]]
cs = (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]]
forall a b. (a -> b) -> [a] -> [b]
map (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]])
-> ((a -> LMR a a) -> [a] -> [LMR a a])
-> (a -> LMR a a)
-> [[a]]
-> [[LMR a a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map) a -> LMR a a
forall a b. a -> LMR a b
L (Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits (Matroid a -> [[a]]) -> Matroid a -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a
m1 Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
p1]) [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
[ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. a -> LMR a b
L (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p1 [a]
c1) [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ [LMR a a
forall a b. LMR a b
Mid] | [a]
c1 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m1, a
p1 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c1 ] [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
(([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]]
forall a b. (a -> b) -> [a] -> [b]
map (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]])
-> ((a -> LMR a a) -> [a] -> [LMR a a])
-> (a -> LMR a a)
-> [[a]]
-> [[LMR a a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map) a -> LMR a a
forall a b. b -> LMR a b
R (Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits (Matroid a -> [[a]]) -> Matroid a -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a
m2 Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
p2]) [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
[ [LMR a a
forall a b. LMR a b
Mid] [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. b -> LMR a b
R (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p2 [a]
c2) | [a]
c2 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m2, a
p2 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c2 ] [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
[ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. a -> LMR a b
L (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p1 [a]
c1) [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. b -> LMR a b
R (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p2 [a]
c2)
| [a]
c1 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m1, a
p1 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c1, [a]
c2 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m2, a
p2 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c2 ]
twoSum :: (Matroid a, a) -> (Matroid a, a) -> Matroid (LMR a a)
twoSum (m1 :: Matroid a
m1,p1 :: a
p1) (m2 :: Matroid a
m2,p2 :: a
p2)
| Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop Matroid a
m1 a
p1) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isColoop Matroid a
m1 a
p1) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop Matroid a
m2 a
p2) Bool -> Bool -> Bool
&& Bool -> Bool
not (Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isColoop Matroid a
m2 a
p2) =
[LMR a a] -> [[LMR a a]] -> Matroid (LMR a a)
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromCircuits [LMR a a]
es [[LMR a a]]
cs
| Bool
otherwise = [Char] -> Matroid (LMR a a)
forall a. HasCallStack => [Char] -> a
error "not yet implemented"
where es :: [LMR a a]
es = (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. a -> LMR a b
L (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m1 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a
p1]) [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ [LMR a a
forall a b. LMR a b
Mid] [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. b -> LMR a b
R (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m2 [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a
p2])
cs :: [[LMR a a]]
cs = (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]]
forall a b. (a -> b) -> [a] -> [b]
map (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]])
-> ((a -> LMR a a) -> [a] -> [LMR a a])
-> (a -> LMR a a)
-> [[a]]
-> [[LMR a a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map) a -> LMR a a
forall a b. a -> LMR a b
L (Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits (Matroid a -> [[a]]) -> Matroid a -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a
m1 Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
p1]) [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
(([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]]
forall a b. (a -> b) -> [a] -> [b]
map (([a] -> [LMR a a]) -> [[a]] -> [[LMR a a]])
-> ((a -> LMR a a) -> [a] -> [LMR a a])
-> (a -> LMR a a)
-> [[a]]
-> [[LMR a a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map) a -> LMR a a
forall a b. b -> LMR a b
R (Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits (Matroid a -> [[a]]) -> Matroid a -> [[a]]
forall a b. (a -> b) -> a -> b
$ Matroid a
m2 Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
p2]) [[LMR a a]] -> [[LMR a a]] -> [[LMR a a]]
forall a. [a] -> [a] -> [a]
++
[ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. a -> LMR a b
L (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p1 [a]
c1) [LMR a a] -> [LMR a a] -> [LMR a a]
forall a. [a] -> [a] -> [a]
++ (a -> LMR a a) -> [a] -> [LMR a a]
forall a b. (a -> b) -> [a] -> [b]
map a -> LMR a a
forall a b. b -> LMR a b
R (a -> [a] -> [a]
forall a. Eq a => a -> [a] -> [a]
L.delete a
p2 [a]
c2)
| [a]
c1 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m1, a
p1 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c1, [a]
c2 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m2, a
p2 a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
c2]
matroidUnion :: Matroid a -> Matroid a -> Matroid a
matroidUnion m1 :: Matroid a
m1 m2 :: Matroid a
m2 = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromBases [a]
es [[a]]
bs
where es :: [a]
es = [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.union (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m1) (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m2)
is :: [[a]]
is = [[a]] -> [[a]]
forall (t :: * -> *) a. (Ord (t a), Foldable t) => [t a] -> [t a]
toShortlex ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [[a]] -> [[a]]
forall a. Ord a => [a] -> [a]
toSet [ [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.union [a]
b1 [a]
b2 | [a]
b1 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m1, [a]
b2 <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
bases Matroid a
m2 ]
r :: Int
r = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> [a] -> Int
forall a b. (a -> b) -> a -> b
$ [[a]] -> [a]
forall a. [a] -> a
last [[a]]
is
bs :: [[a]]
bs = ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile ( (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r) (Int -> Bool) -> ([a] -> Int) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ) [[a]]
is
f7 :: Matroid Int
f7 :: Matroid Int
f7 = [[Int]] -> [[Int]] -> [[Int]] -> [[Int]] -> Matroid Int
forall a. Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep [] [] [[1,2,3],[1,4,7],[1,5,6],[2,4,6],[2,5,7],[3,4,5],[3,6,7]] [[1..7]]
f7m :: Matroid Int
f7m :: Matroid Int
f7m = Matroid Int -> [Int] -> Matroid Int
forall a. Ord a => Matroid a -> [a] -> Matroid a
relaxation Matroid Int
f7 [2,4,6]
pappus :: Matroid Int
pappus :: Matroid Int
pappus = [[Int]] -> [[Int]] -> [[Int]] -> [[Int]] -> Matroid Int
forall a. Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep [] [] [[1,2,3],[1,5,7],[1,6,8],[2,4,7],[2,6,9],[3,4,8],[3,5,9],[4,5,6],[7,8,9]] [[1..9]]
nonPappus :: Matroid Int
nonPappus :: Matroid Int
nonPappus = Matroid Int -> [Int] -> Matroid Int
forall a. Ord a => Matroid a -> [a] -> Matroid a
relaxation Matroid Int
pappus [7,8,9]
desargues :: Matroid Int
desargues :: Matroid Int
desargues = [[Int]] -> [[Int]] -> [[Int]] -> [[Int]] -> Matroid Int
forall a. Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep [] [] [[1,2,5],[1,3,6],[1,4,7],[2,3,8],[2,4,9],[3,4,10],[5,6,8],[5,7,9],[6,7,10],[8,9,10]]
[[1,2,3,5,6,8],[1,2,4,5,7,9],[1,3,4,6,7,10],[2,3,4,8,9,10],[5,6,7,8,9,10]]
vamosMatroid1 :: Matroid a
vamosMatroid1 = [a] -> [[a]] -> Matroid a
forall a. Ord a => [a] -> [[a]] -> Matroid a
fromHyperplanes [1..8] ([[a]]
forall a. Num a => [[a]]
hs4 [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]]
forall a. (Num a, Enum a, Ord a) => [[a]]
hs3)
where hs4 :: [[a]]
hs4 = [ [1,2,3,4], [1,4,5,6], [2,3,5,6], [1,4,7,8], [2,3,7,8] ]
hs3 :: [[a]]
hs3 = [ [a]
h3 | [a]
h3 <- Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
combinationsOf 3 [1..8], [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [[a]
h4 | [a]
h4 <- [[a]]
forall a. Num a => [[a]]
hs4, [a]
h3 [a] -> [a] -> Bool
forall a. Ord a => [a] -> [a] -> Bool
`LS.isSubset` [a]
h4] ]
vamosMatroid :: Matroid a
vamosMatroid = [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
forall a. Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep [] [] [] [[1,2,3,4],[1,4,5,6],[2,3,5,6],[1,4,7,8],[2,3,7,8]]
v8 :: Matroid Int
v8 :: Matroid Int
v8 = Matroid Int
forall a. (Ord a, Num a) => Matroid a
vamosMatroid
p8 :: Matroid Int
p8 :: Matroid Int
p8 = [[F3]] -> Matroid Int
forall k. (Eq k, Fractional k) => [[k]] -> Matroid Int
vectorMatroid ([[F3]] -> Matroid Int) -> [[F3]] -> Matroid Int
forall a b. (a -> b) -> a -> b
$
( [ [1,0,0,0, 0, 1, 1,-1],
[0,1,0,0, 1, 0, 1, 1],
[0,0,1,0, 1, 1, 0, 1],
[0,0,0,1, -1, 1, 1, 0] ] :: [[F3]] )
p8' :: Matroid a
p8' = [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
forall a. Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep [] [] [] [ [1,2,3,8], [1,2,4,7], [1,3,4,6], [1,4,5,8], [1,5,6,7], [2,3,4,5], [2,3,6,7], [2,5,6,8], [3,5,7,8], [4,6,7,8] ]
p8m :: Matroid Int
p8m :: Matroid Int
p8m = Matroid Int -> [Int] -> Matroid Int
forall a. Ord a => Matroid a -> [a] -> Matroid a
relaxation Matroid Int
p8 [2,3,6,7]
p8mm :: Matroid Int
p8mm :: Matroid Int
p8mm = Matroid Int -> [Int] -> Matroid Int
forall a. Ord a => Matroid a -> [a] -> Matroid a
relaxation Matroid Int
p8m [1,4,5,8]
wheelGraph :: a -> Graph a
wheelGraph r :: a
r = [a] -> [[a]] -> Graph a
forall a. [a] -> [[a]] -> Graph a
G.G [a]
vs [[a]]
es
where vs :: [a]
vs = [0..a
r]
es :: [[a]]
es = [ [0,a
i] | a
i <- [1..a
r] ] [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [ [a
i,a
ia -> a -> a
forall a. Num a => a -> a -> a
+1] | a
i <- [1..a
ra -> a -> a
forall a. Num a => a -> a -> a
-1] ] [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [ [1,a
r] ]
mw4 :: Matroid Int
mw4 = [[Integer]] -> Matroid Int
forall a. Ord a => [[a]] -> Matroid Int
cycleMatroid ([[Integer]] -> Matroid Int) -> [[Integer]] -> Matroid Int
forall a b. (a -> b) -> a -> b
$ Graph Integer -> [[Integer]]
forall a. Graph a -> [[a]]
G.edges (Graph Integer -> [[Integer]]) -> Graph Integer -> [[Integer]]
forall a b. (a -> b) -> a -> b
$ Integer -> Graph Integer
forall a. (Num a, Enum a) => a -> Graph a
wheelGraph 4
w4' :: Matroid Int
w4' = Matroid Int -> [Int] -> Matroid Int
forall a. Ord a => Matroid a -> [a] -> Matroid a
relaxation Matroid Int
mw4 ([Int] -> Matroid Int) -> [Int] -> Matroid Int
forall a b. (a -> b) -> a -> b
$ [[Int]] -> [Int]
forall a. [a] -> a
unique ([[Int]] -> [Int]) -> [[Int]] -> [Int]
forall a b. (a -> b) -> a -> b
$ Matroid Int -> [[Int]]
forall a. Ord a => Matroid a -> [[a]]
circuitHyperplanes Matroid Int
mw4
w4 :: Matroid a
w4 = [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
forall a. Ord a => [[a]] -> [[a]] -> [[a]] -> [[a]] -> Matroid a
fromGeoRep [] [] [[1,2,5],[1,4,8],[2,3,6],[3,4,7]] [[1,2,3,5,6],[1,2,4,5,8],[1,3,4,7,8],[2,3,4,6,7]]
isBinary2 :: Matroid a -> Bool
isBinary2 m :: Matroid a
m = ([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Int -> Bool
forall a. Integral a => a -> Bool
even (Int -> Bool) -> ([a] -> Int) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length) [ [a]
c [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
`LS.intersect` [a]
cc | [a]
c <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
circuits Matroid a
m, [a]
cc <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
cocircuits Matroid a
m ]
[x :: GlexPoly Integer [Char]
x,y :: GlexPoly Integer [Char]
y] = ([Char] -> GlexPoly Integer [Char])
-> [[Char]] -> [GlexPoly Integer [Char]]
forall a b. (a -> b) -> [a] -> [b]
map [Char] -> GlexPoly Integer [Char]
forall k v. Num k => v -> GlexPoly k v
glexVar ["x","y"] :: [GlexPoly Integer String]
rankPoly1 :: Matroid a -> GlexPoly Integer [Char]
rankPoly1 m :: Matroid a
m = [GlexPoly Integer [Char]] -> GlexPoly Integer [Char]
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [ GlexPoly Integer [Char]
xGlexPoly Integer [Char] -> Int -> GlexPoly Integer [Char]
forall a b. (Num a, Integral b) => a -> b -> a
^(Int
rm Int -> Int -> Int
forall a. Num a => a -> a -> a
- [a] -> Int
r [a]
a) GlexPoly Integer [Char]
-> GlexPoly Integer [Char] -> GlexPoly Integer [Char]
forall a. Num a => a -> a -> a
* GlexPoly Integer [Char]
yGlexPoly Integer [Char] -> Int -> GlexPoly Integer [Char]
forall a b. (Num a, Integral b) => a -> b -> a
^(Int
rm' Int -> Int -> Int
forall a. Num a => a -> a -> a
- [a] -> Int
r' [a]
a') | [a]
a <- [a] -> [[a]]
forall a. [a] -> [[a]]
powersetdfs [a]
es, let a' :: [a]
a' = [a]
es [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
LS.\\ [a]
a ]
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
rm :: Int
rm = Matroid a -> Int
forall a. Ord a => Matroid a -> Int
rank Matroid a
m
r :: [a] -> Int
r = Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m
m' :: Matroid a
m' = Matroid a -> Matroid a
forall a. Ord a => Matroid a -> Matroid a
dual Matroid a
m
rm' :: Int
rm' = Matroid a -> Int
forall a. Ord a => Matroid a -> Int
rank Matroid a
m'
r' :: [a] -> Int
r' = Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m'
rankPoly :: (Ord a) => Matroid a -> GlexPoly Integer String
rankPoly :: Matroid a -> GlexPoly Integer [Char]
rankPoly m :: Matroid a
m
| [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
es = 1
| Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isLoop Matroid a
m a
e = (1GlexPoly Integer [Char]
-> GlexPoly Integer [Char] -> GlexPoly Integer [Char]
forall a. Num a => a -> a -> a
+GlexPoly Integer [Char]
y) GlexPoly Integer [Char]
-> GlexPoly Integer [Char] -> GlexPoly Integer [Char]
forall a. Num a => a -> a -> a
* Matroid a -> GlexPoly Integer [Char]
forall a. Ord a => Matroid a -> GlexPoly Integer [Char]
rankPoly (Matroid a
m Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
e])
| Matroid a -> a -> Bool
forall a. Ord a => Matroid a -> a -> Bool
isColoop Matroid a
m a
e = (1GlexPoly Integer [Char]
-> GlexPoly Integer [Char] -> GlexPoly Integer [Char]
forall a. Num a => a -> a -> a
+GlexPoly Integer [Char]
x) GlexPoly Integer [Char]
-> GlexPoly Integer [Char] -> GlexPoly Integer [Char]
forall a. Num a => a -> a -> a
* Matroid a -> GlexPoly Integer [Char]
forall a. Ord a => Matroid a -> GlexPoly Integer [Char]
rankPoly (Matroid a
m Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
/// [a
e])
| Bool
otherwise = Matroid a -> GlexPoly Integer [Char]
forall a. Ord a => Matroid a -> GlexPoly Integer [Char]
rankPoly (Matroid a
m Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
\\\ [a
e]) GlexPoly Integer [Char]
-> GlexPoly Integer [Char] -> GlexPoly Integer [Char]
forall a. Num a => a -> a -> a
+ Matroid a -> GlexPoly Integer [Char]
forall a. Ord a => Matroid a -> GlexPoly Integer [Char]
rankPoly (Matroid a
m Matroid a -> [a] -> Matroid a
forall a. Ord a => Matroid a -> [a] -> Matroid a
/// [a
e])
where es :: [a]
es = Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m
e :: a
e = [a] -> a
forall a. [a] -> a
head [a]
es
numBases :: Matroid a -> Integer
numBases m :: Matroid a
m = Vect Integer () -> Integer
forall k. Num k => Vect k () -> k
unwrap (Vect Integer () -> Integer) -> Vect Integer () -> Integer
forall a b. (a -> b) -> a -> b
$ Matroid a -> GlexPoly Integer [Char]
forall a. Ord a => Matroid a -> GlexPoly Integer [Char]
rankPoly Matroid a
m GlexPoly Integer [Char]
-> ([Char] -> Vect Integer ()) -> Vect Integer ()
forall (m :: * -> *) k b v.
(Monomial m, Eq k, Num k, Ord b, Show b, Algebra k b) =>
Vect k (m v) -> (v -> Vect k b) -> Vect k b
`bind` (\v :: [Char]
v -> case [Char]
v of "x" -> 0; "y" -> 0)
numIndeps :: Matroid a -> Integer
numIndeps m :: Matroid a
m = Vect Integer () -> Integer
forall k. Num k => Vect k () -> k
unwrap (Vect Integer () -> Integer) -> Vect Integer () -> Integer
forall a b. (a -> b) -> a -> b
$ Matroid a -> GlexPoly Integer [Char]
forall a. Ord a => Matroid a -> GlexPoly Integer [Char]
rankPoly Matroid a
m GlexPoly Integer [Char]
-> ([Char] -> Vect Integer ()) -> Vect Integer ()
forall (m :: * -> *) k b v.
(Monomial m, Eq k, Num k, Ord b, Show b, Algebra k b) =>
Vect k (m v) -> (v -> Vect k b) -> Vect k b
`bind` (\v :: [Char]
v -> case [Char]
v of "x" -> 1; "y" -> 0)
numSpanning :: Matroid a -> Integer
numSpanning m :: Matroid a
m = Vect Integer () -> Integer
forall k. Num k => Vect k () -> k
unwrap (Vect Integer () -> Integer) -> Vect Integer () -> Integer
forall a b. (a -> b) -> a -> b
$ Matroid a -> GlexPoly Integer [Char]
forall a. Ord a => Matroid a -> GlexPoly Integer [Char]
rankPoly Matroid a
m GlexPoly Integer [Char]
-> ([Char] -> Vect Integer ()) -> Vect Integer ()
forall (m :: * -> *) k b v.
(Monomial m, Eq k, Num k, Ord b, Show b, Algebra k b) =>
Vect k (m v) -> (v -> Vect k b) -> Vect k b
`bind` (\v :: [Char]
v -> case [Char]
v of "x" -> 0; "y" -> 1)
indepCounts :: Matroid a -> [Int]
indepCounts m :: Matroid a
m = ([(Int, [a])] -> Int) -> [[(Int, [a])]] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map [(Int, [a])] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([[(Int, [a])]] -> [Int]) -> [[(Int, [a])]] -> [Int]
forall a b. (a -> b) -> a -> b
$ ((Int, [a]) -> (Int, [a]) -> Bool)
-> [(Int, [a])] -> [[(Int, [a])]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
L.groupBy (Int, [a]) -> (Int, [a]) -> Bool
forall a b1 b2. Eq a => (a, b1) -> (a, b2) -> Bool
eqfst ([(Int, [a])] -> [[(Int, [a])]]) -> [(Int, [a])] -> [[(Int, [a])]]
forall a b. (a -> b) -> a -> b
$ [([a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
i, [a]
i) | [a]
i <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
indeps Matroid a
m]
whitney2nd :: Matroid a -> [Int]
whitney2nd m :: Matroid a
m = ([(Int, [a])] -> Int) -> [[(Int, [a])]] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map [(Int, [a])] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([[(Int, [a])]] -> [Int]) -> [[(Int, [a])]] -> [Int]
forall a b. (a -> b) -> a -> b
$ ((Int, [a]) -> (Int, [a]) -> Bool)
-> [(Int, [a])] -> [[(Int, [a])]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
L.groupBy (Int, [a]) -> (Int, [a]) -> Bool
forall a b1 b2. Eq a => (a, b1) -> (a, b2) -> Bool
eqfst ([(Int, [a])] -> [[(Int, [a])]]) -> [(Int, [a])] -> [[(Int, [a])]]
forall a b. (a -> b) -> a -> b
$ [(Int, [a])] -> [(Int, [a])]
forall a. Ord a => [a] -> [a]
L.sort [(Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m [a]
f, [a]
f) | [a]
f <- Matroid a -> [[a]]
forall a. Ord a => Matroid a -> [[a]]
flats Matroid a
m]
whitney1st :: Matroid a -> [Int]
whitney1st m :: Matroid a
m = [Int] -> [Int]
forall b. Num b => [b] -> [b]
alternatingSign ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ ([(Int, [a])] -> Int) -> [[(Int, [a])]] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map [(Int, [a])] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([[(Int, [a])]] -> [Int]) -> [[(Int, [a])]] -> [Int]
forall a b. (a -> b) -> a -> b
$ ((Int, [a]) -> (Int, [a]) -> Bool)
-> [(Int, [a])] -> [[(Int, [a])]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
L.groupBy (Int, [a]) -> (Int, [a]) -> Bool
forall a b1 b2. Eq a => (a, b1) -> (a, b2) -> Bool
eqfst ([(Int, [a])] -> [[(Int, [a])]]) -> [(Int, [a])] -> [[(Int, [a])]]
forall a b. (a -> b) -> a -> b
$ [(Int, [a])] -> [(Int, [a])]
forall a. Ord a => [a] -> [a]
L.sort [(Matroid a -> [a] -> Int
forall a. Ord a => Matroid a -> [a] -> Int
rankfun Matroid a
m [a]
x, [a]
x) | [a]
x <- [a] -> [[a]]
forall a. [a] -> [[a]]
powersetdfs (Matroid a -> [a]
forall t. Matroid t -> [t]
elements Matroid a
m)]
where alternatingSign :: [b] -> [b]
alternatingSign (x :: b
x:xs :: [b]
xs) = b
x b -> [b] -> [b]
forall a. a -> [a] -> [a]
: [b] -> [b]
alternatingSign ((b -> b) -> [b] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map b -> b
forall a. Num a => a -> a
negate [b]
xs)
alternatingSign [] = []