-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Lazy infinite streams with O(1) indexing and applications for memoization
--   
--   There are plenty of memoizing libraries on Hackage, but they usually
--   fall into two categories:
--   
--   <ul>
--   <li>Store cache as a flat array, enabling us to obtain cached values
--   in O(1) time, which is nice. The drawback is that one must specify the
--   size of the array beforehand, limiting an interval of inputs, and
--   actually allocate it at once.</li>
--   <li>Store cache as a lazy binary tree. Thanks to laziness, one can
--   freely use the full range of inputs. The drawback is that obtaining
--   values from a tree takes logarithmic time and is unfriendly to CPU
--   cache, which kinda defeats the purpose.</li>
--   </ul>
--   
--   This package intends to tackle both issues, providing a data type
--   <a>Chimera</a> for lazy infinite compact streams with cache-friendly
--   O(1) indexing.
--   
--   Additional features include:
--   
--   <ul>
--   <li>memoization of recursive functions and recurrent sequences,</li>
--   <li>memoization of functions of several, possibly signed
--   arguments,</li>
--   <li>efficient memoization of boolean predicates.</li>
--   </ul>
@package chimera
@version 0.4.1.0


-- | Helpers for continuous mappings, useful to memoize functions on
--   <a>Int</a> (instead of <a>Word</a> only) and functions over two and
--   three arguments.
--   
--   <b>Example 1</b>
--   
--   Imagine writing a program to simulate <a>Rule 90</a>. This is a
--   cellular automaton, which consists of an infinite one-dimensional line
--   of cells, each being either dead (<a>False</a>) or alive
--   (<a>True</a>). If two neighbours of a cell are equal, it becomes dead
--   on the next step, otherwise alive.
--   
--   Usually cellular automata are modelled by a finite vector. This is a
--   bit suboptimal, because cellular automata may grow in different
--   directions over time, but with a finite vector one has to define a
--   bounding segment well beforehand. Moreover, what if we are interested
--   to explore an evolution of an essentially infinite initial
--   configuration?
--   
--   It would be natural to encode an initial configuration as a function
--   <a>Int</a> <tt>-&gt;</tt> <a>Bool</a>, which takes a coordinate and
--   returns the status of the corresponding cell. Define a function, which
--   translates the automaton to the next step:
--   
--   <pre>
--   step :: (Int -&gt; Bool) -&gt; (Int -&gt; Bool)
--   step current = \n -&gt; current (n - 1) /= current (n + 1)
--   </pre>
--   
--   Unfortunately, iterating <tt>step</tt> would be extremely slow because
--   of branching recursion. One could suggest to introduce a caching
--   layer:
--   
--   <pre>
--   step :: (Int -&gt; Bool) -&gt; (Int -&gt; Bool)
--   step current = \n -&gt; current' (n - 1) /= current' (n + 1)
--     where
--       current' = memoize (current . fromIntegral) . fromIntegral
--   </pre>
--   
--   Unfortunately, it would not work well, because <a>fromIntegral</a>
--   <tt>::</tt> <a>Int</a> <tt>-&gt;</tt> <a>Word</a> maps <tt>-1</tt> to
--   <a>maxBound</a> and it would take ages to memoize everything up to
--   <a>maxBound</a>. But continuous mappings <a>intToWord</a> and
--   <a>wordToInt</a> avoid this issue:
--   
--   <pre>
--   step :: (Int -&gt; Bool) -&gt; (Int -&gt; Bool)
--   step current = \n -&gt; current' (n - 1) /= current' (n + 1)
--     where
--       current' = memoize (current . wordToInt) . intToWord
--   </pre>
--   
--   <b>Example 2</b>
--   
--   What about another famous cellular automaton: <a>Conway's Game of
--   Life</a>? It is two-dimensional, so its state can be represented as a
--   function <a>Int</a> <tt>-&gt;</tt> <a>Int</a> <tt>-&gt;</tt>
--   <a>Bool</a>. Following the approach above, we would like to memoize
--   such functions. Namely, cast the state to <a>Word</a> <tt>-&gt;</tt>
--   <a>Bool</a>, ready for memoization:
--   
--   <pre>
--   cast :: (Int -&gt; Int -&gt; Bool) -&gt; (Word -&gt; Bool)
--   cast f = \n -&gt; let (x, y) = fromZCurve n in f (fromHalf x) (fromHalf y)
--     where
--       fromHalf :: HalfWord -&gt; Int
--       fromHalf = wordToInt . fromIntegral @HalfWord @Word
--   </pre>
--   
--   and then back:
--   
--   <pre>
--   uncast :: (Word -&gt; Bool) -&gt; (Int -&gt; Int -&gt; Bool)
--   uncast g = \x y -&gt; g (toZCurve (toHalf x) (toHalf y))
--     where
--       toHalf :: Int -&gt; HalfWord
--       toHalf = fromIntegral @Word @HalfWord . intToWord
--   </pre>
module Data.Chimera.ContinuousMapping

