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


-- | Lazy, infinite, compact stream of Bool with O(1) indexing.
--   
--   Lazy, infinite, compact stream of Bool with O(1) indexing.
@package bit-stream
@version 0.1.0.2


-- | Lazy, infinite, compact stream of <a>Bool</a> with O(1) indexing. Most
--   useful for memoization of predicates.
--   
--   <b>Example 1</b>
--   
--   Consider following predicate:
--   
--   <pre>
--   isOdd :: Word -&gt; Bool
--   isOdd 0 = False
--   isOdd n = not (isOdd (n - 1))
--   </pre>
--   
--   Its computation is expensive, so we'd like to memoize its values into
--   <a>BitStream</a> using <a>tabulate</a> and access this stream via
--   <a>index</a> instead of recalculation of <tt>isOdd</tt>:
--   
--   <pre>
--   isOddBS :: BitStream
--   isOddBS = tabulate isOdd
--   
--   isOdd' :: Word -&gt; Bool
--   isOdd' = index isOddBS
--   </pre>
--   
--   We can do even better by replacing part of recursive calls to
--   <tt>isOdd</tt> by indexing memoized values. Write <tt>isOddF</tt> such
--   that <tt>isOdd = <a>fix</a> isOddF</tt>:
--   
--   <pre>
--   isOddF :: (Word -&gt; Bool) -&gt; Word -&gt; Bool
--   isOddF _ 0 = False
--   isOddF f n = not (f (n - 1))
--   </pre>
--   
--   and use <a>tabulateFix</a>:
--   
--   <pre>
--   isOddBS :: BitStream
--   isOddBS = tabulateFix isOddF
--   
--   isOdd' :: Word -&gt; Bool
--   isOdd' = index isOddBS
--   </pre>
--   
--   <b>Example 2</b>
--   
--   Define a predicate, which checks whether its argument is a prime
--   number by trial division.
--   
--   <pre>
--   isPrime :: Word -&gt; Bool
--   isPrime n
--     | n &lt; 2     = False
--     | n &lt; 4     = True
--     | even n    = False
--     | otherwise = and [ n `rem` d /= 0 | d &lt;- [3, 5 .. ceiling (sqrt (fromIntegral n))], isPrime d]
--   </pre>
--   
--   Convert it to unfixed form:
--   
--   <pre>
--   isPrimeF :: (Word -&gt; Bool) -&gt; Word -&gt; Bool
--   isPrimeF f n
--     | n &lt; 2     = False
--     | n &lt; 4     = True
--     | even n    = False
--     | otherwise = and [ n `rem` d /= 0 | d &lt;- [3, 5 .. ceiling (sqrt (fromIntegral n))], f d]
--   </pre>
--   
--   Create its memoized version for faster evaluation:
--   
--   <pre>
--   isPrimeBS :: BitStream
--   isPrimeBS = tabulateFix isPrimeF
--   
--   isPrime' :: Word -&gt; Bool
--   isPrime' = index isPrimeBS
--   </pre>
module Data.BitStream

-- | Compact representation of infinite stream of <a>Bool</a>.
--   
--   It spends one bit (1/8 byte) for one <a>Bool</a> in store. Compare it
--   to at least 24 bytes per element in <tt>[Bool]</tt>, approximately 2
--   bytes per element in <tt>IntSet</tt> and 1 byte per element in unboxed
--   <tt>Vector Bool</tt>.
--   
--   It also offers indexing in constant time. Compare it to linear time
--   for lists and logarithmic time for sets.
--   
--   Moreover, it is lazy: querying n-th element triggers computation of
--   first <tt>max(64, 2 ^ ceiling (logBase 2 n))</tt> elements only. On
--   contrary, sets and unboxed vectors are completely strict.
data BitStream

-- | Create a bit stream from the predicate. The predicate must be
--   well-defined for any value of argument and should not return
--   <a>error</a> / <a>undefined</a>.
tabulate :: (Word -> Bool) -> BitStream

