{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}
{-|
Module      : Test.Matroid.Suites
Description : 
Copyright   : (c) Immanuel Albrecht, 2020-202x
License     : BSD-3
Maintainer  : mail@immanuel-albrecht.de
Stability   : experimental
Portability : POSIX

This module contains hspec test suites that check certain matroid properties.

-}

module Test.Matroid.Suites where
    
import Test.Matroid.Helpers
import Test.QuickCheck
import Test.Hspec

import Data.Matroid


import qualified Data.Set as S

-- | all tests that any matroid should/must pass
matroidSuite :: (Matroid m a, Show (m a)) => Gen (m a) {- ^ matroid test case generator -} -> SpecWith ()
matroidSuite :: Gen (m a) -> SpecWith ()
matroidSuite Gen (m a)
g = do
  Gen (m a) -> SpecWith ()
forall (m :: * -> *) a. Matroid m a => Gen (m a) -> SpecWith ()
rkPropertiesSuite Gen (m a)
g
  Gen (m a) -> SpecWith ()
forall (m :: * -> *) a. Matroid m a => Gen (m a) -> SpecWith ()
indepPropertiesSuite Gen (m a)
g
  Gen (m a) -> SpecWith ()
forall (m :: * -> *) a. Matroid m a => Gen (m a) -> SpecWith ()
basisPropertiesSuite Gen (m a)
g
  Gen (m a) -> SpecWith ()
forall (m :: * -> *) a. Matroid m a => Gen (m a) -> SpecWith ()
clPropertiesSuite Gen (m a)
g
  Gen (m a) -> SpecWith ()
forall (m :: * -> *) a. Matroid m a => Gen (m a) -> SpecWith ()
viaConsistencySuite Gen (m a)
g
  Gen (m a) -> SpecWith ()
forall (m :: * -> *) a. Matroid m a => Gen (m a) -> SpecWith ()
opInvariantsSuite Gen (m a)
g

{- | tests the invariants associated with operations on matroids

   - rk_{M|X}(Y) = rk_M(Y)
   - coRk_{M.X}(Y) = coRk_M(Y)
   
   - rk_(M^*)(Y) = coRk_M(Y)
   
   - loop(M) = coloop(M^*)
   - coloop(M^*) = loop(M)
   
   - groundsets of restriction/contraction
   - restriction is the dual of contraction
-}
opInvariantsSuite :: Matroid m a => Gen (m a) {- ^ matroid test case generator -} -> SpecWith ()
opInvariantsSuite :: Gen (m a) -> SpecWith ()
opInvariantsSuite Gen (m a)
genMatroids = String -> SpecWith () -> SpecWith ()
forall a. HasCallStack => String -> SpecWith a -> SpecWith a
context String
"op invariants" (SpecWith () -> SpecWith ()) -> SpecWith () -> SpecWith ()
forall a b. (a -> b) -> a -> b
$ do
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk_{M|X}(Y) = rk_M(Y)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        m_ :: AMatroid a
m_ = m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m Set a
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
m_ Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"coRk_{M.X}(Y) = coRk_M(Y)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
      m a
m <- Gen (m a)
genMatroids
      [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
      [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
      let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
          y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
          m_ :: AMatroid a
m_ = m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
        in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk m a
m Set a
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk AMatroid a
m_ Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk_(M^*)(Y) = coRk_M(Y)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
      m a
m <- Gen (m a)
genMatroids
      [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
      let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
          m_ :: AMatroid a
m_ = m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m
        in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
m_ Set a
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk m a
m Set a
x
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"loops(M) = coloops(M^*)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
      m a
m <- Gen (m a)
genMatroids
      let m_ :: AMatroid a
m_ = m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m
        in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops AMatroid a
m_ Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops m a
m
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"coloops(M) = loops(M^*)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    let m_ :: AMatroid a
m_ = m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops m a
m Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops AMatroid a
m_
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"groundsets of restriction" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        m1 :: AMatroid a
m1 = m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ Set a
x Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset AMatroid a
m1
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"groundsets of contraction" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        m1 :: AMatroid a
m1 = m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ Set a
x Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset AMatroid a
m1
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via rk)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
mr Set a
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via indep)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep AMatroid a
mr Set a
y Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via basis)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        m1 :: AMatroid a
m1 = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        m2 :: AMatroid a
m2 = (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
        b1 :: Set a
b1 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis AMatroid a
m1 Set a
y
        b2 :: Set a
b2 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis AMatroid a
m2 Set a
y
        c1b1 :: Set a
c1b1 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m1 Set a
b1
        c1b2 :: Set a
c1b2 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m1 Set a
b2
        c2b1 :: Set a
c2b1 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m2 Set a
b1
        c2b2 :: Set a
c2b2 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m2 Set a
b2
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c1b2) Bool -> Bool -> Bool
&& (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c2b1) Bool -> Bool -> Bool
&& (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c2b2)
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via cl)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
mr Set a
y Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via coRk)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk AMatroid a
mr Set a
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (loops)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        mr :: AMatroid a
mr = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops AMatroid a
mr Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops AMatroid a
mc
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (coloops)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        mr :: AMatroid a
mr = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops AMatroid a
mr Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops AMatroid a
mc
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via rk, alternative)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
mr Set a
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via indep, alternative))" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep AMatroid a
mr Set a
y Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via basis, alternative)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        m1 :: AMatroid a
m1 = (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        m2 :: AMatroid a
m2 = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
        b1 :: Set a
b1 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis AMatroid a
m1 Set a
y
        b2 :: Set a
b2 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis AMatroid a
m2 Set a
y
        c1b1 :: Set a
c1b1 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m1 Set a
b1
        c1b2 :: Set a
c1b2 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m1 Set a
b2
        c2b1 :: Set a
c2b1 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m2 Set a
b1
        c2b2 :: Set a
c2b2 = AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
m2 Set a
b2
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c1b2) Bool -> Bool -> Bool
&& (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c2b1) Bool -> Bool -> Bool
&& (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c2b2)
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via cl, alternative)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
mr Set a
y Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (via coRk, alternative)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf [a]
x0
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y :: Set a
y = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
        mr :: AMatroid a
