{-# LANGUAGE UndecidableInstances, OverlappingInstances, TemplateHaskell, CPP, FlexibleInstances #-}
module MagicHaskeller.Classification
where
import Prelude hiding ((/))
#ifdef TFRANDOM
import System.Random.TF.Gen
#else
import System.Random
#endif
import MagicHaskeller.MyCheck
import Data.Char
import Data.List
import Control.Monad
import Control.Monad.Search.Combinatorial
import Data.Complex
import MagicHaskeller.MHTH
import MagicHaskeller.TimeOut
import MagicHaskeller.T10
import MagicHaskeller.Instantiate(compareRealFloat)
class (Search m) => SStrategy m where
sfilter :: Relation r =>
(k->k->r) -> (Int->Int) -> m ([k],e) -> m ([k],e)
ofilter :: Relation r =>
(k->k->r) -> m (k,e) -> m (k,e)
instance SStrategy Matrix where
sfilter :: (k -> k -> r) -> (Int -> Int) -> Matrix ([k], e) -> Matrix ([k], e)
sfilter = (k -> k -> r) -> (Int -> Int) -> Matrix ([k], e) -> Matrix ([k], e)
forall r k e.
Relation r =>
(k -> k -> r) -> (Int -> Int) -> Matrix ([k], e) -> Matrix ([k], e)
sfilterMx
ofilter :: (k -> k -> r) -> Matrix (k, e) -> Matrix (k, e)
ofilter = (k -> k -> r) -> Matrix (k, e) -> Matrix (k, e)
forall r k e.
Relation r =>
(k -> k -> r) -> Matrix (k, e) -> Matrix (k, e)
ofilterMx
instance SStrategy DBound where
sfilter :: (k -> k -> r) -> (Int -> Int) -> DBound ([k], e) -> DBound ([k], e)
sfilter = (k -> k -> r) -> (Int -> Int) -> DBound ([k], e) -> DBound ([k], e)
forall r k e.
Relation r =>
(k -> k -> r) -> (Int -> Int) -> DBound ([k], e) -> DBound ([k], e)
sfilterDB
ofilter :: (k -> k -> r) -> DBound (k, e) -> DBound (k, e)
ofilter = (k -> k -> r) -> DBound (k, e) -> DBound (k, e)
forall r k e.
Relation r =>
(k -> k -> r) -> DBound (k, e) -> DBound (k, e)
ofilterDB
#ifdef TFRANDOM
arbitraries :: Arbitrary a => [a]
arbitraries = arbs 0 (seedTFGen (12279932681387497184,218462391894233257,1625759680792809304,12756118543158863164))
arbs :: Arbitrary a => Int -> TFGen -> [a]
arbs n stdgen = case map (splitn stdgen 8) [0..255] of
g0:gs -> zipWith f [n..] gs ++ arbs (n+255) g0
where Gen f = arbitrary
#else
arbitraries :: Arbitrary a => [a]
arbitraries :: [a]
arbitraries = Int -> StdGen -> [a]
forall a. Arbitrary a => Int -> StdGen -> [a]
arbs Int
0 (Int -> StdGen
mkStdGen Int
1)
arbs :: Arbitrary a => Int -> StdGen -> [a]
arbs :: Int -> StdGen -> [a]
arbs Int
n StdGen
stdgen = case StdGen -> (StdGen, StdGen)
forall g. RandomGen g => g -> (g, g)
split StdGen
stdgen of
(StdGen
g0,StdGen
g1) -> Int -> StdGen -> a
f Int
n StdGen
g0 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Int -> StdGen -> [a]
forall a. Arbitrary a => Int -> StdGen -> [a]
arbs (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) StdGen
g1
where Gen Int -> StdGen -> a
f = Gen a
forall a. Arbitrary a => Gen a
arbitrary
#endif
(/~) :: [a] -> (a->a->Bool) -> [[a]]
[] /~ :: [a] -> (a -> a -> Bool) -> [[a]]
/~ a -> a -> Bool
eq = []
(a
x:[a]
xs) /~ a -> a -> Bool
eq = case (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition (a
x a -> a -> Bool
`eq`) [a]
xs of
([a]
same, [a]
diff) -> (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
same) [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: ([a]
diff [a] -> (a -> a -> Bool) -> [[a]]
forall a. [a] -> (a -> a -> Bool) -> [[a]]
/~ a -> a -> Bool
eq)
nubSortBy :: (a->a->Ordering) -> [a] -> [a]
nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]
nubSortBy = (a -> a -> a) -> (a -> a -> Ordering) -> [a] -> [a]
forall k. (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k]
mergesortWithBy a -> a -> a
forall a b. a -> b -> a
const
nubSortByBot :: (a->a->Maybe Ordering) -> [a] -> [a]
nubSortByBot :: (a -> a -> Maybe Ordering) -> [a] -> [a]
nubSortByBot = (a -> a -> a) -> (a -> a -> Maybe Ordering) -> [a] -> [a]
forall k. (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k]
mergesortWithByBot a -> a -> a
forall a b. a -> b -> a
const
(/<) :: [a] -> (a->a->Ordering) -> [[a]]
[a]
xs /< :: [a] -> (a -> a -> Ordering) -> [[a]]
/< a -> a -> Ordering
cmp = ([a] -> [a] -> [a]) -> ([a] -> [a] -> Ordering) -> [[a]] -> [[a]]
forall k. (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k]
mergesortWithBy [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
(++)
(\[a]
x [a]
y -> [a] -> a
forall a. [a] -> a
head [a]
x a -> a -> Ordering
`cmp` [a] -> a
forall a. [a] -> a
head [a]
y)
((a -> [a]) -> [a] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
xs)
(/<?) :: [a] -> (a->a->Maybe Ordering) -> [[a]]
[a]
xs /<? :: [a] -> (a -> a -> Maybe Ordering) -> [[a]]
/<? a -> a -> Maybe Ordering
cmp = ([a] -> [a] -> [a])
-> ([a] -> [a] -> Maybe Ordering) -> [[a]] -> [[a]]
forall k. (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k]
mergesortWithByBot [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
(++)
(\[a]
x [a]
y -> [a] -> a
forall a. [a] -> a
head [a]
x a -> a -> Maybe Ordering
`cmp` [a] -> a
forall a. [a] -> a
head [a]
y)
((a -> [a]) -> [a] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
xs)
class Eq rel => Relation rel where
fromListBy :: (k->k->rel) -> [k] -> [k]
fromListBy k -> k -> rel
cmp = ([k] -> k) -> [[k]] -> [k]
forall a b. (a -> b) -> [a] -> [b]
map [k] -> k
forall a. [a] -> a
head ([[k]] -> [k]) -> ([k] -> [[k]]) -> [k] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([k] -> (k -> k -> rel) -> [[k]]
forall rel k. Relation rel => [k] -> (k -> k -> rel) -> [[k]]
/k -> k -> rel
cmp)
fromListByDB :: (k->k->rel) -> [(k,Int)] -> [(k,Int)]
fromListByDB k -> k -> rel
rel [(k, Int)]
ts =
([(k, Int)] -> (k, Int)) -> [[(k, Int)]] -> [(k, Int)]
forall a b. (a -> b) -> [a] -> [b]
map (((k, Int) -> (k, Int) -> Ordering) -> [(k, Int)] -> (k, Int)
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
minimumBy (\(k, Int)
x (k, Int)
y -> Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ((k, Int) -> Int
forall a b. (a, b) -> b
snd (k, Int)
y) ((k, Int) -> Int
forall a b. (a, b) -> b
snd (k, Int)
x)))
([(k, Int)]
ts [(k, Int)] -> ((k, Int) -> (k, Int) -> rel) -> [[(k, Int)]]
forall rel k. Relation rel => [k] -> (k -> k -> rel) -> [[k]]
/ (\(k, Int)
x (k, Int)
y -> k -> k -> rel
rel ((k, Int) -> k
forall a b. (a, b) -> a
fst (k, Int)
x) ((k, Int) -> k
forall a b. (a, b) -> a
fst (k, Int)
y)))
(/) :: [k] -> (k->k->rel) -> [[k]]
appendWithBy :: (k->k->k) ->
(k->k->rel) -> [k] -> [k] -> [k]
diffBy :: (k -> k -> rel) -> [k] -> [k] -> [k]
cEQ :: rel
appendQuotientsBy ::
(Relation rel) =>
(k -> k -> rel) -> [[k]] -> [[k]] -> [[k]]
appendQuotientsBy :: (k -> k -> rel) -> [[k]] -> [[k]] -> [[k]]
appendQuotientsBy k -> k -> rel
rel =
([k] -> [k] -> [k])
-> ([k] -> [k] -> rel) -> [[k]] -> [[k]] -> [[k]]
forall rel k.
Relation rel =>
(k -> k -> k) -> (k -> k -> rel) -> [k] -> [k] -> [k]
appendWithBy [k] -> [k] -> [k]
forall a. [a] -> [a] -> [a]
(++) (\ (k
x:[k]
_) (k
y:[k]
_) -> k
x k -> k -> rel
`rel` k
y)
appendRepresentativesBy ::
(Relation rel) =>
(k -> k -> rel) -> [k] -> [k] -> [k]
appendRepresentativesBy :: (k -> k -> rel) -> [k] -> [k] -> [k]
appendRepresentativesBy = (k -> k -> k) -> (k -> k -> rel) -> [k] -> [k] -> [k]
forall rel k.
Relation rel =>
(k -> k -> k) -> (k -> k -> rel) -> [k] -> [k] -> [k]
appendWithBy k -> k -> k
forall a b. a -> b -> a
const
instance Relation Bool where
fromListBy :: (k -> k -> Bool) -> [k] -> [k]
fromListBy = (k -> k -> Bool) -> [k] -> [k]
forall k. (k -> k -> Bool) -> [k] -> [k]
Data.List.nubBy
/ :: [k] -> (k -> k -> Bool) -> [[k]]
(/) = [k] -> (k -> k -> Bool) -> [[k]]
forall a. [a] -> (a -> a -> Bool) -> [[a]]
(/~)
appendWithBy :: (k -> k -> k) -> (k -> k -> Bool) -> [k] -> [k] -> [k]
appendWithBy = (k -> k -> k) -> (k -> k -> Bool) -> [k] -> [k] -> [k]
forall k. (k -> k -> k) -> (k -> k -> Bool) -> [k] -> [k] -> [k]
unionWithBy
diffBy :: (k -> k -> Bool) -> [k] -> [k] -> [k]
diffBy = (k -> k -> Bool) -> [k] -> [k] -> [k]
forall k. (k -> k -> Bool) -> [k] -> [k] -> [k]
Data.List.deleteFirstsBy
cEQ :: Bool
cEQ = Bool
True
unionWithBy :: (a -> a -> a) -> (a -> a -> Bool) -> [a] -> [a] -> [a]
unionWithBy a -> a -> a
combiner a -> a -> Bool
eq [] [a]
ys = [a]
ys
unionWithBy a -> a -> a
combiner a -> a -> Bool
eq (a
x:[a]
xs) [a]
ys =
case (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
break (a -> a -> Bool
eq a
x) [a]
ys of
([a]
_, []) -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> a -> a) -> (a -> a -> Bool) -> [a] -> [a] -> [a]
unionWithBy a -> a -> a
combiner a -> a -> Bool
eq [a]
xs [a]
ys
([a]
ts, a
h:[a]
ds) -> (a
x a -> a -> a
`combiner` a
h)
a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> a -> a) -> (a -> a -> Bool) -> [a] -> [a] -> [a]
unionWithBy a -> a -> a
combiner a -> a -> Bool
eq [a]
xs ([a]
ts[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a]
ds)
instance Relation Ordering where
fromListBy :: (k -> k -> Ordering) -> [k] -> [k]
fromListBy = (k -> k -> Ordering) -> [k] -> [k]
forall k. (k -> k -> Ordering) -> [k] -> [k]
nubSortBy
fromListByDB :: (k -> k -> Ordering) -> [(k, Int)] -> [(k, Int)]
fromListByDB k -> k -> Ordering
rel =
((k, Int) -> (k, Int) -> (k, Int))
-> ((k, Int) -> (k, Int) -> Ordering) -> [(k, Int)] -> [(k, Int)]
forall k. (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k]
mergesortWithBy
(\(k, Int)
x (k, Int)
y -> if (k, Int) -> Int
forall a b. (a, b) -> b
snd (k, Int)
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< (k, Int) -> Int
forall a b. (a, b) -> b
snd (k, Int)
y then (k, Int)
y else (k, Int)
x)
(\(k, Int)
x (k, Int)
y -> (k, Int) -> k
forall a b. (a, b) -> a
fst (k, Int)
x k -> k -> Ordering
`rel` (k, Int) -> k
forall a b. (a, b) -> a
fst (k, Int)
y)
/ :: [k] -> (k -> k -> Ordering) -> [[k]]
(/) = [k] -> (k -> k -> Ordering) -> [[k]]
forall k. [k] -> (k -> k -> Ordering) -> [[k]]
(/<)
appendWithBy :: (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k] -> [k]
appendWithBy = (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k] -> [k]
mergeWithBy
diffBy :: (k -> k -> Ordering) -> [k] -> [k] -> [k]
diffBy = (k -> k -> Ordering) -> [k] -> [k] -> [k]
forall a t. (a -> t -> Ordering) -> [a] -> [t] -> [a]
diffSortedBy
cEQ :: Ordering
cEQ = Ordering
EQ
instance Relation (Maybe Ordering) where
fromListBy :: (k -> k -> Maybe Ordering) -> [k] -> [k]
fromListBy = (k -> k -> Maybe Ordering) -> [k] -> [k]
forall k. (k -> k -> Maybe Ordering) -> [k] -> [k]
nubSortByBot
fromListByDB :: (k -> k -> Maybe Ordering) -> [(k, Int)] -> [(k, Int)]
fromListByDB k -> k -> Maybe Ordering
rel =
((k, Int) -> (k, Int) -> (k, Int))
-> ((k, Int) -> (k, Int) -> Maybe Ordering)
-> [(k, Int)]
-> [(k, Int)]
forall k. (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k]
mergesortWithByBot
(\(k, Int)
x (k, Int)
y -> if (k, Int) -> Int
forall a b. (a, b) -> b
snd (k, Int)
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< (k, Int) -> Int
forall a b. (a, b) -> b
snd (k, Int)
y then (k, Int)
y else (k, Int)
x)
(\(k, Int)
x (k, Int)
y -> (k, Int) -> k
forall a b. (a, b) -> a
fst (k, Int)
x k -> k -> Maybe Ordering
`rel` (k, Int) -> k
forall a b. (a, b) -> a
fst (k, Int)
y)
/ :: [k] -> (k -> k -> Maybe Ordering) -> [[k]]
(/) = [k] -> (k -> k -> Maybe Ordering) -> [[k]]
forall k. [k] -> (k -> k -> Maybe Ordering) -> [[k]]
(/<?)
appendWithBy :: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
appendWithBy = (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot
diffBy :: (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
diffBy = (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall a t. (a -> t -> Maybe Ordering) -> [a] -> [t] -> [a]
diffSortedByBot
cEQ :: Maybe Ordering
cEQ = Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just Ordering
EQ
randomTestFilter :: (SStrategy m, Filtrable a) =>
(Int->Int) -> m (e,a) -> m (e,a)
randomTestFilter :: (Int -> Int) -> m (e, a) -> m (e, a)
randomTestFilter Int -> Int
numRandoms = (Int -> Int) -> m (a, (e, a)) -> m (e, a)
forall a (m :: * -> *) e.
(Filtrable a, SStrategy m) =>
(Int -> Int) -> m (a, e) -> m e
filt Int -> Int
numRandoms (m (a, (e, a)) -> m (e, a))
-> (m (e, a) -> m (a, (e, a))) -> m (e, a) -> m (e, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((e, a) -> (a, (e, a))) -> m (e, a) -> m (a, (e, a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\ t :: (e, a)
t@(e
_,a
a) -> (a
a,(e, a)
t))
unsafeRandomTestFilter :: (SStrategy m, Filtrable a) =>
Maybe Int
-> (Int->Int) -> m (e,a) -> m (e,a)
unsafeRandomTestFilter :: Maybe Int -> (Int -> Int) -> m (e, a) -> m (e, a)
unsafeRandomTestFilter Maybe Int
mto Int -> Int
numRandoms = Maybe Int -> (Int -> Int) -> m (a, (e, a)) -> m (e, a)
forall a (m :: * -> *) e.
(Filtrable a, SStrategy m) =>
Maybe Int -> (Int -> Int) -> m (a, e) -> m e
unsafeFilt Maybe Int
mto Int -> Int
numRandoms (m (a, (e, a)) -> m (e, a))
-> (m (e, a) -> m (a, (e, a))) -> m (e, a) -> m (e, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((e, a) -> (a, (e, a))) -> m (e, a) -> m (a, (e, a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\ t :: (e, a)
t@(e
_,a
a) -> (a
a,(e, a)
t))
mapFst :: (t -> a) -> (t, b) -> (a, b)
mapFst t -> a
f (t
a,b
b) = (t -> a
f t
a, b
b)
class Filtrable a where
filt :: SStrategy m => (Int->Int) -> m (a,e) -> m e
filtFun :: (SStrategy m, Arbitrary b) =>
(Int->Int) -> m (b->a,e) -> m e
unsafeFilt :: SStrategy m =>
Maybe Int -> (Int->Int) -> m (a,e) -> m e
unsafeFiltFun :: (SStrategy m, Arbitrary b) =>
Maybe Int -> (Int->Int) -> m (b->a,e) -> m e
instance (Arbitrary a, Filtrable r) => Filtrable (a->r)
where
filt :: (Int -> Int) -> m (a -> r, e) -> m e
filt = (Int -> Int) -> m (a -> r, e) -> m e
forall a (m :: * -> *) b e.
(Filtrable a, SStrategy m, Arbitrary b) =>
(Int -> Int) -> m (b -> a, e) -> m e
filtFun
filtFun :: (Int -> Int) -> m (b -> a -> r, e) -> m e
filtFun Int -> Int
f = (Int -> Int) -> m ((b, a) -> r, e) -> m e
forall a (m :: * -> *) e.
(Filtrable a, SStrategy m) =>
(Int -> Int) -> m (a, e) -> m e
filt Int -> Int
f (m ((b, a) -> r, e) -> m e)
-> (m (b -> a -> r, e) -> m ((b, a) -> r, e))
-> m (b -> a -> r, e)
-> m e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b -> a -> r, e) -> ((b, a) -> r, e))
-> m (b -> a -> r, e) -> m ((b, a) -> r, e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((b -> a -> r) -> (b, a) -> r)
-> (b -> a -> r, e) -> ((b, a) -> r, e)
forall t a b. (t -> a) -> (t, b) -> (a, b)
mapFst (b -> a -> r) -> (b, a) -> r
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry)
unsafeFilt :: Maybe Int -> (Int -> Int) -> m (a -> r, e) -> m e
unsafeFilt Maybe Int
mto Int -> Int
f = Maybe Int -> (Int -> Int) -> m (a -> r, e) -> m e
forall a (m :: * -> *) b e.
(Filtrable a, SStrategy m, Arbitrary b) =>
Maybe Int -> (Int -> Int) -> m (b -> a, e) -> m e
unsafeFiltFun Maybe Int
mto Int -> Int
f
unsafeFiltFun :: Maybe Int -> (Int -> Int) -> m (b -> a -> r, e) -> m e
unsafeFiltFun Maybe Int
mto Int -> Int
f = Maybe Int -> (Int -> Int) -> m ((b, a) -> r, e) -> m e
forall a (m :: * -> *) e.
(Filtrable a, SStrategy m) =>
Maybe Int -> (Int -> Int) -> m (a, e) -> m e
unsafeFilt Maybe Int
mto Int -> Int
f (m ((b, a) -> r, e) -> m e)
-> (m (b -> a -> r, e) -> m ((b, a) -> r, e))
-> m (b -> a -> r, e)
-> m e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b -> a -> r, e) -> ((b, a) -> r, e))
-> m (b -> a -> r, e) -> m ((b, a) -> r, e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((b -> a -> r) -> (b, a) -> r)
-> (b -> a -> r, e) -> ((b, a) -> r, e)
forall t a b. (t -> a) -> (t, b) -> (a, b)
mapFst (b -> a -> r) -> (b, a) -> r
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry)
#ifdef TESTEQ
instance Eq a => Filtrable a where
filt = filtNullary (==)
filtFun = filtUnary (==)
#else
instance Ord a => Filtrable a where
filt :: (Int -> Int) -> m (a, e) -> m e
filt = (a -> a -> Ordering) -> (Int -> Int) -> m (a, e) -> m e
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> (Int -> Int) -> m (k, e) -> m e
filtNullary a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
filtFun :: (Int -> Int) -> m (b -> a, e) -> m e
filtFun = (a -> a -> Ordering) -> (Int -> Int) -> m (b -> a, e) -> m e
forall (f :: * -> *) r a k b.
(SStrategy f, Relation r, Arbitrary a) =>
(k -> k -> r) -> (Int -> Int) -> f (a -> k, b) -> f b
filtUnary a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
unsafeFilt :: Maybe Int -> (Int -> Int) -> m (a, e) -> m e
unsafeFilt Maybe Int
mto = (a -> a -> Maybe Ordering) -> (Int -> Int) -> m (a, e) -> m e
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> (Int -> Int) -> m (k, e) -> m e
filtNullary (Maybe Int -> (a -> a -> Ordering) -> a -> a -> Maybe Ordering
forall a b c. Maybe Int -> (a -> b -> c) -> a -> b -> Maybe c
unsafeOpWithPTO Maybe Int
mto a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare)
unsafeFiltFun :: Maybe Int -> (Int -> Int) -> m (b -> a, e) -> m e
unsafeFiltFun Maybe Int
mto = (a -> a -> Maybe Ordering) -> (Int -> Int) -> m (b -> a, e) -> m e
forall (f :: * -> *) r a k b.
(SStrategy f, Relation r, Arbitrary a) =>
(k -> k -> r) -> (Int -> Int) -> f (a -> k, b) -> f b
filtUnary (Maybe Int -> (a -> a -> Ordering) -> a -> a -> Maybe Ordering
forall a b c. Maybe Int -> (a -> b -> c) -> a -> b -> Maybe c
unsafeOpWithPTO Maybe Int
mto a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare)
instance Filtrable Double where
filt :: (Int -> Int) -> m (Double, e) -> m e
filt = (Double -> Double -> Ordering)
-> (Int -> Int) -> m (Double, e) -> m e
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> (Int -> Int) -> m (k, e) -> m e
filtNullary Double -> Double -> Ordering
forall a. (NearEq a, RealFloat a) => a -> a -> Ordering
compareRealFloat
filtFun :: (Int -> Int) -> m (b -> Double, e) -> m e
filtFun = (Double -> Double -> Ordering)
-> (Int -> Int) -> m (b -> Double, e) -> m e
forall (f :: * -> *) r a k b.
(SStrategy f, Relation r, Arbitrary a) =>
(k -> k -> r) -> (Int -> Int) -> f (a -> k, b) -> f b
filtUnary Double -> Double -> Ordering
forall a. (NearEq a, RealFloat a) => a -> a -> Ordering
compareRealFloat
unsafeFilt :: Maybe Int -> (Int -> Int) -> m (Double, e) -> m e
unsafeFilt Maybe Int
mto = (Double -> Double -> Maybe Ordering)
-> (Int -> Int) -> m (Double, e) -> m e
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> (Int -> Int) -> m (k, e) -> m e
filtNullary (Maybe Int
-> (Double -> Double -> Ordering)
-> Double
-> Double
-> Maybe Ordering
forall a b c. Maybe Int -> (a -> b -> c) -> a -> b -> Maybe c
unsafeOpWithPTO Maybe Int
mto Double -> Double -> Ordering
forall a. (NearEq a, RealFloat a) => a -> a -> Ordering
compareRealFloat)
unsafeFiltFun :: Maybe Int -> (Int -> Int) -> m (b -> Double, e) -> m e
unsafeFiltFun Maybe Int
mto = (Double -> Double -> Maybe Ordering)
-> (Int -> Int) -> m (b -> Double, e) -> m e
forall (f :: * -> *) r a k b.
(SStrategy f, Relation r, Arbitrary a) =>
(k -> k -> r) -> (Int -> Int) -> f (a -> k, b) -> f b
filtUnary (Maybe Int
-> (Double -> Double -> Ordering)
-> Double
-> Double
-> Maybe Ordering
forall a b c. Maybe Int -> (a -> b -> c) -> a -> b -> Maybe c
unsafeOpWithPTO Maybe Int
mto Double -> Double -> Ordering
forall a. (NearEq a, RealFloat a) => a -> a -> Ordering
compareRealFloat)
#endif
filtNullary :: (SStrategy m, Relation r) =>
(k->k->r) -> (Int->Int) -> m (k,e) -> m e
filtNullary :: (k -> k -> r) -> (Int -> Int) -> m (k, e) -> m e
filtNullary k -> k -> r
op Int -> Int
_ = ((k, e) -> e) -> m (k, e) -> m e
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, e) -> e
forall a b. (a, b) -> b
snd (m (k, e) -> m e) -> (m (k, e) -> m (k, e)) -> m (k, e) -> m e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> k -> r) -> m (k, e) -> m (k, e)
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> m (k, e) -> m (k, e)
ofilter k -> k -> r
op
filtUnary :: (k -> k -> r) -> (Int -> Int) -> f (a -> k, b) -> f b
filtUnary k -> k -> r
op Int -> Int
f = (([k], b) -> b) -> f ([k], b) -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([k], b) -> b
forall a b. (a, b) -> b
snd (f ([k], b) -> f b)
-> (f (a -> k, b) -> f ([k], b)) -> f (a -> k, b) -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> k -> r) -> (Int -> Int) -> f ([k], b) -> f ([k], b)
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> (Int -> Int) -> m ([k], e) -> m ([k], e)
sfilter k -> k -> r
op Int -> Int
f (f ([k], b) -> f ([k], b))
-> (f (a -> k, b) -> f ([k], b)) -> f (a -> k, b) -> f ([k], b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
((a -> k, b) -> ([k], b)) -> f (a -> k, b) -> f ([k], b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((a -> k) -> [k]) -> (a -> k, b) -> ([k], b)
forall t a b. (t -> a) -> (t, b) -> (a, b)
mapFst (((a -> k) -> [a] -> [k]) -> [a] -> (a -> k) -> [k]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> k) -> [a] -> [k]
forall a b. (a -> b) -> [a] -> [b]
map [a]
forall a. Arbitrary a => [a]
arbitraries))
instance (RealFloat a, Ord a) =>
Filtrable (Complex a) where
filt :: (Int -> Int) -> m (Complex a, e) -> m e
filt = (Complex a -> Complex a -> Ordering)
-> (Int -> Int) -> m (Complex a, e) -> m e
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> (Int -> Int) -> m (k, e) -> m e
filtNullary Complex a -> Complex a -> Ordering
forall a.
(RealFloat a, Ord a) =>
Complex a -> Complex a -> Ordering
compareCx
filtFun :: (Int -> Int) -> m (b -> Complex a, e) -> m e
filtFun = (Complex a -> Complex a -> Ordering)
-> (Int -> Int) -> m (b -> Complex a, e) -> m e
forall (f :: * -> *) r a k b.
(SStrategy f, Relation r, Arbitrary a) =>
(k -> k -> r) -> (Int -> Int) -> f (a -> k, b) -> f b
filtUnary Complex a -> Complex a -> Ordering
forall a.
(RealFloat a, Ord a) =>
Complex a -> Complex a -> Ordering
compareCx
unsafeFilt :: Maybe Int -> (Int -> Int) -> m (Complex a, e) -> m e
unsafeFilt Maybe Int
mto = (Complex a -> Complex a -> Maybe Ordering)
-> (Int -> Int) -> m (Complex a, e) -> m e
forall (m :: * -> *) r k e.
(SStrategy m, Relation r) =>
(k -> k -> r) -> (Int -> Int) -> m (k, e) -> m e
filtNullary (Maybe Int
-> (Complex a -> Complex a -> Ordering)
-> Complex a
-> Complex a
-> Maybe Ordering
forall a b c. Maybe Int -> (a -> b -> c) -> a -> b -> Maybe c
unsafeOpWithPTO Maybe Int
mto Complex a -> Complex a -> Ordering
forall a.
(RealFloat a, Ord a) =>
Complex a -> Complex a -> Ordering
compareCx)
unsafeFiltFun :: Maybe Int -> (Int -> Int) -> m (b -> Complex a, e) -> m e
unsafeFiltFun Maybe Int
mto = (Complex a -> Complex a -> Maybe Ordering)
-> (Int -> Int) -> m (b -> Complex a, e) -> m e
forall (f :: * -> *) r a k b.
(SStrategy f, Relation r, Arbitrary a) =>
(k -> k -> r) -> (Int -> Int) -> f (a -> k, b) -> f b
filtUnary (Maybe Int
-> (Complex a -> Complex a -> Ordering)
-> Complex a
-> Complex a
-> Maybe Ordering
forall a b c. Maybe Int -> (a -> b -> c) -> a -> b -> Maybe c
unsafeOpWithPTO Maybe Int
mto Complex a -> Complex a -> Ordering
forall a.
(RealFloat a, Ord a) =>
Complex a -> Complex a -> Ordering
compareCx)
compareCx :: (RealFloat a, Ord a) =>
Complex a -> Complex a -> Ordering
(a
a:+a
b) compareCx :: Complex a -> Complex a -> Ordering
`compareCx` (a
c:+a
d) = case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
c of
Ordering
EQ -> a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
b a
d
Ordering
o -> Ordering
o
ofilterMx :: Relation r =>
(k->k->r) -> Matrix (k,e) -> Matrix (k,e)
ofilterMx :: (k -> k -> r) -> Matrix (k, e) -> Matrix (k, e)
ofilterMx k -> k -> r
op (Mx Stream (Bag (k, e))
xss)
= let
(k
k,b
_) rel :: (k, b) -> (k, b) -> r
`rel` (k
l,b
_) = k
k k -> k -> r
`op` k
l
mapped :: Stream (Bag (k, e))
mapped = (Bag (k, e) -> Bag (k, e))
-> Stream (Bag (k, e)) -> Stream (Bag (k, e))
forall a b. (a -> b) -> [a] -> [b]
map (((k, e) -> (k, e) -> r) -> Bag (k, e) -> Bag (k, e)
forall rel k. Relation rel => (k -> k -> rel) -> [k] -> [k]
fromListBy (k, e) -> (k, e) -> r
forall b b. (k, b) -> (k, b) -> r
rel) Stream (Bag (k, e))
xss
cumulative :: Stream (Bag (k, e))
cumulative =
(Bag (k, e) -> Bag (k, e) -> Bag (k, e))
-> Bag (k, e) -> Stream (Bag (k, e)) -> Stream (Bag (k, e))
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (((k, e) -> (k, e) -> r) -> Bag (k, e) -> Bag (k, e) -> Bag (k, e)
forall rel k. Relation rel => (k -> k -> rel) -> [k] -> [k] -> [k]
appendRepresentativesBy (k, e) -> (k, e) -> r
forall b b. (k, b) -> (k, b) -> r
rel)
[] Stream (Bag (k, e))
mapped
in Stream (Bag (k, e)) -> Matrix (k, e)
forall a. Stream (Bag a) -> Matrix a
Mx (Stream (Bag (k, e)) -> Matrix (k, e))
-> Stream (Bag (k, e)) -> Matrix (k, e)
forall a b. (a -> b) -> a -> b
$ (Bag (k, e) -> Bag (k, e) -> Bag (k, e))
-> Stream (Bag (k, e))
-> Stream (Bag (k, e))
-> Stream (Bag (k, e))
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (((k, e) -> (k, e) -> r) -> Bag (k, e) -> Bag (k, e) -> Bag (k, e)
forall rel k. Relation rel => (k -> k -> rel) -> [k] -> [k] -> [k]
diffBy (k, e) -> (k, e) -> r
forall b b. (k, b) -> (k, b) -> r
rel) Stream (Bag (k, e))
mapped Stream (Bag (k, e))
cumulative
ofilterDB :: Relation rel =>
(k->k->rel) ->
DBound (k,e) -> DBound (k,e)
ofilterDB :: (k -> k -> rel) -> DBound (k, e) -> DBound (k, e)
ofilterDB k -> k -> rel
cmp (DB Int -> Bag ((k, e), Int)
f) = (Int -> Bag ((k, e), Int)) -> DBound (k, e)
forall a. (Int -> Bag (a, Int)) -> DBound a
DB ((Int -> Bag ((k, e), Int)) -> DBound (k, e))
-> (Int -> Bag ((k, e), Int)) -> DBound (k, e)
forall a b. (a -> b) -> a -> b
$
\Int
n -> ((k, e) -> (k, e) -> rel) -> Bag ((k, e), Int) -> Bag ((k, e), Int)
forall rel k.
Relation rel =>
(k -> k -> rel) -> [(k, Int)] -> [(k, Int)]
fromListByDB (\(k
k,e
_) (k
l,e
_) -> k -> k -> rel
cmp k
k k
l)
(Int -> Bag ((k, e), Int)
f Int
n)
cumulativeRepresentatives ::
Relation rel =>
[a->a->rel] -> Matrix a -> Matrix a
cumulativeRepresentatives :: [a -> a -> rel] -> Matrix a -> Matrix a
cumulativeRepresentatives [a -> a -> rel]
relations Matrix a
mx =
([a] -> a) -> Matrix [a] -> Matrix a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [a] -> a
forall a. [a] -> a
head ([a -> a -> rel] -> Matrix a -> Matrix [a]
forall rel k.
Relation rel =>
[k -> k -> rel] -> Matrix k -> Matrix [k]
cumulativeQuotients [a -> a -> rel]
relations Matrix a
mx)
representatives ::
Relation rel =>
[a->a->rel] -> Matrix a -> Matrix a
representatives :: [a -> a -> rel] -> Matrix a -> Matrix a
representatives [a -> a -> rel]
relations Matrix a
mx =
[a -> a -> rel] -> Matrix a -> Matrix a
forall r k. Relation r => [k -> k -> r] -> Matrix k -> Matrix k
unscanlByList [a -> a -> rel]
relations (Matrix a -> Matrix a) -> Matrix a -> Matrix a
forall a b. (a -> b) -> a -> b
$
[a -> a -> rel] -> Matrix a -> Matrix a
forall r k. Relation r => [k -> k -> r] -> Matrix k -> Matrix k
cumulativeRepresentatives [a -> a -> rel]
relations Matrix a
mx
unscanlByList :: Relation r =>
[k->k->r] -> Matrix k -> Matrix k
unscanlByList :: [k -> k -> r] -> Matrix k -> Matrix k
unscanlByList (k -> k -> r
_:[k -> k -> r]
rels) (Mx (yss :: Stream (Bag k)
yss@(Bag k
xs:Stream (Bag k)
xss))) =
Stream (Bag k) -> Matrix k
forall a. Stream (Bag a) -> Matrix a
Mx (Stream (Bag k) -> Matrix k) -> Stream (Bag k) -> Matrix k
forall a b. (a -> b) -> a -> b
$ Bag k
xs Bag k -> Stream (Bag k) -> Stream (Bag k)
forall a. a -> [a] -> [a]
: ((k -> k -> r) -> Bag k -> Bag k -> Bag k)
-> [k -> k -> r]
-> Stream (Bag k)
-> Stream (Bag k)
-> Stream (Bag k)
forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3 (k -> k -> r) -> Bag k -> Bag k -> Bag k
forall rel k. Relation rel => (k -> k -> rel) -> [k] -> [k] -> [k]
diffBy [k -> k -> r]
rels Stream (Bag k)
xss Stream (Bag k)
yss
sfilterMx :: Relation r =>
(k->k->r) ->
(Int->Int) ->
Matrix ([k],e) -> Matrix ([k],e)
sfilterMx :: (k -> k -> r) -> (Int -> Int) -> Matrix ([k], e) -> Matrix ([k], e)
sfilterMx k -> k -> r
rel Int -> Int
numRands = [([k], e) -> ([k], e) -> r] -> Matrix ([k], e) -> Matrix ([k], e)
forall r k. Relation r => [k -> k -> r] -> Matrix k -> Matrix k
representatives ((Int -> ([k], e) -> ([k], e) -> r)
-> [Int] -> [([k], e) -> ([k], e) -> r]
forall a b. (a -> b) -> [a] -> [b]
map ((k -> k -> r) -> Int -> ([k], e) -> ([k], e) -> r
forall r k e.
Relation r =>
(k -> k -> r) -> Int -> ([k], e) -> ([k], e) -> r
liftRelation k -> k -> r
rel (Int -> ([k], e) -> ([k], e) -> r)
-> (Int -> Int) -> Int -> ([k], e) -> ([k], e) -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int
numRands) [Int
0..])
liftRelation :: Relation r =>
(k->k->r) ->
Int -> ([k],e) -> ([k],e) -> r
liftRelation :: (k -> k -> r) -> Int -> ([k], e) -> ([k], e) -> r
liftRelation k -> k -> r
rel Int
len ([k]
xs,e
_) ([k]
ys,e
_) = (k -> k -> r) -> Int -> [k] -> [k] -> r
forall t p t t.
(Num t, Relation p, Eq t) =>
(t -> t -> p) -> t -> [t] -> [t] -> p
liftRel k -> k -> r
rel Int
len [k]
xs [k]
ys
liftRel :: (t -> t -> p) -> t -> [t] -> [t] -> p
liftRel t -> t -> p
_ t
0 [t]
_ [t]
_ = p
forall rel. Relation rel => rel
cEQ
liftRel t -> t -> p
_ t
_ [] [] = p
forall rel. Relation rel => rel
cEQ
liftRel t -> t -> p
rel t
len (t
x:[t]
xs) (t
y:[t]
ys) =
case t -> t -> p
rel t
x t
y of
p
c | p
c p -> p -> Bool
forall a. Eq a => a -> a -> Bool
== p
forall rel. Relation rel => rel
cEQ -> (t -> t -> p) -> t -> [t] -> [t] -> p
liftRel t -> t -> p
rel (t
lent -> t -> t
forall a. Num a => a -> a -> a
-t
1) [t]
xs [t]
ys
| Bool
otherwise -> p
c
sfilterDB :: Relation rel =>
(k->k->rel) ->
(Int->Int)->
DBound ([k],e) -> DBound ([k],e)
sfilterDB :: (k -> k -> rel)
-> (Int -> Int) -> DBound ([k], e) -> DBound ([k], e)
sfilterDB k -> k -> rel
rel Int -> Int
numRands (DB Int -> Bag (([k], e), Int)
f) = (Int -> Bag (([k], e), Int)) -> DBound ([k], e)
forall a. (Int -> Bag (a, Int)) -> DBound a
DB ((Int -> Bag (([k], e), Int)) -> DBound ([k], e))
-> (Int -> Bag (([k], e), Int)) -> DBound ([k], e)
forall a b. (a -> b) -> a -> b
$ \Int
n -> (([k], e) -> ([k], e) -> rel)
-> Bag (([k], e), Int) -> Bag (([k], e), Int)
forall rel k.
Relation rel =>
(k -> k -> rel) -> [(k, Int)] -> [(k, Int)]
fromListByDB ((k -> k -> rel) -> Int -> ([k], e) -> ([k], e) -> rel
forall r k e.
Relation r =>
(k -> k -> r) -> Int -> ([k], e) -> ([k], e) -> r
liftRelation k -> k -> rel
rel (Int -> Int
numRands Int
n)) (Int -> Bag (([k], e), Int)
f Int
n)
cumulativeQuotients :: [k -> k -> rel] -> Matrix k -> Matrix [k]
cumulativeQuotients [k -> k -> rel]
relations (Mx Stream [k]
xss)
= let Stream [k]
yss:[Stream [k]]
ysss = ([k] -> (k -> k -> rel) -> Stream [k])
-> Stream [k] -> [k -> k -> rel] -> [Stream [k]]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith [k] -> (k -> k -> rel) -> Stream [k]
forall rel k. Relation rel => [k] -> (k -> k -> rel) -> [[k]]
(/) Stream [k]
xss [k -> k -> rel]
relations
in [Stream [k]] -> Matrix [k]
forall a. Stream (Bag a) -> Matrix a
Mx ([Stream [k]] -> Matrix [k]) -> [Stream [k]] -> Matrix [k]
forall a b. (a -> b) -> a -> b
$ (Stream [k] -> (k -> k -> rel, Stream [k]) -> Stream [k])
-> Stream [k] -> [(k -> k -> rel, Stream [k])] -> [Stream [k]]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (\Stream [k]
rec (k -> k -> rel
r,Stream [k]
z) ->
(k -> k -> rel) -> Stream [k] -> Stream [k] -> Stream [k]
forall rel k.
Relation rel =>
(k -> k -> rel) -> [[k]] -> [[k]] -> [[k]]
appendQuotientsBy k -> k -> rel
r (Stream [k]
recStream [k] -> ([k] -> Stream [k]) -> Stream [k]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>=([k] -> (k -> k -> rel) -> Stream [k]
forall rel k. Relation rel => [k] -> (k -> k -> rel) -> [[k]]
/k -> k -> rel
r)) Stream [k]
z)
Stream [k]
yss ([k -> k -> rel] -> [Stream [k]] -> [(k -> k -> rel, Stream [k])]
forall a b. [a] -> [b] -> [(a, b)]
zip ([k -> k -> rel] -> [k -> k -> rel]
forall a. [a] -> [a]
tail [k -> k -> rel]
relations) [Stream [k]]
ysss)
ns :: [Integer]
ns = [Integer
6..]