-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Finite or countably infinite sequences of values.
--
-- Finite or countably infinite sequences of values, supporting efficient
-- indexing and random sampling.
@package simple-enumeration
@version 0.2
-- | An enumeration is a finite or countably infinite sequence of
-- values, that is, enumerations are isomorphic to lists. However,
-- enumerations are represented a functions from index to value, so they
-- support efficient indexing and can be constructed for very large
-- finite sets. A few examples are shown below.
--
--
-- >>> enumerate . takeE 15 $ listOf nat
-- [[],[0],[0,0],[1],[0,0,0],[1,0],[2],[0,1],[1,0,0],[2,0],[3],[0,0,0,0],[1,1],[2,0,0],[3,0]]
--
-- >>> select (listOf nat) 986235087203970702008108646
-- [11987363624969,1854392,1613,15,0,2,0]
--
--
--
-- data Tree = L | B Tree Tree deriving Show
--
-- treesUpTo :: Int -> Enumeration Tree
-- treesUpTo 0 = singleton L
-- treesUpTo n = singleton L <|> B <$> t' <*> t'
-- where t' = treesUpTo (n-1)
--
-- trees :: Enumeration Tree
-- trees = infinite $ singleton L <|> B <$> trees <*> trees
--
--
--
-- >>> card (treesUpTo 1)
-- Finite 2
--
-- >>> card (treesUpTo 10)
-- Finite 14378219780015246281818710879551167697596193767663736497089725524386087657390556152293078723153293423353330879856663164406809615688082297859526620035327291442156498380795040822304677
--
-- >>> select (treesUpTo 5) 12345
-- B (B L (B (B (B L L) L) (B L L))) (B (B (B L L) L) (B L L))
--
--
--
-- >>> card trees
-- Infinite
--
-- >>> select trees 12345
-- B (B (B (B L (B L L)) L) (B L (B (B L L) L))) (B (B L (B L L)) (B (B L L) (B L (B L L))))
--
--
-- For invertible enumerations, i.e. bijections between
-- some set of values and natural numbers (or finite prefix thereof), see
-- Data.Enumeration.Invertible.
module Data.Enumeration
-- | An enumeration of a finite or countably infinite set of values. An
-- enumeration is represented as a function from the natural numbers (for
-- infinite enumerations) or a finite prefix of the natural numbers (for
-- finite ones) to values. Enumerations can thus easily be constructed
-- for very large sets, and support efficient indexing and random
-- sampling.
--
-- Enumeration is an instance of the following type classes:
--
--
-- - Functor (you can map a function over every element of an
-- enumeration)
-- - Applicative (representing Cartesian product of
-- enumerations; see (><))
-- - Alternative (representing disjoint union of enumerations;
-- see (<+>))
--
--
-- Enumeration is not a Monad, since there is no way
-- to implement join that works for any combination of finite and
-- infinite enumerations (but see interleave).
data Enumeration a
-- | Create an enumeration primitively out of a cardinality and an index
-- function.
mkEnumeration :: Cardinality -> (Index -> a) -> Enumeration a
-- | The cardinality of a countable set: either a specific finite natural
-- number, or countably infinite.
data Cardinality
Finite :: !Integer -> Cardinality
Infinite :: Cardinality
-- | Get the cardinality of an enumeration.
card :: Enumeration a -> Cardinality
-- | An index into an enumeration.
type Index = Integer
-- | Select the value at a particular index of an enumeration.
-- Precondition: the index must be strictly less than the cardinality.
-- For infinite sets, every possible value must occur at some finite
-- index.
select :: Enumeration a -> Index -> a
-- | Test whether an enumeration is finite.
--
--
-- >>> isFinite (finiteList [1,2,3])
-- True
--
--
--
-- >>> isFinite nat
-- False
--
isFinite :: Enumeration a -> Bool
-- | List the elements of an enumeration in order. Inverse of
-- finiteList.
enumerate :: Enumeration a -> [a]
-- | The unit enumeration, with a single value of ().
--
--
-- >>> card unit
-- Finite 1
--
--
--
-- >>> enumerate unit
-- [()]
--
unit :: Enumeration ()
-- | An enumeration of a single given element.
--
--
-- >>> card (singleton 17)
-- Finite 1
--
--
--
-- >>> enumerate (singleton 17)
-- [17]
--
singleton :: a -> Enumeration a
-- | A constant infinite enumeration.
--
--
-- >>> card (always 17)
-- Infinite
--
--
--
-- >>> enumerate . takeE 10 $ always 17
-- [17,17,17,17,17,17,17,17,17,17]
--
always :: a -> Enumeration a
-- | A finite prefix of the natural numbers.
--
--
-- >>> card (finite 5)
-- Finite 5
--
-- >>> card (finite 1234567890987654321)
-- Finite 1234567890987654321
--
--
--
-- >>> enumerate (finite 5)
-- [0,1,2,3,4]
--
-- >>> enumerate (finite 0)
-- []
--
finite :: Integer -> Enumeration Integer
-- | Construct an enumeration from the elements of a finite list. To
-- turn an enumeration back into a list, use enumerate.
--
--
-- >>> enumerate (finiteList [2,3,8,1])
-- [2,3,8,1]
--
-- >>> select (finiteList [2,3,8,1]) 2
-- 8
--
--
-- finiteList does not work on infinite lists: inspecting the
-- cardinality of the resulting enumeration (something many of the
-- enumeration combinators need to do) will hang trying to compute the
-- length of the infinite list. To make an infinite enumeration, use
-- something like f <$> nat where f
-- is a function to compute the value at any given index.
--
-- finiteList uses (!!) internally, so you probably want to
-- avoid using it on long lists. It would be possible to make a version
-- with better indexing performance by allocating a vector internally,
-- but I am too lazy to do it. If you have a good use case let me know
-- (better yet, submit a pull request).
finiteList :: [a] -> Enumeration a
-- | Enumerate all the values of a bounded Enum instance.
--
--
-- >>> enumerate (boundedEnum @Bool)
-- [False,True]
--
--
--
-- >>> select (boundedEnum @Char) 97
-- 'a'
--
--
--
-- >>> card (boundedEnum @Int)
-- Finite 18446744073709551616
--
-- >>> select (boundedEnum @Int) 0
-- -9223372036854775808
--
boundedEnum :: forall a. (Enum a, Bounded a) => Enumeration a
-- | The natural numbers, 0, 1, 2, ....
--
--
-- >>> enumerate . takeE 10 $ nat
-- [0,1,2,3,4,5,6,7,8,9]
--
nat :: Enumeration Integer
-- | All integers in the order 0, 1, -1, 2, -2, 3, -3, ....
int :: Enumeration Integer
-- | The positive rational numbers, enumerated according to the
-- Calkin-Wilf sequence.
--
--
-- >>> enumerate . takeE 10 $ cw
-- [1 % 1,1 % 2,2 % 1,1 % 3,3 % 2,2 % 3,3 % 1,1 % 4,4 % 3,3 % 5]
--
cw :: Enumeration Rational
-- | An enumeration of all rational numbers: 0 first, then each rational in
-- the Calkin-Wilf sequence followed by its negative.
--
--
-- >>> enumerate . takeE 10 $ rat
-- [0 % 1,1 % 1,(-1) % 1,1 % 2,(-1) % 2,2 % 1,(-2) % 1,1 % 3,(-1) % 3,3 % 2]
--
rat :: Enumeration Rational
-- | Take a finite prefix from the beginning of an enumeration. takeE k
-- e always yields the empty enumeration for <math>, and
-- results in e whenever k is greater than or equal to
-- the cardinality of the enumeration. Otherwise takeE k e has
-- cardinality k and matches e from 0 to
-- k-1.
--
--
-- >>> enumerate $ takeE 3 (boundedEnum @Int)
-- [-9223372036854775808,-9223372036854775807,-9223372036854775806]
--
--
--
-- >>> enumerate $ takeE 2 (finiteList [1..5])
-- [1,2]
--
--
--
-- >>> enumerate $ takeE 0 (finiteList [1..5])
-- []
--
--
--
-- >>> enumerate $ takeE 7 (finiteList [1..5])
-- [1,2,3,4,5]
--
takeE :: Integer -> Enumeration a -> Enumeration a
-- | Drop some elements from the beginning of an enumeration. dropE k
-- e yields e unchanged if <math>, and results in the
-- empty enumeration whenever k is greater than or equal to the
-- cardinality of e.
--
--
-- >>> enumerate $ dropE 2 (finiteList [1..5])
-- [3,4,5]
--
--
--
-- >>> enumerate $ dropE 0 (finiteList [1..5])
-- [1,2,3,4,5]
--
--
--
-- >>> enumerate $ dropE 7 (finiteList [1..5])
-- []
--
dropE :: Integer -> Enumeration a -> Enumeration a
-- | Explicitly mark an enumeration as having an infinite cardinality,
-- ignoring the previous cardinality. It is sometimes necessary to use
-- this as a "hint" when constructing a recursive enumeration whose
-- cardinality would otherwise consist of an infinite sum of finite
-- cardinalities.
--
-- For example, consider the following definitions:
--
--
-- data Tree = L | B Tree Tree deriving Show
--
-- treesBad :: Enumeration Tree
-- treesBad = singleton L <|> B <$> treesBad <*> treesBad
--
-- trees :: Enumeration Tree
-- trees = infinite $ singleton L <|> B <$> trees <*> trees
--
--
-- Trying to use treesBad at all will simply hang, since trying
-- to compute its cardinality leads to infinite recursion.
--
--
-- >>> select treesBad 5
-- ^CInterrupted.
--
--
-- However, using infinite, as in the definition of
-- trees, provides the needed laziness:
--
--
-- >>> card trees
-- Infinite
--
-- >>> enumerate . takeE 3 $ trees
-- [L,B L L,B L (B L L)]
--
-- >>> select trees 87239862967296
-- B (B (B (B (B L L) (B (B (B L L) L) L)) (B L (B L (B L L)))) (B (B (B L (B L (B L L))) (B (B L L) (B L L))) (B (B L (B L (B L L))) L))) (B (B L (B (B (B L (B L L)) (B L L)) L)) (B (B (B L (B L L)) L) L))
--
infinite :: Enumeration a -> Enumeration a
-- | Zip two enumerations in parallel, producing the pair of elements at
-- each index. The resulting enumeration is truncated to the cardinality
-- of the smaller of the two arguments.
--
--
-- >>> enumerate $ zipE nat (boundedEnum @Bool)
-- [(0,False),(1,True)]
--
zipE :: Enumeration a -> Enumeration b -> Enumeration (a, b)
-- | Zip two enumerations in parallel, applying the given function to the
-- pair of elements at each index to produce a new element. The resulting
-- enumeration is truncated to the cardinality of the smaller of the two
-- arguments.
--
--
-- >>> enumerate $ zipWithE replicate (finiteList [1..10]) (dropE 35 (boundedEnum @Char))
-- ["#","$$","%%%","&&&&","'''''","((((((",")))))))","********","+++++++++",",,,,,,,,,,"]
--
zipWithE :: (a -> b -> c) -> Enumeration a -> Enumeration b -> Enumeration c
-- | Sum, i.e. disjoint union, of two enumerations. If both are
-- finite, all the values of the first will be enumerated before the
-- values of the second. If only one is finite, the values from the
-- finite enumeration will be listed first. If both are infinite, a fair
-- (alternating) interleaving is used, so that every value ends up at a
-- finite index in the result.
--
-- Note that the (<+>) operator is a synonym for
-- (<|>) from the Alternative instance for
-- Enumeration, which should be used in preference to
-- (<+>). (<+>) is provided as a separate
-- standalone operator to make it easier to document.
--
--
-- >>> enumerate . takeE 10 $ singleton 17 <|> nat
-- [17,0,1,2,3,4,5,6,7,8]
--
--
--
-- >>> enumerate . takeE 10 $ nat <|> singleton 17
-- [17,0,1,2,3,4,5,6,7,8]
--
--
--
-- >>> enumerate . takeE 10 $ nat <|> (negate <$> nat)
-- [0,0,1,-1,2,-2,3,-3,4,-4]
--
--
-- Note that this is not associative in a strict sense. In particular, it
-- may fail to be associative when mixing finite and infinite
-- enumerations:
--
--
-- >>> enumerate . takeE 10 $ nat <|> (singleton 17 <|> nat)
-- [0,17,1,0,2,1,3,2,4,3]
--
--
--
-- >>> enumerate . takeE 10 $ (nat <|> singleton 17) <|> nat
-- [17,0,0,1,1,2,2,3,3,4]
--
--
-- However, it is associative in several weaker senses:
--
--
-- - If all the enumerations are finite
-- - If all the enumerations are infinite
-- - If enumerations are considered equivalent up to reordering (they
-- are not, but considering them so may be acceptable in some
-- applications).
--
(<+>) :: Enumeration a -> Enumeration a -> Enumeration a
-- | Cartesian product of enumerations. If both are finite, uses a simple
-- lexicographic ordering. If only one is finite, the resulting
-- enumeration is still in lexicographic order, with the infinite
-- enumeration as the most significant component. For two infinite
-- enumerations, uses a fair diagonal interleaving.
--
--
-- >>> enumerate $ finiteList [1..3] >< finiteList "abcd"
-- [(1,'a'),(1,'b'),(1,'c'),(1,'d'),(2,'a'),(2,'b'),(2,'c'),(2,'d'),(3,'a'),(3,'b'),(3,'c'),(3,'d')]
--
--
--
-- >>> enumerate . takeE 10 $ finiteList "abc" >< nat
-- [('a',0),('b',0),('c',0),('a',1),('b',1),('c',1),('a',2),('b',2),('c',2),('a',3)]
--
--
--
-- >>> enumerate . takeE 10 $ nat >< finiteList "abc"
-- [(0,'a'),(0,'b'),(0,'c'),(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a')]
--
--
--
-- >>> enumerate . takeE 10 $ nat >< nat
-- [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]
--
--
-- Like (<+>), this operation is also not associative (not
-- even up to reassociating tuples).
(><) :: Enumeration a -> Enumeration b -> Enumeration (a, b)
-- | Fairly interleave a set of infinite enumerations.
--
-- For a finite set of infinite enumerations, a round-robin interleaving
-- is used. That is, if we think of an enumeration of enumerations as a
-- 2D matrix read off row-by-row, this corresponds to taking the
-- transpose of a matrix with finitely many infinite rows, turning it
-- into one with infinitely many finite rows. For an infinite set of
-- infinite enumerations, i.e. an infinite 2D matrix, the
-- resulting enumeration reads off the matrix by diagonals.
--
--
-- >>> enumerate . takeE 15 $ interleave (finiteList [nat, negate <$> nat, (*10) <$> nat])
-- [0,0,0,1,-1,10,2,-2,20,3,-3,30,4,-4,40]
--
--
--
-- >>> enumerate . takeE 15 $ interleave (always nat)
-- [0,0,1,0,1,2,0,1,2,3,0,1,2,3,4]
--
--
-- This function is similar to join in a hypothetical Monad
-- instance for Enumeration, but it only works when the inner
-- enumerations are all infinite.
--
-- To interleave a finite enumeration of enumerations, some of which may
-- be finite, you can use asum . enumerate. If you
-- want to interleave an infinite enumeration of finite enumerations, you
-- are out of luck.
interleave :: Enumeration (Enumeration a) -> Enumeration a
-- | Enumerate all possible values of type `Maybe a`, where the values of
-- type a are taken from the given enumeration.
--
--
-- >>> enumerate $ maybeOf (finiteList [1,2,3])
-- [Nothing,Just 1,Just 2,Just 3]
--
maybeOf :: Enumeration a -> Enumeration (Maybe a)
-- | Enumerae all possible values of type Either a b with inner
-- values taken from the given enumerations.
--
--
-- >>> enumerate . takeE 6 $ eitherOf nat nat
-- [Left 0,Right 0,Left 1,Right 1,Left 2,Right 2]
--
eitherOf :: Enumeration a -> Enumeration b -> Enumeration (Either a b)
-- | Enumerate all possible finite lists containing values from the given
-- enumeration.
--
--
-- >>> enumerate . takeE 15 $ listOf nat
-- [[],[0],[0,0],[1],[0,0,0],[1,0],[2],[0,1],[1,0,0],[2,0],[3],[0,0,0,0],[1,1],[2,0,0],[3,0]]
--
listOf :: Enumeration a -> Enumeration [a]
-- | Enumerate all possible finite subsets of values from the given
-- enumeration.
--
--
-- >>> enumerate $ finiteSubsetOf (finite 3)
-- [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]
--
finiteSubsetOf :: Enumeration a -> Enumeration [a]
-- | finiteEnumerationOf n a creates an enumeration of all
-- sequences of exactly n items taken from the enumeration a.
finiteEnumerationOf :: Int -> Enumeration a -> Enumeration (Enumeration a)
-- | One half of the isomorphism between <math> and <math>
-- which enumerates by diagonals: turn a particular natural number index
-- into its position in the 2D grid. That is, given this numbering of a
-- 2D grid:
--
--
-- 0 1 3 6 ...
-- 2 4 7
-- 5 8
-- 9
--
--
--
-- diagonal maps <math>
diagonal :: Integer -> (Integer, Integer)
instance GHC.Base.Functor Data.Enumeration.Enumeration
instance GHC.Classes.Ord Data.Enumeration.Cardinality
instance GHC.Classes.Eq Data.Enumeration.Cardinality
instance GHC.Show.Show Data.Enumeration.Cardinality
instance GHC.Base.Applicative Data.Enumeration.Enumeration
instance GHC.Base.Alternative Data.Enumeration.Enumeration
instance GHC.Num.Num Data.Enumeration.Cardinality
-- | An invertible enumeration is a bijection between a set of
-- values and the natural numbers (or a finite prefix thereof),
-- represented as a pair of inverse functions, one in each direction.
-- Hence they support efficient indexing and can be constructed for very
-- large finite sets. A few examples are shown below.
--
-- Compared to Data.Enumeration, one can also build invertible
-- enumerations of functions (or other type formers with contravariant
-- arguments); however, invertible enumerations no longer make for valid
-- Functor, Applicative, or Alternative instances.
--
-- This module exports many of the same names as Data.Enumeration;
-- the expectation is that you will choose one or the other to import,
-- though of course it is possible to import both if you qualify the
-- imports.
module Data.Enumeration.Invertible
-- | An invertible enumeration is a bijection between a set of enumerated
-- values and the natural numbers, or a finite prefix of the natural
-- numbers. An invertible enumeration is represented as a function from
-- natural numbers to values, paired with an inverse function that
-- returns the natural number index of a given value. Enumerations can
-- thus easily be constructed for very large sets, and support efficient
-- indexing and random sampling.
--
-- Note that IEnumeration cannot be made an instance of
-- Functor, Applicative, or Alternative. However, it
-- does support the functionOf combinator which cannot be
-- supported by Data.Enumeration.
data IEnumeration a
-- | The cardinality of a countable set: either a specific finite natural
-- number, or countably infinite.
data Cardinality
Finite :: !Integer -> Cardinality
Infinite :: Cardinality
-- | Get the cardinality of an enumeration.
card :: IEnumeration a -> Cardinality
-- | An index into an enumeration.
type Index = Integer
-- | Select the value at a particular index. Precondition: the index must
-- be strictly less than the cardinality.
select :: IEnumeration a -> Index -> a
-- | Compute the index of a particular value in its enumeration. Note that
-- the result of locate is only valid when given a value which is
-- actually in the range of the enumeration.
locate :: IEnumeration a -> a -> Index
-- | Test whether an enumeration is finite.
--
--
-- >>> isFinite (finiteList [1,2,3])
-- True
--
--
--
-- >>> isFinite nat
-- False
--
isFinite :: IEnumeration a -> Bool
-- | List the elements of an enumeration in order. Inverse of
-- finiteList.
enumerate :: IEnumeration a -> [a]
-- | The empty enumeration, with cardinality zero and no elements.
--
--
-- >>> card void
-- Finite 0
--
--
--
-- >>> enumerate void
-- []
--
void :: IEnumeration a
-- | The unit enumeration, with a single value of () at index 0.
--
--
-- >>> card unit
-- Finite 1
--
--
--
-- >>> enumerate unit
-- [()]
--
--
--
-- >>> locate unit ()
-- 0
--
unit :: IEnumeration ()
-- | An enumeration of a single given element at index 0.
--
--
-- >>> card (singleton 17)
-- Finite 1
--
--
--
-- >>> enumerate (singleton 17)
-- [17]
--
--
--
-- >>> locate (singleton 17) 17
-- 0
--
singleton :: a -> IEnumeration a
-- | A finite prefix of the natural numbers.
--
--
-- >>> card (finite 5)
-- Finite 5
--
-- >>> card (finite 1234567890987654321)
-- Finite 1234567890987654321
--
--
--
-- >>> enumerate (finite 5)
-- [0,1,2,3,4]
--
-- >>> enumerate (finite 0)
-- []
--
--
--
-- >>> locate (finite 5) 2
-- 2
--
finite :: Integer -> IEnumeration Integer
-- | Construct an enumeration from the elements of a finite list.
-- The elements of the list must all be distinct. To turn an enumeration
-- back into a list, use enumerate.
--
--
-- >>> enumerate (finiteList [2,3,8,1])
-- [2,3,8,1]
--
-- >>> select (finiteList [2,3,8,1]) 2
-- 8
--
-- >>> locate (finiteList [2,3,8,1]) 8
-- 2
--
--
-- finiteList does not work on infinite lists: inspecting the
-- cardinality of the resulting enumeration (something many of the
-- enumeration combinators need to do) will hang trying to compute the
-- length of the infinite list.
--
-- finiteList uses (!!) and findIndex internally
-- (which both take $O(n)$ time), so you probably want to avoid using it
-- on long lists. It would be possible to make a version with better
-- indexing performance by allocating a vector internally, but I am too
-- lazy to do it. If you have a good use case let me know (better yet,
-- submit a pull request).
finiteList :: Eq a => [a] -> IEnumeration a
-- | Enumerate all the values of a bounded Enum instance.
--
--
-- >>> enumerate (boundedEnum @Bool)
-- [False,True]
--
--
--
-- >>> select (boundedEnum @Char) 97
-- 'a'
--
-- >>> locate (boundedEnum @Char) 'Z'
-- 90
--
--
--
-- >>> card (boundedEnum @Int)
-- Finite 18446744073709551616
--
-- >>> select (boundedEnum @Int) 0
-- -9223372036854775808
--
boundedEnum :: forall a. (Enum a, Bounded a) => IEnumeration a
-- | The natural numbers, 0, 1, 2, ....
--
--
-- >>> enumerate . takeE 10 $ nat
-- [0,1,2,3,4,5,6,7,8,9]
--
nat :: IEnumeration Integer
-- | All integers in the order 0, 1, -1, 2, -2, 3, -3, ....
int :: IEnumeration Integer
-- | The positive rational numbers, enumerated according to the
-- Calkin-Wilf sequence.
--
--
-- >>> enumerate . takeE 10 $ cw
-- [1 % 1,1 % 2,2 % 1,1 % 3,3 % 2,2 % 3,3 % 1,1 % 4,4 % 3,3 % 5]
--
-- >>> locate cw (3 % 2)
-- 4
--
-- >>> locate cw (23 % 99)
-- 3183
--
cw :: IEnumeration Rational
-- | An enumeration of all rational numbers: 0 first, then each rational in
-- the Calkin-Wilf sequence followed by its negative.
--
--
-- >>> enumerate . takeE 10 $ rat
-- [0 % 1,1 % 1,(-1) % 1,1 % 2,(-1) % 2,2 % 1,(-2) % 1,1 % 3,(-1) % 3,3 % 2]
--
-- >>> locate rat (-45 % 61)
-- 2540
--
rat :: IEnumeration Rational
-- | Map a pair of inverse functions over an invertible enumeration of
-- a values to turn it into an invertible enumeration of
-- b values. Because invertible enumerations contain a
-- bijection to the natural numbers, we really do need both
-- directions of a bijection between a and b in order
-- to map. This is why IEnumeration cannot be an instance of
-- Functor.
mapE :: (a -> b) -> (b -> a) -> IEnumeration a -> IEnumeration b
-- | Take a finite prefix from the beginning of an enumeration. takeE k
-- e always yields the empty enumeration for <math>, and
-- results in e whenever k is greater than or equal to
-- the cardinality of the enumeration. Otherwise takeE k e has
-- cardinality k and matches e from 0 to
-- k-1.
--
--
-- >>> enumerate $ takeE 3 (boundedEnum @Int)
-- [-9223372036854775808,-9223372036854775807,-9223372036854775806]
--
--
--
-- >>> enumerate $ takeE 2 (finiteList [1..5])
-- [1,2]
--
--
--
-- >>> enumerate $ takeE 0 (finiteList [1..5])
-- []
--
--
--
-- >>> enumerate $ takeE 7 (finiteList [1..5])
-- [1,2,3,4,5]
--
takeE :: Integer -> IEnumeration a -> IEnumeration a
-- | Drop some elements from the beginning of an enumeration. dropE k
-- e yields e unchanged if <math>, and results in the
-- empty enumeration whenever k is greater than or equal to the
-- cardinality of e.
--
--
-- >>> enumerate $ dropE 2 (finiteList [1..5])
-- [3,4,5]
--
--
--
-- >>> enumerate $ dropE 0 (finiteList [1..5])
-- [1,2,3,4,5]
--
--
--
-- >>> enumerate $ dropE 7 (finiteList [1..5])
-- []
--
dropE :: Integer -> IEnumeration a -> IEnumeration a
-- | Zip two enumerations in parallel, producing the pair of elements at
-- each index. The resulting enumeration is truncated to the cardinality
-- of the smaller of the two arguments.
--
-- Note that defining zipWithE as in Data.Enumeration is
-- not possible since there would be no way to invert it in general.
-- However, one can use zipE in combination with mapE to
-- achieve a similar result.
--
--
-- >>> enumerate $ zipE nat (boundedEnum @Bool)
-- [(0,False),(1,True)]
--
--
--
-- >>> cs = mapE (uncurry replicate) (length &&& head) (zipE (finiteList [1..10]) (dropE 35 (boundedEnum @Char)))
--
-- >>> enumerate cs
-- ["#","$$","%%%","&&&&","'''''","((((((",")))))))","********","+++++++++",",,,,,,,,,,"]
--
-- >>> locate cs "********"
-- 7
--
zipE :: IEnumeration a -> IEnumeration b -> IEnumeration (a, b)
-- | Explicitly mark an enumeration as having an infinite cardinality,
-- ignoring the previous cardinality. It is sometimes necessary to use
-- this as a "hint" when constructing a recursive enumeration whose
-- cardinality would otherwise consist of an infinite sum of finite
-- cardinalities.
--
-- For example, consider the following definitions:
--
--
-- data Tree = L | B Tree Tree deriving Show
--
-- toTree :: Either () (Tree, Tree) -> Tree
-- toTree = either (const L) (uncurry B)
--
-- fromTree :: Tree -> Either () (Tree, Tree)
-- fromTree L = Left ()
-- fromTree (B l r) = Right (l,r)
--
-- treesBad :: IEnumeration Tree
-- treesBad = mapE toTree fromTree (unit <+> (treesBad >< treesBad))
--
-- trees :: IEnumeration Tree
-- trees = infinite $ mapE toTree fromTree (unit <+> (trees >< trees))
--
--
-- Trying to use treesBad at all will simply hang, since trying
-- to compute its cardinality leads to infinite recursion.
--
--
-- >>> select treesBad 5
-- ^CInterrupted.
--
--
-- However, using infinite, as in the definition of
-- trees, provides the needed laziness:
--
--
-- >>> card trees
-- Infinite
--
-- >>> enumerate . takeE 3 $ trees
-- [L,B L L,B L (B L L)]
--
-- >>> select trees 87239862967296
-- B (B (B (B (B L L) (B (B (B L L) L) L)) (B L (B L (B L L)))) (B (B (B L (B L (B L L))) (B (B L L) (B L L))) (B (B L (B L (B L L))) L))) (B (B L (B (B (B L (B L L)) (B L L)) L)) (B (B (B L (B L L)) L) L))
--
-- >>> select trees 123
-- B (B L (B L L)) (B (B L (B L L)) (B L (B L L)))
--
-- >>> locate trees (B (B L (B L L)) (B (B L (B L L)) (B L (B L L))))
-- 123
--
infinite :: IEnumeration a -> IEnumeration a
-- | Sum, i.e. disjoint union, of two enumerations. If both are
-- finite, all the values of the first will be enumerated before the
-- values of the second. If only one is finite, the values from the
-- finite enumeration will be listed first. If both are infinite, a fair
-- (alternating) interleaving is used, so that every value ends up at a
-- finite index in the result.
--
-- Note that this has a different type than the version in
-- Data.Enumeration. Here we require the output to carry an
-- explicit Either tag to make it invertible.
--
--
-- >>> enumerate . takeE 5 $ singleton 17 <+> nat
-- [Left 17,Right 0,Right 1,Right 2,Right 3]
--
--
--
-- >>> enumerate . takeE 5 $ nat <+> singleton 17
-- [Right 17,Left 0,Left 1,Left 2,Left 3]
--
--
--
-- >>> enumerate . takeE 5 $ nat <+> nat
-- [Left 0,Right 0,Left 1,Right 1,Left 2]
--
--
--
-- >>> locate (nat <+> nat) (Right 35)
-- 71
--
(<+>) :: IEnumeration a -> IEnumeration b -> IEnumeration (Either a b)
-- | Cartesian product of enumerations. If both are finite, uses a simple
-- lexicographic ordering. If only one is finite, the resulting
-- enumeration is still in lexicographic order, with the infinite
-- enumeration as the most significant component. For two infinite
-- enumerations, uses a fair diagonal interleaving.
--
--
-- >>> enumerate $ finiteList [1..3] >< finiteList "abcd"
-- [(1,'a'),(1,'b'),(1,'c'),(1,'d'),(2,'a'),(2,'b'),(2,'c'),(2,'d'),(3,'a'),(3,'b'),(3,'c'),(3,'d')]
--
--
--
-- >>> enumerate . takeE 10 $ finiteList "abc" >< nat
-- [('a',0),('b',0),('c',0),('a',1),('b',1),('c',1),('a',2),('b',2),('c',2),('a',3)]
--
--
--
-- >>> enumerate . takeE 10 $ nat >< finiteList "abc"
-- [(0,'a'),(0,'b'),(0,'c'),(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a')]
--
--
--
-- >>> enumerate . takeE 10 $ nat >< nat
-- [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]
--
--
--
-- >>> locate (nat >< nat) (1,1)
-- 4
--
-- >>> locate (nat >< nat) (36,45)
-- 3357
--
--
-- Like (<+>), this operation is also not associative (not
-- even up to reassociating tuples).
(><) :: IEnumeration a -> IEnumeration b -> IEnumeration (a, b)
-- | Fairly interleave a set of infinite enumerations.
--
-- For a finite set of infinite enumerations, a round-robin interleaving
-- is used. That is, if we think of an enumeration of enumerations as a
-- 2D matrix read off row-by-row, this corresponds to taking the
-- transpose of a matrix with finitely many infinite rows, turning it
-- into one with infinitely many finite rows. For an infinite set of
-- infinite enumerations, i.e. an infinite 2D matrix, the
-- resulting enumeration reads off the matrix by diagonals.
--
-- Note that the type of this function is slightly different than its
-- counterpart in Data.Enumeration: each enumerated value in the
-- output is tagged with an index indicating which input enumeration it
-- came from. This is required to make the result invertible, and is
-- analogous to the way the output values of <+> are tagged
-- with Left or Right; in fact, interleave can be
-- thought of as an iterated version of <+>, but with a more
-- efficient implementation.
interleave :: IEnumeration (IEnumeration a) -> IEnumeration (Index, a)
-- | Enumerate all possible values of type `Maybe a`, where the values of
-- type a are taken from the given enumeration.
--
--
-- >>> enumerate $ maybeOf (finiteList [1,2,3])
-- [Nothing,Just 1,Just 2,Just 3]
--
-- >>> locate (maybeOf (maybeOf (finiteList [1,2,3]))) (Just (Just 2))
-- 3
--
maybeOf :: IEnumeration a -> IEnumeration (Maybe a)
-- | Enumerae all possible values of type Either a b with inner
-- values taken from the given enumerations.
--
-- Note that for invertible enumerations, eitherOf is simply a
-- synonym for <+>.
--
--
-- >>> enumerate . takeE 6 $ eitherOf nat nat
-- [Left 0,Right 0,Left 1,Right 1,Left 2,Right 2]
--
eitherOf :: IEnumeration a -> IEnumeration b -> IEnumeration (Either a b)
-- | Enumerate all possible finite lists containing values from the given
-- enumeration.
--
--
-- >>> enumerate . takeE 15 $ listOf nat
-- [[],[0],[0,0],[1],[0,0,0],[1,0],[2],[0,1],[1,0,0],[2,0],[3],[0,0,0,0],[1,1],[2,0,0],[3,0]]
--
-- >>> locate (listOf nat) [3,4,20,5,19]
-- 666270815854068922513792635440014
--
listOf :: IEnumeration a -> IEnumeration [a]
-- | Enumerate all possible finite subsets of values from the given
-- enumeration. The elements in each list will always occur in increasing
-- order of their index in the given enumeration.
--
--
-- >>> enumerate $ finiteSubsetOf (finite 3)
-- [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]
--
--
--
-- >>> locate (finiteSubsetOf nat) [2,3,6,8]
-- 332
--
-- >>> 332 == 2^8 + 2^6 + 2^3 + 2^2
-- True
--
finiteSubsetOf :: IEnumeration a -> IEnumeration [a]
-- | finiteEnumerationOf n a creates an enumeration of all
-- sequences of exactly n items taken from the enumeration a.
--
--
-- >>> map E.enumerate . enumerate $ finiteEnumerationOf 2 (finite 3)
-- [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
--
--
--
-- >>> map E.enumerate . take 10 . enumerate $ finiteEnumerationOf 3 nat
-- [[0,0,0],[0,0,1],[1,0,0],[0,1,0],[1,0,1],[2,0,0],[0,0,2],[1,1,0],[2,0,1],[3,0,0]]
--
finiteEnumerationOf :: Int -> IEnumeration a -> IEnumeration (Enumeration a)
-- | functionOf a b creates an enumeration of all functions taking
-- values from the enumeration a and returning values from the
-- enumeration b. As a precondition, a must be finite;
-- otherwise functionOf throws an error.
--
--
-- >>> bbs = functionOf (boundedEnum @Bool) (boundedEnum @Bool)
--
-- >>> card bbs
-- Finite 4
--
-- >>> map (select bbs 2) [False, True]
-- [True,False]
--
-- >>> locate bbs not
-- 2
--
--
--
-- >>> locate (functionOf bbs (boundedEnum @Bool)) (\f -> f True)
-- 5
--
functionOf :: IEnumeration a -> IEnumeration b -> IEnumeration (a -> b)
-- | The other half of the isomorphism between <math> and
-- <math> which enumerates by diagonals: turn a pair of natural
-- numbers giving a position in the 2D grid into the number in the cell,
-- according to this numbering scheme:
--
--
-- 0 1 3 6 ...
-- 2 4 7
-- 5 8
-- 9
--
--
undiagonal :: (Integer, Integer) -> Integer