-- | Create a bit stream from the unfixed predicate. The predicate must be
--   well-defined for any value of argument and should not return
--   <a>error</a> / <a>undefined</a>.
tabulateFix :: ((Word -> Bool) -> Word -> Bool) -> BitStream

-- | Create a bit stream from the monadic predicate. The predicate must be
--   well-defined for any value of argument and should not return
--   <a>error</a> / <a>undefined</a>.
tabulateM :: forall m. Monad m => (Word -> m Bool) -> m BitStream

-- | Create a bit stream from the unfixed monadic predicate. The predicate
--   must be well-defined for any value of argument and should not return
--   <a>error</a> / <a>undefined</a>.
tabulateFixM :: forall m. Monad m => ((Word -> m Bool) -> Word -> m Bool) -> m BitStream

-- | Convert a bit stream back to predicate. Indexing itself works in O(1)
--   time, but triggers evaluation and allocation of surrounding elements
--   of the stream, if they were not computed before.
index :: BitStream -> Word -> Bool

-- | Map over all indices and respective elements in the stream.
mapWithKey :: (Word -> Bool -> Bool) -> BitStream -> BitStream

-- | Traverse over all indices and respective elements in the stream.
traverseWithKey :: forall m. Monad m => (Word -> Bool -> m Bool) -> BitStream -> m BitStream

-- | Element-wise <a>not</a>.
not :: BitStream -> BitStream

-- | Zip two streams with the function, which is provided with an index and
--   respective elements of both streams.
zipWithKey :: (Word -> Bool -> Bool -> Bool) -> BitStream -> BitStream -> BitStream

-- | Zip two streams with the monadic function, which is provided with an
--   index and respective elements of both streams.
zipWithKeyM :: forall m. Monad m => (Word -> Bool -> Bool -> m Bool) -> BitStream -> BitStream -> m BitStream

-- | Element-wise <a>and</a>.
and :: BitStream -> BitStream -> BitStream

-- | Element-wise <a>or</a>.
or :: BitStream -> BitStream -> BitStream


