Copyright | (c) 2017 Andrew Lelechenko |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | None |
Language | Haskell2010 |
Lazy, infinite, compact stream of Bool
with O(1) indexing.
Most useful for memoization of predicates.
Example 1
Consider following predicate:
isOdd :: Word -> Bool isOdd 0 = False isOdd n = not (isOdd (n - 1))
Its computation is expensive, so we'd like to memoize its values into
BitStream
using tabulate
and access this stream via index
instead of recalculation of isOdd
:
isOddBS :: BitStream isOddBS = tabulate isOdd isOdd' :: Word -> Bool isOdd' = index isOddBS
We can do even better by replacing part of recursive calls to isOdd
by indexing memoized values. Write isOddF
such that isOdd =
:fix
isOddF
isOddF :: (Word -> Bool) -> Word -> Bool isOddF _ 0 = False isOddF f n = not (f (n - 1))
and use tabulateFix
:
isOddBS :: BitStream isOddBS = tabulateFix isOddF isOdd' :: Word -> Bool isOdd' = index isOddBS
Example 2
Define a predicate, which checks whether its argument is a prime number by trial division.
isPrime :: Word -> Bool isPrime n | n < 2 = False | n < 4 = True | even n = False | otherwise = and [ n `rem` d /= 0 | d <- [3, 5 .. ceiling (sqrt (fromIntegral n))], isPrime d]
Convert it to unfixed form:
isPrimeF :: (Word -> Bool) -> Word -> Bool isPrimeF f n | n < 2 = False | n < 4 = True | even n = False | otherwise = and [ n `rem` d /= 0 | d <- [3, 5 .. ceiling (sqrt (fromIntegral n))], f d]
Create its memoized version for faster evaluation:
isPrimeBS :: BitStream isPrimeBS = tabulateFix isPrimeF isPrime' :: Word -> Bool isPrime' = index isPrimeBS
- data BitStream
- tabulate :: (Word -> Bool) -> BitStream
- tabulateFix :: ((Word -> Bool) -> Word -> Bool) -> BitStream
- tabulateM :: forall m. Monad m => (Word -> m Bool) -> m BitStream
- tabulateFixM :: forall m. Monad m => ((Word -> m Bool) -> Word -> m Bool) -> m BitStream
- index :: BitStream -> Word -> Bool
- mapWithKey :: (Word -> Bool -> Bool) -> BitStream -> BitStream
- traverseWithKey :: forall m. Monad m => (Word -> Bool -> m Bool) -> BitStream -> m BitStream
- not :: BitStream -> BitStream
- zipWithKey :: (Word -> Bool -> Bool -> Bool) -> BitStream -> BitStream -> BitStream
- zipWithKeyM :: forall m. Monad m => (Word -> Bool -> Bool -> m Bool) -> BitStream -> BitStream -> m BitStream
- and :: BitStream -> BitStream -> BitStream
- or :: BitStream -> BitStream -> BitStream
Documentation
Compact representation of infinite stream of Bool
.
It spends one bit (1/8 byte) for one Bool
in store.
Compare it to at least 24 bytes per element in [Bool]
,
approximately 2 bytes per element in IntSet
and 1 byte per element in unboxed Vector Bool
.
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 max(64, 2 ^ ceiling (logBase 2 n))
elements only. On contrary,
sets and unboxed vectors are completely strict.
index :: BitStream -> Word -> Bool Source #
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.
mapWithKey :: (Word -> Bool -> Bool) -> BitStream -> BitStream Source #
Map over all indices and respective elements in the stream.
traverseWithKey :: forall m. Monad m => (Word -> Bool -> m Bool) -> BitStream -> m BitStream Source #
Traverse over all indices and respective elements in the stream.
zipWithKey :: (Word -> Bool -> Bool -> Bool) -> BitStream -> BitStream -> BitStream Source #
Zip two streams with the function, which is provided with an index and respective elements of both streams.