-- | Total map, which satisfies
--   
--   <pre>
--   abs (intToWord x - intToWord y) &lt;= 2 * abs (x - y)
--   </pre>
--   
--   Note that usual <a>fromIntegral</a> <tt>::</tt> <a>Int</a>
--   <tt>-&gt;</tt> <a>Word</a> does not satisfy this inequality, because
--   it has a discontinuity between −1 and 0.
--   
--   <pre>
--   &gt;&gt;&gt; map intToWord [-5..5]
--   [9,7,5,3,1,0,2,4,6,8,10]
--   </pre>
intToWord :: Int -> Word

-- | Inverse for <a>intToWord</a>.
--   
--   <pre>
--   &gt;&gt;&gt; map wordToInt [0..10]
--   [0,-1,1,-2,2,-3,3,-4,4,-5,5]
--   </pre>
wordToInt :: Word -> Int

-- | 32 bits on 64-bit architecture, 16 bits on 32-bit architecture.
--   
--   To create a value of type <a>HalfWord</a> use <a>fromIntegral</a>.
data HalfWord

-- | Total map from plain to line, continuous almost everywhere. See
--   <a>Z-order curve</a>.
--   
--   <pre>
--   &gt;&gt;&gt; [ toZCurve x y | x &lt;- [0..3], y &lt;- [0..3] ]
--   [0,2,8,10,1,3,9,11,4,6,12,14,5,7,13,15]
--   </pre>
toZCurve :: HalfWord -> HalfWord -> Word

-- | Inverse for <a>toZCurve</a>. See <a>Z-order curve</a>.
--   
--   <pre>
--   &gt;&gt;&gt; map fromZCurve [0..15]
--   [(0,0),(1,0),(0,1),(1,1),(2,0),(3,0),(2,1),(3,1),(0,2),(1,2),(0,3),(1,3),(2,2),(3,2),(2,3),(3,3)]
--   </pre>
fromZCurve :: Word -> (HalfWord, HalfWord)

-- | For an input function <tt>f</tt> return function <tt>g</tt> such that
--   <a>fix</a> <tt>f</tt> = (<a>fix</a> <tt>g</tt> <a>.</a>) <a>.</a>
--   <a>toZCurve</a>.
throughZCurveFix :: ((HalfWord -> HalfWord -> a) -> HalfWord -> HalfWord -> a) -> (Word -> a) -> Word -> a

-- | 21 bits on 64-bit architecture, 10 bits on 32-bit architecture.
--   
--   To create a value of type <a>ThirdWord</a> use <a>fromIntegral</a>.
data ThirdWord

-- | Total map from space to line, continuous almost everywhere. See
--   <a>Z-order curve</a>.
--   
--   <pre>
--   &gt;&gt;&gt; [ toZCurve3 x y z | x &lt;- [0..3], y &lt;- [0..3], z &lt;- [0..3] ]
--   [0,4,32,36,2,6,34,38,16,20,48,52,18,22,50,54,1,5,33,37,3,7,35,39,17,21,49,53,19,23,51,55,
--   8,12,40,44,10,14,42,46,24,28,56,60,26,30,58,62,9,13,41,45,11,15,43,47,25,29,57,61,27,31,59,63]
--   </pre>
toZCurve3 :: ThirdWord -> ThirdWord -> ThirdWord -> Word