mr = (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk AMatroid a
mr Set a
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
coRk AMatroid a
mc Set a
y
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (loops, alternative)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        mr :: AMatroid a
mr = (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops AMatroid a
mr Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops AMatroid a
mc
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"duality restriction/contraction (coloops, alternative)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        mr :: AMatroid a
mr = (m a
m m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
x)
        mc :: AMatroid a
mc = AMatroid a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual (AMatroid a -> AMatroid a) -> AMatroid a -> AMatroid a
forall a b. (a -> b) -> a -> b
$ (m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m) AMatroid a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops AMatroid a
mr Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== AMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops AMatroid a
mc


{- | test suite for rank axioms 

 The following properties are verified:
  -  rk is monotone increasing
  -  rk(X+{x}) <= rk(X) + 1  (unit increasing)
  -  rk(\emptyset) = 0 (important special case)
  -  rk(X) <= |X| (subcardinal)
  -  rk(A/\B) + rk(A\/B) <= rk(A) + rk(B) (submodular)
-}
rkPropertiesSuite :: Matroid m a => Gen (m a) {- ^ matroid test case generator -} -> SpecWith ()
rkPropertiesSuite :: Gen (m a) -> SpecWith ()
rkPropertiesSuite Gen (m a)
genMatroids = String -> SpecWith () -> SpecWith ()
forall a. HasCallStack => String -> SpecWith a -> SpecWith a
context String
"rk properties" (SpecWith () -> SpecWith ()) -> SpecWith () -> SpecWith ()
forall a b. (a -> b) -> a -> b
$ do
   String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk is monotone increasing" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
e <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
shuffle ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (Set a -> Int) -> [a] -> Bool
forall a. Ord a => (Set a -> Int) -> [a] -> Bool
isMonotoneUnitIncreasing (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m) [a]
e
   String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk({}) == 0" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
     m a
m <- Gen (m a)
genMatroids
     Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m Set a
forall a. Set a
S.empty Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
   String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk is subcardinal" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
      m a
m <- Gen (m a)
genMatroids
      [a]
x <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
      Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m) ([a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
x
   String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk is submodular" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
      m a
m <- Gen (m a)
genMatroids
      [a]
a0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
      [a]
b0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
      let a :: Set a
a = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
a0
          b :: Set a
b = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
b0
        in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m (Set a
a Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.union` Set a
b)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m (Set a
a Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` Set a
b)) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m Set a
a) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m Set a
b)
{- | test suite for indep properties

The following properties are verified:
  -  indep X  &&  Y\subseteq X => indep Y (hereditary)
  -  indep \emptyset
  -  indep X && indep Y && |Y| > |X| => exists y\in Y: indep X+{y} (exchange property)

-}
indepPropertiesSuite :: Matroid m a => Gen (m a) {- ^ matroid test case generator -} -> SpecWith ()
indepPropertiesSuite :: Gen (m a) -> SpecWith ()
indepPropertiesSuite Gen (m a)
genMatroids = String -> SpecWith () -> SpecWith ()
forall a. HasCallStack => String -> SpecWith a -> SpecWith a
context String
"indep properties" (SpecWith () -> SpecWith ()) -> SpecWith () -> SpecWith ()
forall a b. (a -> b) -> a -> b
$ do
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"indep is hereditary" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
e <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
shuffle ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (Set a -> Bool) -> [a] -> Bool
forall a. Ord a => (Set a -> Bool) -> [a] -> Bool
isMonotoneDecreasingBool (m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m) [a]
e
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"indep({}) == True" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m Set a
forall a. Set a
S.empty Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== Bool
True
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"indep obeys the exchange property" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    [a]
y0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x1 :: Set a
x1 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        y1 :: Set a
y1 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
y0
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (Set a -> Bool) -> Set a -> Set a -> Bool
forall a. Ord a => (Set a -> Bool) -> Set a -> Set a -> Bool
hasIndepExchangeProperty (m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m) Set a
x1 Set a
y1
      