-- | Helpers for continuous mappings, useful to memoize predicates on
--   <a>Int</a> (instead of <a>Word</a> only), and predicates over two,
--   three and more arguments.
--   
--   <b> Example</b>
--   
--   An infinite plain board of live and dead cells (common for cellular
--   automatons, e. g., <a>Conway's Game of Life</a>) can be represented as
--   a predicate <tt>board</tt> :: <a>Int</a> -&gt; <a>Int</a> -&gt;
--   <a>Bool</a>. Assume that we want to convert it to memoized form. We
--   cannot do it directly, because <a>tabulate</a> accepts predicates from
--   <a>Word</a> to <a>Bool</a> only.
--   
--   The first step is to define:
--   
--   <pre>
--   board'' :: Int -&gt; Int -&gt; Bool
--   board'' x y = board' (intToWord x) (intToWord y)
--   
--   board' :: Word -&gt; Word -&gt; Bool
--   board' x y = board (wordToInt x) (wordToInt y)
--   </pre>
--   
--   This is better, but <tt>board'</tt> is a predicate over two arguments,
--   and we need it to be a predicate over one. Conversion to Z-curve and
--   back does the trick:
--   
--   <pre>
--   board'' :: Int -&gt; Int -&gt; Bool
--   board'' x y = board1 $ toZCurve (intToWord x) (intToWord y)
--   
--   board' :: Word -&gt; Bool
--   board' z = let (x, y) = fromZCurve z in
--              board (wordToInt x) (wordToInt y)
--   </pre>
--   
--   Now we are ready to insert memoizing layer:
--   
--   <pre>
--   board'' :: Int -&gt; Int -&gt; Bool
--   board'' x y = index board' $ toZCurve (intToWord x) (intToWord y)
--   
--   board' :: BitStream
--   board' = tabulate $
--     \z -&gt; let (x, y) = fromZCurve z in
--           board (wordToInt x) (wordToInt y)
--   </pre>
module Data.BitStream.ContinuousMapping

-- | Total map, which satisfies inequality abs (<a>intToWord</a> x -
--   <a>intToWord</a> y) ≤ 2 abs(x - y).
--   
--   Note that this is not the case for <a>fromIntegral</a> :: <a>Int</a>
--   -&gt; <a>Word</a>, because it has a discontinuity between −1 and 0.
--   
--   <pre>
--   &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; map wordToInt [0..10]
--   [0,-1,1,-2,2,-3,3,-4,4,-5,5]
--   </pre>
wordToInt :: Word -> Int

-- | Total map from plain to line, continuous almost everywhere. See
--   <a>Z-order curve</a>.
--   
--   Only lower halfs of bits of arguments are used (32 bits on 64-bit
--   architecture).
--   
--   <pre>
--   &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 :: Word -> Word -> Word

-- | Inverse for <a>toZCurve</a>. See <a>Z-order curve</a>.
--   
--   <pre>
--   &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 -> (Word, Word)

-- | Total map from space to line, continuous almost everywhere. See
--   <a>Z-order curve</a>.
--   
--   Only lower thirds of bits of arguments are used (21 bits on 64-bit
--   architecture).
--   
--   <pre>
--   &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 :: Word -> Word -> Word -> Word

-- | Inverse for <a>toZCurve3</a>. See <a>Z-order curve</a>.
--   
--   <pre>
--   &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 -> (Word, Word, Word)


-- | Helpers for mapping to <a>rough numbers</a> and back. Mostly useful 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 improve performance of
--   repetitive reevaluation by memoization:
--   
--   <pre>
--   isPrimeBS :: BitStream
--   isPrimeBS = tabulate isPrime
--   
--   isPrime' :: Word -&gt; Bool
--   isPrime' = index isPrimeBS
--   </pre>
--   
--   However, it is well-known that the only even prime is 2. So we can
--   save half of space by memoizing the predicate for odd numbers only:
--   
--   <pre>
--   isPrimeBS2 :: BitStream
--   isPrimeBS2 = tabulate (\n -&gt; isPrime (2 * n + 1))
--   
--   isPrime2' :: Word -&gt; Bool
--   isPrime2' n
--     | n == 2    = True
--     | even n    = False
--     | otherwise = index isPrimeBS2 ((n - 1) `quot` 2)
--   </pre>
--   
--   or, using <a>fromWheel2</a> and <a>toWheel2</a>,
--   
--   <pre>
--   isPrimeBS2 :: BitStream
--   isPrimeBS2 = tabulate (isPrime . fromWheel2)
--   
--   isPrime2' :: Word -&gt; Bool
--   isPrime2' n
--     | n == 2    = True
--     | even n    = False
--     | otherwise = index isPrimeBS2 (toWheel2 n)
--   </pre>
--   
--   Well, we also know that all primes, except 2 and 3, are coprime to 6;
--   and all primes, except 2, 3 and 5, are coprime 30. So we can save even
--   more space by writing
--   
--   <pre>
--   isPrimeBS6 :: BitStream
--   isPrimeBS6 = tabulate (isPrime . fromWheel6)
--   
--   isPrime6' :: Word -&gt; Bool
--   isPrime6' n
--     | n `elem` [2, 3] = True
--     | n `gcd` 6 /= 1  = False
--     | otherwise       = index isPrimeBS6 (toWheel6 n)
--   </pre>
--   
--   or
--   
--   <pre>
--   isPrimeBS30 :: BitStream
--   isPrimeBS30 = tabulate (isPrime . fromWheel30)
--   
--   isPrime30' :: Word -&gt; Bool
--   isPrime30' n
--     | n `elem` [2, 3, 5] = True
--     | n `gcd` 30 /= 1    = False
--     | otherwise          = index isPrimeBS30 (toWheel30 n)
--   </pre>
module Data.BitStream.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; 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; 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; 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; 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