-- | Inverse for <a>toZCurve3</a>. See <a>Z-order curve</a>.
--   
--   <pre>
--   &gt;&gt;&gt; map fromZCurve3 [0..63]
--   [(0,0,0),(1,0,0),(0,1,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1),(2,0,0),(3,0,0),(2,1,0),(3,1,0),(2,0,1),(3,0,1),(2,1,1),(3,1,1),
--    (0,2,0),(1,2,0),(0,3,0),(1,3,0),(0,2,1),(1,2,1),(0,3,1),(1,3,1),(2,2,0),(3,2,0),(2,3,0),(3,3,0),(2,2,1),(3,2,1),(2,3,1),(3,3,1),
--    (0,0,2),(1,0,2),(0,1,2),(1,1,2),(0,0,3),(1,0,3),(0,1,3),(1,1,3),(2,0,2),(3,0,2),(2,1,2),(3,1,2),(2,0,3),(3,0,3),(2,1,3),(3,1,3),
--    (0,2,2),(1,2,2),(0,3,2),(1,3,2),(0,2,3),(1,2,3),(0,3,3),(1,3,3),(2,2,2),(3,2,2),(2,3,2),(3,3,2),(2,2,3),(3,2,3),(2,3,3),(3,3,3)]
--   </pre>
fromZCurve3 :: Word -> (ThirdWord, ThirdWord, ThirdWord)

