{-# LANGUAGE CPP, BangPatterns, TypeFamilies, ScopedTypeVariables #-}
{-# LANGUAGE FlexibleContexts #-}
#ifdef DEFAULT_SIGNATURES
{-# LANGUAGE DefaultSignatures #-}
#endif
{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >=704
{-# LANGUAGE Safe #-}
#elif __GLASGOW_HASKELL__ >=702
{-# LANGUAGE Trustworthy #-}
#endif
module Data.Universe.Class
( Universe(..)
, Finite(..)
) where
import Data.Universe.Helpers
import Control.Applicative (Const (..))
import Control.Monad (liftM2, liftM3, liftM4, liftM5)
import Control.Monad.Trans.Identity (IdentityT (..))
import Control.Monad.Trans.Reader (ReaderT (..))
import Data.Functor.Compose (Compose (..))
import Data.Functor.Identity (Identity (..))
import Data.Functor.Product (Product (..))
import Data.Functor.Sum (Sum (..))
import Data.Int (Int, Int8, Int16, Int32, Int64)
import Data.List (genericLength)
import Data.List.NonEmpty (NonEmpty (..))
import Data.Map ((!), fromList)
import Data.Proxy (Proxy (..))
import Data.Ratio (Ratio, numerator, denominator, (%))
import Data.Tagged (Tagged (..), retag)
import Data.Void (Void)
import Data.Word (Word, Word8, Word16, Word32, Word64)
import GHC.Real (Ratio (..))
import Numeric.Natural (Natural)
import qualified Data.Monoid as Mon
import qualified Data.Semigroup as Semi
import qualified Data.Set as Set
import qualified Data.Map as Map
#if MIN_VERSION_base(4,18,0)
import Data.Tuple (Solo (MkSolo))
#elif MIN_VERSION_base(4,16,0)
import Data.Tuple (Solo (Solo))
#define MkSolo Solo
#elif MIN_VERSION_base(4,15,0)
import GHC.Tuple (Solo (Solo))
#define MkSolo Solo
#else
#if MIN_VERSION_OneTuple(0,4,0)
import Data.Tuple.Solo (Solo (MkSolo))
#else
import Data.Tuple.Solo (Solo (Solo))
#define MkSolo Solo
#endif
#endif
class Universe a where
universe :: [a]
#ifdef DEFAULT_SIGNATURES
default universe :: (Enum a, Bounded a) => [a]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
#endif
class Universe a => Finite a where
universeF :: [a]
universeF = forall a. Universe a => [a]
universe
cardinality :: Tagged a Natural
cardinality = forall {k} (s :: k) b. b -> Tagged s b
Tagged (forall i a. Num i => [a] -> i
genericLength (forall a. Finite a => [a]
universeF :: [a]))
instance Universe () where universe :: [()]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Bool where universe :: [Bool]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Char where universe :: [Char]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Ordering where universe :: [Ordering]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Integer where universe :: [Integer]
universe = [Integer
0, -Integer
1..] forall a. [a] -> [a] -> [a]
+++ [Integer
1..]
instance Universe Natural where universe :: [Natural]
universe = [Natural
0..]
instance Universe Int where universe :: [Int]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Int8 where universe :: [Int8]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Int16 where universe :: [Int16]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Int32 where universe :: [Int32]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Int64 where universe :: [Int64]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Word where universe :: [Word]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Word8 where universe :: [Word8]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Word16 where universe :: [Word16]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Word32 where universe :: [Word32]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance Universe Word64 where universe :: [Word64]
universe = forall a. (Bounded a, Enum a) => [a]
universeDef
instance (Universe a, Universe b) => Universe (Either a b) where universe :: [Either a b]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a b. a -> Either a b
Left forall a. Universe a => [a]
universe forall a. [a] -> [a] -> [a]
+++ forall a b. (a -> b) -> [a] -> [b]
map forall a b. b -> Either a b
Right forall a. Universe a => [a]
universe
instance Universe a => Universe (Maybe a ) where universe :: [Maybe a]
universe = forall a. Maybe a
Nothing forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Maybe a
Just forall a. Universe a => [a]
universe
instance (Universe a, Universe b) => Universe (a, b) where universe :: [(a, b)]
universe = forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe
instance (Universe a, Universe b, Universe c) => Universe (a, b, c) where universe :: [(a, b, c)]
universe = [(a
a,b
b,c
c) | ((a
a,b
b),c
c) <- forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe]
instance (Universe a, Universe b, Universe c, Universe d) => Universe (a, b, c, d) where universe :: [(a, b, c, d)]
universe = [(a
a,b
b,c
c,d
d) | (((a
a,b
b),c
c),d
d) <- forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe]
instance (Universe a, Universe b, Universe c, Universe d, Universe e) => Universe (a, b, c, d, e) where universe :: [(a, b, c, d, e)]
universe = [(a
a,b
b,c
c,d
d,e
e) | ((((a
a,b
b),c
c),d
d),e
e) <- forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe]
instance Universe a => Universe [a] where
universe :: [[a]]
universe = forall a. [[a]] -> [a]
diagonal forall a b. (a -> b) -> a -> b
$ [[]] forall a. a -> [a] -> [a]
: [[a
hforall a. a -> [a] -> [a]
:[a]
t | [a]
t <- forall a. Universe a => [a]
universe] | a
h <- forall a. Universe a => [a]
universe]
instance Universe a => Universe (NonEmpty a) where
universe :: [NonEmpty a]
universe = forall a. [[a]] -> [a]
diagonal [[a
h forall a. a -> [a] -> NonEmpty a
:| [a]
t | [a]
t <- forall a. Universe a => [a]
universe] | a
h <- forall a. Universe a => [a]
universe]
instance Universe Mon.All where universe :: [All]
universe = forall a b. (a -> b) -> [a] -> [b]
map Bool -> All
Mon.All forall a. Universe a => [a]
universe
instance Universe Mon.Any where universe :: [Any]
universe = forall a b. (a -> b) -> [a] -> [b]
map Bool -> Any
Mon.Any forall a. Universe a => [a]
universe
instance Universe a => Universe (Mon.Sum a) where universe :: [Sum a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Sum a
Mon.Sum forall a. Universe a => [a]
universe
instance Universe a => Universe (Mon.Product a) where universe :: [Product a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Product a
Mon.Product forall a. Universe a => [a]
universe
instance Universe a => Universe (Mon.Dual a) where universe :: [Dual a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Dual a
Mon.Dual forall a. Universe a => [a]
universe
instance Universe a => Universe (Mon.First a) where universe :: [First a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. Maybe a -> First a
Mon.First forall a. Universe a => [a]
universe
instance Universe a => Universe (Mon.Last a) where universe :: [Last a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. Maybe a -> Last a
Mon.Last forall a. Universe a => [a]
universe
instance Universe a => Universe (Semi.Max a) where universe :: [Max a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Max a
Semi.Max forall a. Universe a => [a]
universe
instance Universe a => Universe (Semi.Min a) where universe :: [Min a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Min a
Semi.Min forall a. Universe a => [a]
universe
instance Universe a => Universe (Semi.First a) where universe :: [First a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> First a
Semi.First forall a. Universe a => [a]
universe
instance Universe a => Universe (Semi.Last a) where universe :: [Last a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Last a
Semi.Last forall a. Universe a => [a]
universe
infixr 5 :<
data Stream a = !a :< Stream a
leftSideStream :: Integral a => Stream (Ratio a)
leftSideStream :: forall a. Integral a => Stream (Ratio a)
leftSideStream = a
1 forall a. a -> a -> Ratio a
:% a
2 forall a. a -> Stream a -> Stream a
:< forall {a}. Num a => Stream (Ratio a) -> Stream (Ratio a)
go forall a. Integral a => Stream (Ratio a)
leftSideStream
where
go :: Stream (Ratio a) -> Stream (Ratio a)
go (Ratio a
x :< Stream (Ratio a)
xs) = Ratio a
lChild forall a. a -> Stream a -> Stream a
:< Ratio a
rChild forall a. a -> Stream a -> Stream a
:< Stream (Ratio a) -> Stream (Ratio a)
go Stream (Ratio a)
xs
where
nd :: a
nd = forall a. Ratio a -> a
numerator Ratio a
x forall a. Num a => a -> a -> a
+ forall a. Ratio a -> a
denominator Ratio a
x
!lChild :: Ratio a
lChild = forall a. Ratio a -> a
numerator Ratio a
x forall a. a -> a -> Ratio a
:% a
nd
!rChild :: Ratio a
rChild = a
nd forall a. a -> a -> Ratio a
:% forall a. Ratio a -> a
denominator Ratio a
x
instance RationalUniverse a => Universe (Ratio a) where
universe :: [Ratio a]
universe = forall a. RationalUniverse a => [Ratio a]
rationalUniverse
class RationalUniverse a where
rationalUniverse :: [Ratio a]
instance RationalUniverse Integer where
rationalUniverse :: [Ratio Integer]
rationalUniverse = Ratio Integer
0 forall a. a -> [a] -> [a]
: Ratio Integer
1 forall a. a -> [a] -> [a]
: (-Ratio Integer
1) forall a. a -> [a] -> [a]
: forall {a}. Integral a => Stream (Ratio a) -> [Ratio a]
go forall a. Integral a => Stream (Ratio a)
leftSideStream
where
go :: Stream (Ratio a) -> [Ratio a]
go (x :: Ratio a
x@(a
xn :% a
xd) :< Stream (Ratio a)
xs) =
let !nx :: Ratio a
nx = -Ratio a
x
!rx :: Ratio a
rx = a
xd forall a. a -> a -> Ratio a
:% a
xn
!nrx :: Ratio a
nrx = -Ratio a
rx
in Ratio a
x forall a. a -> [a] -> [a]
: Ratio a
rx forall a. a -> [a] -> [a]
: Ratio a
nx forall a. a -> [a] -> [a]
: Ratio a
nrx forall a. a -> [a] -> [a]
: Stream (Ratio a) -> [Ratio a]
go Stream (Ratio a)
xs
instance RationalUniverse Natural where
rationalUniverse :: [Ratio Natural]
rationalUniverse = Ratio Natural
0 forall a. a -> [a] -> [a]
: Ratio Natural
1 forall a. a -> [a] -> [a]
: forall {a}. Stream (Ratio a) -> [Ratio a]
go forall a. Integral a => Stream (Ratio a)
leftSideStream
where
go :: Stream (Ratio a) -> [Ratio a]
go (x :: Ratio a
x@(a
xn :% a
xd) :< Stream (Ratio a)
xs) =
let !rx :: Ratio a
rx = a
xd forall a. a -> a -> Ratio a
:% a
xn
in Ratio a
x forall a. a -> [a] -> [a]
: Ratio a
rx forall a. a -> [a] -> [a]
: Stream (Ratio a) -> [Ratio a]
go Stream (Ratio a)
xs
instance (Finite a, Ord a, Universe b) => Universe (a -> b) where
universe :: [a -> b]
universe = forall a b. (a -> b) -> [a] -> [b]
map [b] -> a -> b
tableToFunction [[b]]
tables where
tables :: [[b]]
tables = forall a. [[a]] -> [[a]]
choices [forall a. Universe a => [a]
universe | a
_ <- [a]
monoUniverse]
tableToFunction :: [b] -> a -> b
tableToFunction = forall k a. Ord k => Map k a -> k -> a
(!) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => [(k, a)] -> Map k a
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. [a] -> [b] -> [(a, b)]
zip [a]
monoUniverse
monoUniverse :: [a]
monoUniverse = forall a. Finite a => [a]
universeF
instance Finite () where cardinality :: Tagged () Natural
cardinality = Tagged () Natural
1
instance Finite Bool where cardinality :: Tagged Bool Natural
cardinality = Tagged Bool Natural
2
instance Finite Char where cardinality :: Tagged Char Natural
cardinality = Tagged Char Natural
1114112
instance Finite Ordering where cardinality :: Tagged Ordering Natural
cardinality = Tagged Ordering Natural
3
instance Finite Int where cardinality :: Tagged Int Natural
cardinality = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Bounded a => a
maxBound :: Int) forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Bounded a => a
minBound :: Int) forall a. Num a => a -> a -> a
+ Tagged Int Natural
1
instance Finite Int8 where cardinality :: Tagged Int8 Natural
cardinality = Tagged Int8 Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
8
instance Finite Int16 where cardinality :: Tagged Int16 Natural
cardinality = Tagged Int16 Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
16
instance Finite Int32 where cardinality :: Tagged Int32 Natural
cardinality = Tagged Int32 Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
32
instance Finite Int64 where cardinality :: Tagged Int64 Natural
cardinality = Tagged Int64 Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
64
instance Finite Word where cardinality :: Tagged Word Natural
cardinality = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Bounded a => a
maxBound :: Word) forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Bounded a => a
minBound :: Word) forall a. Num a => a -> a -> a
+ Tagged Word Natural
1
instance Finite Word8 where cardinality :: Tagged Word8 Natural
cardinality = forall {k} (s :: k) b. b -> Tagged s b
Tagged forall a b. (a -> b) -> a -> b
$ Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
8
instance Finite Word16 where cardinality :: Tagged Word16 Natural
cardinality = forall {k} (s :: k) b. b -> Tagged s b
Tagged forall a b. (a -> b) -> a -> b
$ Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
16
instance Finite Word32 where cardinality :: Tagged Word32 Natural
cardinality = forall {k} (s :: k) b. b -> Tagged s b
Tagged forall a b. (a -> b) -> a -> b
$ Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
32
instance Finite Word64 where cardinality :: Tagged Word64 Natural
cardinality = forall {k} (s :: k) b. b -> Tagged s b
Tagged forall a b. (a -> b) -> a -> b
$ Natural
2forall a b. (Num a, Integral b) => a -> b -> a
^Integer
64
instance Finite a => Finite (Maybe a ) where
cardinality :: Tagged (Maybe a) Natural
cardinality = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Enum a => a -> a
succ (forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
instance (Finite a, Finite b) => Finite (Either a b) where
universeF :: [Either a b]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a b. a -> Either a b
Left forall a. Universe a => [a]
universe forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
map forall a b. b -> Either a b
Right forall a. Universe a => [a]
universe
cardinality :: Tagged (Either a b) Natural
cardinality = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 (\Natural
a Natural
b -> Natural
a forall a. Num a => a -> a -> a
+ Natural
b)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged b Natural))
instance (Finite a, Finite b) => Finite (a, b) where
universeF :: [(a, b)]
universeF = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 (,) forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF
cardinality :: Tagged (a, b) Natural
cardinality = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 (\Natural
a Natural
b -> Natural
a forall a. Num a => a -> a -> a
* Natural
b)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged b Natural))
instance (Finite a, Finite b, Finite c) => Finite (a, b, c) where
universeF :: [(a, b, c)]
universeF = forall (m :: * -> *) a1 a2 a3 r.
Monad m =>
(a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
liftM3 (,,) forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF
cardinality :: Tagged (a, b, c) Natural
cardinality = forall (m :: * -> *) a1 a2 a3 r.
Monad m =>
(a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
liftM3 (\Natural
a Natural
b Natural
c -> Natural
a forall a. Num a => a -> a -> a
* Natural
b forall a. Num a => a -> a -> a
* Natural
c)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged b Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged c Natural))
instance (Finite a, Finite b, Finite c, Finite d) => Finite (a, b, c, d) where
universeF :: [(a, b, c, d)]
universeF = forall (m :: * -> *) a1 a2 a3 a4 r.
Monad m =>
(a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
liftM4 (,,,) forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF
cardinality :: Tagged (a, b, c, d) Natural
cardinality = forall (m :: * -> *) a1 a2 a3 a4 r.
Monad m =>
(a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
liftM4 (\Natural
a Natural
b Natural
c Natural
d -> Natural
a forall a. Num a => a -> a -> a
* Natural
b forall a. Num a => a -> a -> a
* Natural
c forall a. Num a => a -> a -> a
* Natural
d)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged b Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged c Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged d Natural))
instance (Finite a, Finite b, Finite c, Finite d, Finite e) => Finite (a, b, c, d, e) where
universeF :: [(a, b, c, d, e)]
universeF = forall (m :: * -> *) a1 a2 a3 a4 a5 r.
Monad m =>
(a1 -> a2 -> a3 -> a4 -> a5 -> r)
-> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
liftM5 (,,,,) forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF
cardinality :: Tagged (a, b, c, d, e) Natural
cardinality = forall (m :: * -> *) a1 a2 a3 a4 a5 r.
Monad m =>
(a1 -> a2 -> a3 -> a4 -> a5 -> r)
-> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
liftM5 (\Natural
a Natural
b Natural
c Natural
d Natural
e -> Natural
a forall a. Num a => a -> a -> a
* Natural
b forall a. Num a => a -> a -> a
* Natural
c forall a. Num a => a -> a -> a
* Natural
d forall a. Num a => a -> a -> a
* Natural
e)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged b Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged c Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged d Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged e Natural))
instance Finite Mon.All where universeF :: [All]
universeF = forall a b. (a -> b) -> [a] -> [b]
map Bool -> All
Mon.All forall a. Finite a => [a]
universeF; cardinality :: Tagged All Natural
cardinality = Tagged All Natural
2
instance Finite Mon.Any where universeF :: [Any]
universeF = forall a b. (a -> b) -> [a] -> [b]
map Bool -> Any
Mon.Any forall a. Finite a => [a]
universeF; cardinality :: Tagged Any Natural
cardinality = Tagged Any Natural
2
instance Finite a => Finite (Mon.Sum a) where universeF :: [Sum a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Sum a
Mon.Sum forall a. Finite a => [a]
universeF; cardinality :: Tagged (Sum a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> Sum a
Mon.Sum forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Mon.Product a) where universeF :: [Product a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Product a
Mon.Product forall a. Finite a => [a]
universeF; cardinality :: Tagged (Product a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> Product a
Mon.Product forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Mon.Dual a) where universeF :: [Dual a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Dual a
Mon.Dual forall a. Finite a => [a]
universeF; cardinality :: Tagged (Dual a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> Dual a
Mon.Dual forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Mon.First a) where universeF :: [First a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. Maybe a -> First a
Mon.First forall a. Finite a => [a]
universeF; cardinality :: Tagged (First a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. Maybe a -> First a
Mon.First forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Mon.Last a) where universeF :: [Last a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. Maybe a -> Last a
Mon.Last forall a. Finite a => [a]
universeF; cardinality :: Tagged (Last a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. Maybe a -> Last a
Mon.Last forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Semi.Max a) where universeF :: [Max a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Max a
Semi.Max forall a. Finite a => [a]
universeF; cardinality :: Tagged (Max a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> Max a
Semi.Max forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Semi.Min a) where universeF :: [Min a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Min a
Semi.Min forall a. Finite a => [a]
universeF; cardinality :: Tagged (Min a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> Min a
Semi.Min forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Semi.First a) where universeF :: [First a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> First a
Semi.First forall a. Finite a => [a]
universeF; cardinality :: Tagged (First a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> First a
Semi.First forall a. Finite a => Tagged a Natural
cardinality
instance Finite a => Finite (Semi.Last a) where universeF :: [Last a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Last a
Semi.Last forall a. Finite a => [a]
universeF; cardinality :: Tagged (Last a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> Last a
Semi.Last forall a. Finite a => Tagged a Natural
cardinality
instance (Ord a, Finite a, Finite b) => Finite (a -> b) where
universeF :: [a -> b]
universeF = forall a b. (a -> b) -> [a] -> [b]
map [b] -> a -> b
tableToFunction [[b]]
tables where
tables :: [[b]]
tables = forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence [forall a. Finite a => [a]
universeF | a
_ <- [a]
monoUniverse]
tableToFunction :: [b] -> a -> b
tableToFunction = forall k a. Ord k => Map k a -> k -> a
(!) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => [(k, a)] -> Map k a
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. [a] -> [b] -> [(a, b)]
zip [a]
monoUniverse
monoUniverse :: [a]
monoUniverse = forall a. Finite a => [a]
universeF
cardinality :: Tagged (a -> b) Natural
cardinality = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 forall a b. (Num a, Integral b) => a -> b -> a
(^)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged b Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
instance Universe Void where universe :: [Void]
universe = []
instance Finite Void where cardinality :: Tagged Void Natural
cardinality = Tagged Void Natural
0
instance Universe (Proxy a) where universe :: [Proxy a]
universe = [forall {k} (t :: k). Proxy t
Proxy]
instance Finite (Proxy a) where cardinality :: Tagged (Proxy a) Natural
cardinality = Tagged (Proxy a) Natural
1
instance Universe a => Universe (Tagged b a) where universe :: [Tagged b a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall {k} (s :: k) b. b -> Tagged s b
Tagged forall a. Universe a => [a]
universe
instance Finite a => Finite (Tagged b a) where cardinality :: Tagged (Tagged b a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall {k} (s :: k) b. b -> Tagged s b
Tagged forall a. Finite a => Tagged a Natural
cardinality
instance (Ord a, Universe a) => Universe (Set.Set a) where
universe :: [Set a]
universe = forall a. Set a
Set.empty forall a. a -> [a] -> [a]
: forall {a}. Ord a => [a] -> [Set a]
go forall a. Universe a => [a]
universe
where
go :: [a] -> [Set a]
go [] = []
go (a
x:[a]
xs) = forall a. a -> Set a
Set.singleton a
x forall a. a -> [a] -> [a]
: [Set a] -> [Set a]
inter ([a] -> [Set a]
go [a]
xs)
where
inter :: [Set a] -> [Set a]
inter [] = []
inter (Set a
y:[Set a]
ys) = Set a
y forall a. a -> [a] -> [a]
: forall a. Ord a => a -> Set a -> Set a
Set.insert a
x Set a
y forall a. a -> [a] -> [a]
: [Set a] -> [Set a]
inter [Set a]
ys
instance (Ord a, Finite a) => Finite (Set.Set a) where
cardinality :: Tagged (Set a) Natural
cardinality = forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Natural
2 forall a b. (Num a, Integral b) => a -> b -> a
^) (forall a. Finite a => Tagged a Natural
cardinality :: Tagged a Natural))
instance (Ord k, Finite k, Universe v) => Universe (Map.Map k v) where
universe :: [Map k v]
universe = forall a b. (a -> b) -> [a] -> [b]
map [Maybe v] -> Map k v
tableToFunction [[Maybe v]]
tables where
tables :: [[Maybe v]]
tables = forall a. [[a]] -> [[a]]
choices [forall a. Universe a => [a]
universe | k
_ <- [k]
monoUniverse]
tableToFunction :: [Maybe v] -> Map k v
tableToFunction = forall {k} {a}. Ord k => [(k, Maybe a)] -> Map k a
fromList' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. [a] -> [b] -> [(a, b)]
zip [k]
monoUniverse
monoUniverse :: [k]
monoUniverse = forall a. Finite a => [a]
universeF
fromList' :: [(k, Maybe a)] -> Map k a
fromList' [(k, Maybe a)]
xs = forall k a. Ord k => [(k, a)] -> Map k a
fromList [ (k
k,a
v) | (k
k, Just a
v) <- [(k, Maybe a)]
xs ]
instance (Ord k, Finite k, Finite v) => Finite (Map.Map k v) where
universeF :: [Map k v]
universeF = forall a b. (a -> b) -> [a] -> [b]
map [Maybe v] -> Map k v
tableToFunction [[Maybe v]]
tables where
tables :: [[Maybe v]]
tables = forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence [forall a. Finite a => [a]
universeF | k
_ <- [k]
monoUniverse]
tableToFunction :: [Maybe v] -> Map k v
tableToFunction = forall {k} {a}. Ord k => [(k, Maybe a)] -> Map k a
fromList' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. [a] -> [b] -> [(a, b)]
zip [k]
monoUniverse
monoUniverse :: [k]
monoUniverse = forall a. Finite a => [a]
universeF
fromList' :: [(k, Maybe a)] -> Map k a
fromList' [(k, Maybe a)]
xs = forall k a. Ord k => [(k, a)] -> Map k a
fromList [ (k
k,a
v) | (k
k, Just a
v) <- [(k, Maybe a)]
xs ]
cardinality :: Tagged (Map k v) Natural
cardinality = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 (\Natural
b Natural
a -> (Natural
1 forall a. Num a => a -> a -> a
+ Natural
b) forall a b. (Num a, Integral b) => a -> b -> a
^ Natural
a)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged v Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged k Natural))
instance Universe a => Universe (Const a b) where universe :: [Const a b]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall {k} a (b :: k). a -> Const a b
Const forall a. Universe a => [a]
universe
instance Finite a => Finite (Const a b) where universeF :: [Const a b]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall {k} a (b :: k). a -> Const a b
Const forall a. Finite a => [a]
universeF; cardinality :: Tagged (Const a b) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall {k} a (b :: k). a -> Const a b
Const forall a. Finite a => Tagged a Natural
cardinality
instance Universe a => Universe (Identity a) where universe :: [Identity a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Identity a
Identity forall a. Universe a => [a]
universe
instance Universe (f a) => Universe (IdentityT f a) where universe :: [IdentityT f a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall {k} (f :: k -> *) (a :: k). f a -> IdentityT f a
IdentityT forall a. Universe a => [a]
universe
instance (Finite e, Ord e, Universe (m a)) => Universe (ReaderT e m a) where universe :: [ReaderT e m a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall r (m :: * -> *) a. (r -> m a) -> ReaderT r m a
ReaderT forall a. Universe a => [a]
universe
instance Universe (f (g a)) => Universe (Compose f g a) where universe :: [Compose f g a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose forall a. Universe a => [a]
universe
instance (Universe (f a), Universe (g a)) => Universe (Product f g a) where universe :: [Product f g a]
universe = [forall {k} (f :: k -> *) (g :: k -> *) (a :: k).
f a -> g a -> Product f g a
Pair f a
f g a
g | (f a
f, g a
g) <- forall a. Universe a => [a]
universe forall a b. [a] -> [b] -> [(a, b)]
+*+ forall a. Universe a => [a]
universe]
instance (Universe (f a), Universe (g a)) => Universe (Sum f g a) where universe :: [Sum f g a]
universe = forall a b. (a -> b) -> [a] -> [b]
map forall {k} (f :: k -> *) (g :: k -> *) (a :: k). f a -> Sum f g a
InL forall a. Universe a => [a]
universe forall a. [a] -> [a] -> [a]
+++ forall a b. (a -> b) -> [a] -> [b]
map forall {k} (f :: k -> *) (g :: k -> *) (a :: k). g a -> Sum f g a
InR forall a. Universe a => [a]
universe
instance Finite a => Finite (Identity a) where universeF :: [Identity a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall a. a -> Identity a
Identity forall a. Finite a => [a]
universeF; cardinality :: Tagged (Identity a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall a. a -> Identity a
Identity forall a. Finite a => Tagged a Natural
cardinality
instance Finite (f a) => Finite (IdentityT f a) where universeF :: [IdentityT f a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall {k} (f :: k -> *) (a :: k). f a -> IdentityT f a
IdentityT forall a. Finite a => [a]
universeF; cardinality :: Tagged (IdentityT f a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall {k} (f :: k -> *) (a :: k). f a -> IdentityT f a
IdentityT forall a. Finite a => Tagged a Natural
cardinality
instance (Finite e, Ord e, Finite (m a)) => Finite (ReaderT e m a) where universeF :: [ReaderT e m a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall r (m :: * -> *) a. (r -> m a) -> ReaderT r m a
ReaderT forall a. Finite a => [a]
universeF; cardinality :: Tagged (ReaderT e m a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall r (m :: * -> *) a. (r -> m a) -> ReaderT r m a
ReaderT forall a. Finite a => Tagged a Natural
cardinality
instance Finite (f (g a)) => Finite (Compose f g a) where universeF :: [Compose f g a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose forall a. Finite a => [a]
universeF; cardinality :: Tagged (Compose f g a) Natural
cardinality = forall a b x. (a -> b) -> Tagged a x -> Tagged b x
retagWith forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose forall a. Finite a => Tagged a Natural
cardinality
instance (Finite (f a), Finite (g a)) => Finite (Product f g a) where
universeF :: [Product f g a]
universeF = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 forall {k} (f :: k -> *) (g :: k -> *) (a :: k).
f a -> g a -> Product f g a
Pair forall a. Finite a => [a]
universeF forall a. Finite a => [a]
universeF
cardinality :: Tagged (Product f g a) Natural
cardinality = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 forall a. Num a => a -> a -> a
(*)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged (f a) Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged (g a) Natural))
instance (Finite (f a), Finite (g a)) => Finite (Sum f g a) where
universeF :: [Sum f g a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map forall {k} (f :: k -> *) (g :: k -> *) (a :: k). f a -> Sum f g a
InL forall a. Universe a => [a]
universe forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
map forall {k} (f :: k -> *) (g :: k -> *) (a :: k). g a -> Sum f g a
InR forall a. Universe a => [a]
universe
cardinality :: Tagged (Sum f g a) Natural
cardinality = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 forall a. Num a => a -> a -> a
(+)
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged (f a) Natural))
(forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b
retag (forall a. Finite a => Tagged a Natural
cardinality :: Tagged (g a) Natural))
instance Universe a => Universe (Solo a) where universe :: [Solo a]
universe = forall a b. (a -> b) -> [a] -> [b]
map MkSolo universe
instance Finite a => Finite (Solo a) where universeF :: [Solo a]
universeF = forall a b. (a -> b) -> [a] -> [b]
map MkSolo universeF; cardinality = retagWith MkSolo cardinality