{- | test suite for basis properties

The following properties are verified:
  -  basis X \subseteq X
  -  indep (basis X)
  -  y in X\(basis X) => not indep (basis X)+{y}

-}
basisPropertiesSuite :: Matroid m a => Gen (m a) {- ^ matroid test case generator -} -> SpecWith ()
basisPropertiesSuite :: Gen (m a) -> SpecWith ()
basisPropertiesSuite Gen (m a)
genMatroids = String -> SpecWith () -> SpecWith ()
forall a. HasCallStack => String -> SpecWith a -> SpecWith a
context String
"basis properties" (SpecWith () -> SpecWith ()) -> SpecWith () -> SpecWith ()
forall a b. (a -> b) -> a -> b
$ do
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"basis(X) is a subset of X" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        b :: Set a
b = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ Set a
b Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
`S.isSubsetOf` Set a
x
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"basis(X) is independent" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        b :: Set a
b = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m Set a
b
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"basis(X) is maximally independent" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        b :: Set a
b = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m Set a
x
        result :: Bool
result
          | m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m Set a
x = Set a
b Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
x
          | Bool
otherwise = (a -> Bool) -> Set a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all a -> Bool
augNotIndep (Set a -> Bool) -> Set a -> Bool
forall a b. (a -> b) -> a -> b
$ Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.difference Set a
x Set a
b
        augNotIndep :: a -> Bool
augNotIndep a
y = Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
(==) Bool
False (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m (Set a -> Bool) -> Set a -> Bool
forall a b. (a -> b) -> a -> b
$ a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
y Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ Bool
result
{- | test suite for closure operator properties 

The following properties are verified:
  -  cl is monotone
  -  cl(X) \subseteq E
  -  cl(cl(X)) == cl(X) (idempotence)
  -  e \in E\X, y\in cl(X+{e})\cl(X) => e \in cl(X+{y})
  -  rk(X) == rk(cl(X)) and cl(X) is maximal with this property

-}
clPropertiesSuite :: Matroid m a => Gen (m a) {- ^ matroid test case generator -} -> SpecWith ()
clPropertiesSuite :: Gen (m a) -> SpecWith ()
clPropertiesSuite Gen (m a)
genMatroids = String -> SpecWith () -> SpecWith ()
forall a. HasCallStack => String -> SpecWith a -> SpecWith a
context String
"cl properties" (SpecWith () -> SpecWith ()) -> SpecWith () -> SpecWith ()
forall a b. (a -> b) -> a -> b
$ do
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"cl is extensive" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
e <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
shuffle ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (Set a -> Set a) -> [a] -> Bool
forall a. Ord a => (Set a -> Set a) -> [a] -> Bool
isIsotoneSetMap (m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m) [a]
e
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"cl(E) == E" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m) Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"cl is idempotent" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
        c :: Set a
c = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m Set a
x
        cc :: Set a
cc = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m Set a
c
     in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ Set a
c Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
cc
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"cl satisfies the exchange property" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0 
        cx :: Set a
cx = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m Set a
x -- cl(X)
        es :: Set a
es = (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m) Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.difference` Set a
x -- E\X
        cxy :: a -> Set a
cxy a
y = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m (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
y Set a
x -- cl(X+{y})
        result :: Bool
result = (a -> Bool) -> Set a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all a -> Bool
testAllExchanges Set a
es  -- binds e\in E\X
        testAllExchanges :: a -> Bool
testAllExchanges a
e_ = (a -> Bool) -> Set a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a -> a -> Bool
testExchange a
e_) -- binds y
           (Set a -> Bool) -> Set a -> Bool
forall a b. (a -> b) -> a -> b
$ (m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m (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
e_ Set a
x) Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`S.difference` Set a
cx -- cl(X+{e})\cl(X)
        testExchange :: a -> a -> Bool
testExchange a
e__ a
y_ = a
e__ a -> Set a -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` a -> Set a
cxy a
y_ -- e \in cl(X+{y})
        in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ Bool