-- | For an input function <tt>f</tt> return function <tt>g</tt> such that
--   <a>fix</a> <tt>f</tt> = ((<a>fix</a> <tt>g</tt> <a>.</a>) <a>.</a>)
--   <a>.</a> <a>toZCurve3</a>.
throughZCurveFix3 :: ((ThirdWord -> ThirdWord -> ThirdWord -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a) -> (Word -> a) -> Word -> a
instance GHC.Internal.Bits.Bits Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Bits.Bits Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Enum.Bounded Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Enum.Bounded Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Enum.Enum Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Enum.Enum Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Classes.Eq Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Classes.Eq Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Bits.FiniteBits Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Bits.FiniteBits Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Real.Integral Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Real.Integral Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Num.Num Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Num.Num Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Classes.Ord Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Classes.Ord Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Read.Read Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Read.Read Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Real.Real Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Real.Real Data.Chimera.ContinuousMapping.ThirdWord
instance GHC.Internal.Show.Show Data.Chimera.ContinuousMapping.HalfWord
instance GHC.Internal.Show.Show Data.Chimera.ContinuousMapping.ThirdWord


-- | Lazy infinite streams with O(1) indexing.
module Data.Chimera

-- | Memoize a function: repeating calls to <a>memoize</a> <tt>f</tt>
--   <tt>n</tt> would compute <tt>f</tt> <tt>n</tt> only once and cache the
--   result in <a>VChimera</a>. This is just a shortcut for <a>index</a>
--   <a>.</a> <a>tabulate</a>.
--   
--   <pre>
--   memoize f n = f n
--   </pre>
--   
--   Note that <tt>a</tt> could be a function type itself. This allows, for
--   instance, to define
--   
--   <pre>
--   memoize2 :: (Word -&gt; Word -&gt; a) -&gt; Word -&gt; Word -&gt; a
--   memoize2 = memoize . (memoize .)
--   
--   memoize3 :: (Word -&gt; Word -&gt; Word -&gt; a) -&gt; Word -&gt; Word -&gt; Word -&gt; a
--   memoize3 = memoize . (memoize2 .)
--   </pre>
memoize :: (Word -> a) -> Word -> a

-- | For a given <tt>f</tt> memoize a recursive function <a>fix</a>
--   <tt>f</tt>, caching results in <a>VChimera</a>. This is just a
--   shortcut for <a>index</a> <a>.</a> <a>tabulateFix</a>.
--   
--   <pre>
--   memoizeFix f n = fix f n
--   </pre>
--   
--   For example, imagine that we want to memoize <a>Fibonacci numbers</a>:
--   
--   <pre>
--   &gt;&gt;&gt; fibo n = if n &lt; 2 then toInteger n else fibo (n - 1) + fibo (n - 2)
--   </pre>
--   
--   Can we find <tt>fiboF</tt> such that <tt>fibo</tt> = <a>fix</a>
--   <tt>fiboF</tt>? Just replace all recursive calls to <tt>fibo</tt> with
--   <tt>f</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; fiboF f n = if n &lt; 2 then toInteger n else f (n - 1) + f (n - 2)
--   </pre>
--   
--   Now we are ready to use <a>memoizeFix</a>:
--   
--   <pre>
--   &gt;&gt;&gt; memoizeFix fiboF 10
--   55
--   
--   &gt;&gt;&gt; memoizeFix fiboF 100
--   354224848179261915075
--   </pre>
--   
--   This function can be used even when arguments of recursive calls are
--   not strictly decreasing, but they might not get memoized. For example,
--   here is a routine to measure the length of <a>Collatz sequence</a>:
--   
--   <pre>
--   &gt;&gt;&gt; collatzF f n = if n &lt;= 1 then 0 else 1 + f (if even n then n `quot` 2 else 3 * n + 1)
--   
--   &gt;&gt;&gt; memoizeFix collatzF 27
--   111
--   </pre>
--   
--   If you want to memoize all recursive calls, even with increasing
--   arguments, you can employ another function of the same signature:
--   <a>fix</a> <a>.</a> (<a>memoize</a> <a>.</a>). It is less efficient
--   though.
--   
--   To memoize recursive functions of multiple arguments, one can use
--   
--   <pre>
--   memoizeFix2 :: ((Word -&gt; Word -&gt; a) -&gt; Word -&gt; Word -&gt; a) -&gt; Word -&gt; Word -&gt; a
--   memoizeFix2 = let memoize2 = memoize . (memoize .) in Data.Function.fix . (memoize2 .)
--   </pre>
memoizeFix :: ((Word -> a) -> Word -> a) -> Word -> a

-- | Lazy infinite streams with elements from <tt>a</tt>, backed by a
--   <a>Vector</a> <tt>v</tt> (boxed, unboxed, storable, etc.). Use
--   <a>tabulate</a>, <a>tabulateFix</a>, etc. to create a stream and
--   <a>index</a> to access its arbitrary elements in constant time.
data Chimera (v :: k -> Type) (a :: k)

-- | Streams backed by boxed vectors.
type VChimera = Chimera Vector

-- | Streams backed by unboxed vectors.
type UChimera = Chimera Vector

-- | Create a stream of values of a given function. Once created it can be
--   accessed via <a>index</a> or <a>toList</a>.
--   
--   <pre>
--   &gt;&gt;&gt; ch = tabulate (^ 2) :: UChimera Word
--   
--   &gt;&gt;&gt; index ch 9
--   81
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [0,1,4,9,16,25,36,49,64,81]
--   </pre>
--   
--   Note that <tt>a</tt> could be a function type itself, so one can
--   tabulate a function of multiple arguments as a nested <a>Chimera</a>
--   of <a>Chimera</a>s.
tabulate :: forall (v :: Type -> Type) a. Vector v a => (Word -> a) -> Chimera v a

-- | For a given <tt>f</tt> create a stream of values of a recursive
--   function <a>fix</a> <tt>f</tt>. Once created it can be accessed via
--   <a>index</a> or <a>toList</a>.
--   
--   For example, imagine that we want to tabulate <a>Catalan numbers</a>:
--   
--   <pre>
--   &gt;&gt;&gt; catalan n = if n == 0 then 1 else sum [ catalan i * catalan (n - 1 - i) | i &lt;- [0 .. n - 1] ]
--   </pre>
--   
--   Can we find <tt>catalanF</tt> such that <tt>catalan</tt> = <a>fix</a>
--   <tt>catalanF</tt>? Just replace all recursive calls to
--   <tt>catalan</tt> with <tt>f</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; catalanF f n = if n == 0 then 1 else sum [ f i * f (n - 1 - i) | i &lt;- [0 .. n - 1] ]
--   </pre>
--   
--   Now we are ready to use <a>tabulateFix</a>:
--   
--   <pre>
--   &gt;&gt;&gt; ch = tabulateFix catalanF :: VChimera Integer
--   
--   &gt;&gt;&gt; index ch 9
--   4862
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [1,1,2,5,14,42,132,429,1430,4862]
--   </pre>
--   
--   <b>Note</b>: Only recursive function calls with decreasing arguments
--   are memoized. If full memoization is desired, use <a>tabulateFix'</a>
--   instead.
--   
--   Using unboxed / storable / primitive vectors with <a>tabulateFix</a>
--   is not always a win: the internal memoizing routine necessarily uses
--   boxed vectors to achieve a certain degree of laziness, so converting
--   to <a>UChimera</a> is extra work. This could pay off in a long run by
--   reducing memory residence though.
tabulateFix :: forall (v :: Type -> Type) a. (Vector v a, Typeable v) => ((Word -> a) -> Word -> a) -> Chimera v a

-- | Fully memoizing version of <a>tabulateFix</a>. This function will
--   tabulate every recursive call, but might allocate a lot of memory in
--   doing so. For example, the following piece of code calculates the
--   highest number reached by the <a>Collatz sequence</a> of a given
--   number, but also allocates tens of gigabytes of memory, because the
--   Collatz sequence will spike to very high numbers.
--   
--   <pre>
--   &gt;&gt;&gt; collatzF :: (Word -&gt; Word) -&gt; (Word -&gt; Word)
--   
--   &gt;&gt;&gt; collatzF _ 0 = 0
--   
--   &gt;&gt;&gt; collatzF f n = if n &lt;= 2 then 4 else n `max` f (if even n then n `quot` 2 else 3 * n + 1)
--   
--   &gt;&gt;&gt; 
--   
--   &gt;&gt;&gt; maximumBy (comparing $ index $ tabulateFix' collatzF) [0..1000000]
--   ...
--   </pre>
--   
--   Using <a>memoizeFix</a> instead fixes the problem:
--   
--   <pre>
--   &gt;&gt;&gt; maximumBy (comparing $ memoizeFix collatzF) [0..1000000]
--   56991483520
--   </pre>
--   
--   Since <a>tabulateFix'</a> memoizes all recursive calls, even with
--   increasing argument, you most likely do not want to use it with
--   anything else than boxed vectors (<a>VChimera</a>).
tabulateFix' :: forall (v :: Type -> Type) a. (Vector v a, Typeable v) => ((Word -> a) -> Word -> a) -> Chimera v a

-- | <a>iterate</a> <tt>f</tt> <tt>x</tt> returns an infinite stream,
--   generated by repeated applications of <tt>f</tt> to <tt>x</tt>.
--   
--   It holds that <a>index</a> (<a>iterate</a> <tt>f</tt> <tt>x</tt>) 0 is
--   equal to <tt>x</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; ch = iterate (+ 1) 0 :: UChimera Int
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [0,1,2,3,4,5,6,7,8,9]
--   </pre>
iterate :: forall (v :: Type -> Type) a. Vector v a => (a -> a) -> a -> Chimera v a

-- | <a>iterateWithIndex</a> <tt>f</tt> <tt>x</tt> returns an infinite
--   stream, generated by applications of <tt>f</tt> to a current index and
--   previous value, starting from <tt>x</tt>.
--   
--   It holds that <a>index</a> (<a>iterateWithIndex</a> <tt>f</tt>
--   <tt>x</tt>) 0 is equal to <tt>x</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; ch = iterateWithIndex (+) 100 :: UChimera Word
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [100,101,103,106,110,115,121,128,136,145]
--   </pre>
iterateWithIndex :: forall (v :: Type -> Type) a. Vector v a => (Word -> a -> a) -> a -> Chimera v a

-- | <a>unfoldr</a> <tt>f</tt> <tt>x</tt> returns an infinite stream,
--   generated by repeated applications of <tt>f</tt> to <tt>x</tt>,
--   similar to <a>unfoldr</a>.
--   
--   <pre>
--   &gt;&gt;&gt; ch = unfoldr (\acc -&gt; (acc * acc, acc + 1)) 0 :: UChimera Int
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [0,1,4,9,16,25,36,49,64,81]
--   </pre>
unfoldr :: forall (v :: Type -> Type) b a. Vector v b => (a -> (b, a)) -> a -> Chimera v b

-- | Return an infinite repetition of a given vector. Throw an error on an
--   empty vector.
--   
--   <pre>
--   &gt;&gt;&gt; ch = cycle (Data.Vector.fromList [4, 2]) :: VChimera Int
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [4,2,4,2,4,2,4,2,4,2]
--   </pre>
cycle :: Vector v a => v a -> Chimera v a

-- | Create a stream of values from a given prefix, followed by default
--   value afterwards.
fromListWithDef :: forall (v :: Type -> Type) a. Vector v a => a -> [a] -> Chimera v a

-- | Create a stream of values from a given prefix, followed by default
--   value afterwards.
fromVectorWithDef :: Vector v a => a -> v a -> Chimera v a

-- | Create a stream of values from a given infinite list.
fromInfinite :: forall (v :: Type -> Type) a. Vector v a => Infinite a -> Chimera v a

-- | Intertleave two streams, sourcing even elements from the first one and
--   odd elements from the second one.
--   
--   <pre>
--   &gt;&gt;&gt; ch = interleave (tabulate id) (tabulate (+ 100)) :: UChimera Word
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [0,100,1,101,2,102,3,103,4,104]
--   </pre>
interleave :: forall (v :: Type -> Type) a. Vector v a => Chimera v a -> Chimera v a -> Chimera v a

-- | Prepend a given vector to a stream of values.
prependVector :: Vector v a => v a -> Chimera v a -> Chimera v a

-- | Index a stream in a constant time.
--   
--   <pre>
--   &gt;&gt;&gt; ch = tabulate (^ 2) :: UChimera Word
--   
--   &gt;&gt;&gt; index ch 9
--   81
--   </pre>
index :: forall (v :: Type -> Type) a. Vector v a => Chimera v a -> Word -> a

-- | Right-associative fold, necessarily lazy in the accumulator. Any
--   unconditional attempt to force the accumulator even to WHNF will hang
--   the computation. E. g., the following definition isn't productive:
--   
--   <pre>
--   import Data.List.NonEmpty (NonEmpty(..))
--   toNonEmpty = foldr (\a (x :| xs) -&gt; a :| x : xs) :: VChimera a -&gt; NonEmpty a
--   </pre>
--   
--   One should use lazy patterns, e. g.,
--   
--   <pre>
--   toNonEmpty = foldr (\a ~(x :| xs) -&gt; a :| x : xs)
--   </pre>
foldr :: forall (v :: Type -> Type) a b. Vector v a => (a -> b -> b) -> Chimera v a -> b

-- | Convert a stream to an infinite list.
--   
--   <pre>
--   &gt;&gt;&gt; ch = tabulate (^ 2) :: UChimera Word
--   
--   &gt;&gt;&gt; take 10 (toList ch)
--   [0,1,4,9,16,25,36,49,64,81]
--   </pre>
toList :: forall (v :: Type -> Type) a. Vector v a => Chimera v a -> [a]

-- | Convert a stream to a proper infinite list.
toInfinite :: forall (v :: Type -> Type) a. Vector v a => Chimera v a -> Infinite a

-- | Monadic version of <a>tabulate</a>.
tabulateM :: forall m (v :: Type -> Type) a. (Monad m, Vector v a) => (Word -> m a) -> m (Chimera v a)

-- | Monadic version of <a>tabulateFix</a>. There are no particular
--   guarantees about the order of recursive calls: they may be executed
--   more than once or executed in different order. That said, monadic
--   effects must be idempotent and commutative.
tabulateFixM :: forall m (v :: Type -> Type) a. (Monad m, Vector v a, Typeable v) => ((Word -> m a) -> Word -> m a) -> m (Chimera v a)

-- | Monadic version of <a>tabulateFix'</a>.
tabulateFixM' :: forall m (v :: Type -> Type) a. (Monad m, Vector v a, Typeable v) => ((Word -> m a) -> Word -> m a) -> m (Chimera v a)

-- | Monadic version of <a>iterate</a>.
iterateM :: forall m (v :: Type -> Type) a. (Monad m, Vector v a) => (a -> m a) -> a -> m (Chimera v a)

-- | Monadic version of <a>iterateWithIndex</a>.
iterateWithIndexM :: forall m (v :: Type -> Type) a. (Monad m, Vector v a) => (Word -> a -> m a) -> a -> m (Chimera v a)

-- | Monadic version of <a>unfoldr</a>.
unfoldrM :: forall m (v :: Type -> Type) b a. (Monad m, Vector v b) => (a -> m (b, a)) -> a -> m (Chimera v b)

-- | Map subvectors of a stream, using a given length-preserving function.
mapSubvectors :: (Vector u a, Vector v b) => (u a -> v b) -> Chimera u a -> Chimera v b

-- | Map subvectors of a stream, using a given length-preserving function.
--   The first argument of the function is the index of the first element
--   of subvector in the <a>Chimera</a>.
imapSubvectors :: (Vector u a, Vector v b) => (Word -> u a -> v b) -> Chimera u a -> Chimera v b

-- | Traverse subvectors of a stream, using a given length-preserving
--   function.
--   
--   Be careful, because similar to <a>tabulateM</a>, only lazy monadic
--   effects can be executed in a finite time: lazy state monad is fine,
--   but strict one is not.
traverseSubvectors :: (Vector u a, Vector v b, Applicative m) => (u a -> m (v b)) -> Chimera u a -> m (Chimera v b)

-- | Zip subvectors from two streams, using a given length-preserving
--   function.
zipWithSubvectors :: (Vector u a, Vector v b, Vector w c) => (u a -> v b -> w c) -> Chimera u a -> Chimera v b -> Chimera w c

-- | Zip subvectors from two streams, using a given monadic
--   length-preserving function. Caveats for <a>tabulateM</a> and
--   <a>traverseSubvectors</a> apply.
zipWithMSubvectors :: (Vector u a, Vector v b, Vector w c, Applicative m) => (u a -> v b -> m (w c)) -> Chimera u a -> Chimera v b -> m (Chimera w c)

-- | Take a slice of <a>Chimera</a>, represented as a list on consecutive
--   subvectors.
sliceSubvectors :: Vector v a => Int -> Int -> Chimera v a -> [v a]


-- | Helpers for mapping to <a>rough numbers</a> and back. This has various
--   applications in number theory.
--   
--   <b>Example</b>
--   
--   Let <tt>isPrime</tt> be an expensive predicate, which checks whether
--   its argument is a prime number. We can memoize it as usual:
--   
--   <pre>
--   isPrimeCache1 :: UChimera Bool
--   isPrimeCache1 = tabulate isPrime
--   
--   isPrime1 :: Word -&gt; Bool
--   isPrime1 = index isPrimeCache1
--   </pre>
--   
--   But one may argue that since the only even prime number is 2, it is
--   quite wasteful to cache <tt>isPrime</tt> for even arguments. So we can
--   save half the space by memoizing it for odd numbers only:
--   
--   <pre>
--   isPrimeCache2 :: UChimera Bool
--   isPrimeCache2 = tabulate (isPrime . (\n -&gt; 2 * n + 1))
--   
--   isPrime2 :: Word -&gt; Bool
--   isPrime2 n
--     | n == 2    = True
--     | even n    = False
--     | otherwise = index isPrimeCache2 ((n - 1) `quot` 2)
--   </pre>
--   
--   Here <tt>\n -&gt; 2 * n + 1</tt> maps n to the (n+1)-th odd number,
--   and <tt>\n -&gt; (n - 1) `quot` 2</tt> takes it back. These functions
--   are available below as <a>fromWheel2</a> and <a>toWheel2</a>.
--   
--   Odd numbers are the simplest example of numbers, lacking small prime
--   factors (so called <a>rough numbers</a>). Removing numbers, having
--   small prime factors, is sometimes called <a>wheel sieving</a>.
--   
--   One can go further and exclude not only even numbers, but also
--   integers, divisible by 3. To do this we need a function which maps n
--   to the (n+1)-th number coprime with 2 and 3 (thus, with 6) and its
--   inverse: namely, <a>fromWheel6</a> and <a>toWheel6</a>. Then write
--   
--   <pre>
--   isPrimeCache6 :: UChimera Bool
--   isPrimeCache6 = tabulate (isPrime . fromWheel6)
--   
--   isPrime6 :: Word -&gt; Bool
--   isPrime6 n
--     | n `elem` [2, 3] = True
--     | n `gcd` 6 /= 1  = False
--     | otherwise       = index isPrimeCache6 (toWheel6 n)
--   </pre>
--   
--   Thus, the wheel of 6 saves more space, improving memory locality.
--   
--   (If you need to reduce memory consumption even further, consider using
--   <a>Bit</a> wrapper, which provides an instance of unboxed vector,
--   packing one boolean per bit instead of one boolean per byte for
--   <a>Bool</a>)
module Data.Chimera.WheelMapping

-- | <a>fromWheel2</a> n is the (n+1)-th positive odd number. Sequence
--   <a>A005408</a>.
--   
--   <pre>
--   map fromWheel2 [0..] == [ n | n &lt;- [0..], n `gcd` 2 == 1 ]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map fromWheel2 [0..9]
--   [1,3,5,7,9,11,13,15,17,19]
--   </pre>
fromWheel2 :: Word -> Word

-- | Left inverse for <a>fromWheel2</a>. Monotonically non-decreasing
--   function.
--   
--   <pre>
--   toWheel2 . fromWheel2 == id
--   </pre>
toWheel2 :: Word -> Word

-- | <a>fromWheel6</a> n is the (n+1)-th positive number, not divisible by
--   2 or 3. Sequence <a>A007310</a>.
--   
--   <pre>
--   map fromWheel6 [0..] == [ n | n &lt;- [0..], n `gcd` 6 == 1 ]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map fromWheel6 [0..9]
--   [1,5,7,11,13,17,19,23,25,29]
--   </pre>
fromWheel6 :: Word -> Word

-- | Left inverse for <a>fromWheel6</a>. Monotonically non-decreasing
--   function.
--   
--   <pre>
--   toWheel6 . fromWheel6 == id
--   </pre>
toWheel6 :: Word -> Word

-- | <a>fromWheel30</a> n is the (n+1)-th positive number, not divisible by
--   2, 3 or 5. Sequence <a>A007775</a>.
--   
--   <pre>
--   map fromWheel30 [0..] == [ n | n &lt;- [0..], n `gcd` 30 == 1 ]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map fromWheel30 [0..9]
--   [1,7,11,13,17,19,23,29,31,37]
--   </pre>
fromWheel30 :: Word -> Word

-- | Left inverse for <a>fromWheel30</a>. Monotonically non-decreasing
--   function.
--   
--   <pre>
--   toWheel30 . fromWheel30 == id
--   </pre>
toWheel30 :: Word -> Word

-- | <a>fromWheel210</a> n is the (n+1)-th positive number, not divisible
--   by 2, 3, 5 or 7. Sequence <a>A008364</a>.
--   
--   <pre>
--   map fromWheel210 [0..] == [ n | n &lt;- [0..], n `gcd` 210 == 1 ]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map fromWheel210 [0..9]
--   [1,11,13,17,19,23,29,31,37,41]
--   </pre>
fromWheel210 :: Word -> Word

-- | Left inverse for <a>fromWheel210</a>. Monotonically non-decreasing
--   function.
--   
--   <pre>
--   toWheel210 . fromWheel210 == id
--   </pre>
toWheel210 :: Word -> Word