result
  String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk(cl(X)) == rk(X)" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$ Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
    m a
m <- Gen (m a)
genMatroids
    [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
    let x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0 
        cx :: Set a
cx = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m Set a
x
      in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m Set a
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m Set a
cx
      
{- | tests a given matroid implementation for equality against the default implementations
    
  rk, indep, and cl should produce the same output when given the same input.
  
  basis however is only required to produce a basis of the given subset, and which basis is
  produced really depends on how the basis is derived. Here, we are ok if b1 and b2 have
    cl1(b1) == cl1(b2) == cl2(b1) == cl2(b2).
-}
viaConsistencySuite :: Matroid m a => Gen (m a) {- ^ matroid test case generator -} -> SpecWith ()
viaConsistencySuite :: Gen (m a) -> SpecWith ()
viaConsistencySuite Gen (m a)
genMatroids = String -> SpecWith () -> SpecWith ()
forall a. HasCallStack => String -> SpecWith a -> SpecWith a
context String
"implementation consistency" (SpecWith () -> SpecWith ()) -> SpecWith () -> SpecWith ()
forall a b. (a -> b) -> a -> b
$ do
  let via_rk :: m a -> RkMatroid a
via_rk m a
m_ = String -> Set a -> (Set a -> Int) -> RkMatroid a
forall a. String -> Set a -> (Set a -> Int) -> RkMatroid a
namedFromRk (String
"via_rk $ " String -> String -> String
forall a. [a] -> [a] -> [a]
++ m a -> String
forall (m :: * -> *) a. Matroid m a => m a -> String
showName m a
m_) (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_) (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m_)
      via_indep :: m a -> IndepMatroid a
via_indep m a
m_ = String -> Set a -> (Set a -> Bool) -> IndepMatroid a
forall a. String -> Set a -> (Set a -> Bool) -> IndepMatroid a
namedFromIndep (String
"via_indep $ " String -> String -> String
forall a. [a] -> [a] -> [a]
++ m a -> String
forall (m :: * -> *) a. Matroid m a => m a -> String
showName m a
m_) (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_) (m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m_)
      via_basis :: m a -> BasisFilterMatroid a
via_basis m a
m_ = String -> Set a -> (Set a -> Set a) -> BasisFilterMatroid a
forall a.
String -> Set a -> (Set a -> Set a) -> BasisFilterMatroid a
namedFromBasisFilter (String
"via_basis $ " String -> String -> String
forall a. [a] -> [a] -> [a]
++ m a -> String
forall (m :: * -> *) a. Matroid m a => m a -> String
showName m a
m_) (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_) (m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m_)
      check_eq :: (m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> t
via_x m a -> Set a -> a
fn1 t -> Set a -> a
fn2 = -- fn1 and fn2 are the same function but wrt. different types
       Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do 
        m a
m1 <- Gen (m a)
genMatroids
        [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m1
        let m2 :: t
m2 = m a -> t
via_x m a
m1
            x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
          in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> a
fn1 m a
m1 Set a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== t -> Set a -> a
fn2 t
m2 Set a
x
      check_eq_set :: (m a -> t) -> (m a -> a) -> (t -> a) -> Property
check_eq_set m a -> t
via_x m a -> a
fn1 t -> a
fn2 = -- fn1 and fn2 are the same function but wrt. different types
       Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do 
        m a
m1 <- Gen (m a)
genMatroids
        let m2 :: t
m2 = m a -> t
via_x m a
m1
          in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ m a -> a
fn1 m a
m1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== t -> a
fn2 t
m2 
      check_basis :: (m a -> m a) -> Property
check_basis m a -> m a
via_x =
       Gen Bool -> Property
forall prop. Testable prop => prop -> Property
property (Gen Bool -> Property) -> Gen Bool -> Property
forall a b. (a -> b) -> a -> b
$ do
        m a
m1 <- Gen (m a)
genMatroids
        [a]
x0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m1
        let m2 :: m a
m2 = m a -> m a
via_x m a
m1
            x :: Set a
x = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
x0
            b1 :: Set a
b1 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m1 Set a
x
            b2 :: Set a
b2 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m2 Set a
x
            c1b1 :: Set a
c1b1 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m1 Set a
b1
            c1b2 :: Set a
c1b2 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m1 Set a
b2
            c2b1 :: Set a
c2b1 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m2 Set a
b1
            c2b2 :: Set a
c2b2 = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m2 Set a
b2
          in Bool -> Gen Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Gen Bool) -> Bool -> Gen Bool
forall a b. (a -> b) -> a -> b
$ (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c1b2) Bool -> Bool -> Bool
&& (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c2b1) Bool -> Bool -> Bool
&& (Set a
c1b1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
c2b2)
    in do
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"indep wrt. rk matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> RkMatroid a)
-> (m a -> Set a -> Bool)
-> (RkMatroid a -> Set a -> Bool)
-> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> RkMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> RkMatroid a
via_rk m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep RkMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"cl wrt. rk matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> RkMatroid a)
-> (m a -> Set a -> Set a)
-> (RkMatroid a -> Set a -> Set a)
-> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> RkMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> RkMatroid a
via_rk m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl RkMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"basis wrt. rk matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> RkMatroid a) -> Property
forall (m :: * -> *). Matroid m a => (m a -> m a) -> Property
check_basis m a -> RkMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> RkMatroid a
via_rk
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"loop wrt. rk matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> RkMatroid a)
-> (m a -> Set a) -> (RkMatroid a -> Set a) -> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> a) -> (t -> a) -> Property
check_eq_set m a -> RkMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> RkMatroid a
via_rk m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops RkMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"coloop wrt. rk matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> RkMatroid a)
-> (m a -> Set a) -> (RkMatroid a -> Set a) -> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> a) -> (t -> a) -> Property
check_eq_set m a -> RkMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> RkMatroid a
via_rk m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops RkMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk wrt. indep matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> IndepMatroid a)
-> (m a -> Set a -> Int)
-> (IndepMatroid a -> Set a -> Int)
-> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> IndepMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> IndepMatroid a
via_indep m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk IndepMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"cl wrt. indep matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> IndepMatroid a)
-> (m a -> Set a -> Set a)
-> (IndepMatroid a -> Set a -> Set a)
-> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> IndepMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> IndepMatroid a
via_indep m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl IndepMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"basis wrt. indep matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> IndepMatroid a) -> Property
forall (m :: * -> *). Matroid m a => (m a -> m a) -> Property
check_basis m a -> IndepMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> IndepMatroid a
via_indep
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"loop wrt. indep matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> IndepMatroid a)
-> (m a -> Set a) -> (IndepMatroid a -> Set a) -> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> a) -> (t -> a) -> Property
check_eq_set m a -> IndepMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> IndepMatroid a
via_indep m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops IndepMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"coloop wrt. indep matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> IndepMatroid a)
-> (m a -> Set a) -> (IndepMatroid a -> Set a) -> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> a) -> (t -> a) -> Property
check_eq_set m a -> IndepMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> IndepMatroid a
via_indep m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops IndepMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"indep wrt. basis matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> BasisFilterMatroid a)
-> (m a -> Set a -> Bool)
-> (BasisFilterMatroid a -> Set a -> Bool)
-> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> BasisFilterMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> BasisFilterMatroid a
via_basis m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep BasisFilterMatroid a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"rk wrt. basis matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> BasisFilterMatroid a)
-> (m a -> Set a -> Int)
-> (BasisFilterMatroid a -> Set a -> Int)
-> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> BasisFilterMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> BasisFilterMatroid a
via_basis m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk BasisFilterMatroid a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"cl wrt. basis matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> BasisFilterMatroid a)
-> (m a -> Set a -> Set a)
-> (BasisFilterMatroid a -> Set a -> Set a)
-> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> Set a -> a) -> (t -> Set a -> a) -> Property
check_eq m a -> BasisFilterMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> BasisFilterMatroid a
via_basis m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl BasisFilterMatroid a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"loop wrt. basis matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> BasisFilterMatroid a)
-> (m a -> Set a) -> (BasisFilterMatroid a -> Set a) -> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> a) -> (t -> a) -> Property
check_eq_set m a -> BasisFilterMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> BasisFilterMatroid a
via_basis m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops BasisFilterMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops
      String -> Property -> SpecWith (Arg Property)
forall a.
(HasCallStack, Example a) =>
String -> a -> SpecWith (Arg a)
it String
"coloop wrt. basis matroid" (Property -> SpecWith (Arg Property))
-> Property -> SpecWith (Arg Property)
forall a b. (a -> b) -> a -> b
$  (m a -> BasisFilterMatroid a)
-> (m a -> Set a) -> (BasisFilterMatroid a -> Set a) -> Property
forall a t.
Eq a =>
(m a -> t) -> (m a -> a) -> (t -> a) -> Property
check_eq_set m a -> BasisFilterMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> BasisFilterMatroid a
via_basis m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops BasisFilterMatroid a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
coloops