summaryrefslogtreecommitdiff log msg author committer range
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ``` ``````# bit-stream Lazy, infinite, compact stream of `Bool` with O(1) indexing. Most useful for memoization of predicates. ## Example 1 Consider following predicate: ```haskell 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`: ```haskell 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`: ```haskell isOddF :: (Word -> Bool) -> Word -> Bool isOddF _ 0 = False isOddF f n = not (f (n - 1)) ``` and use `tabulateFix`: ```haskell 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. ```haskell 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: ```haskell 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: ```haskell isPrimeBS :: BitStream isPrimeBS = tabulateFix isPrimeF isPrime' :: Word -> Bool isPrime' = index isPrimeBS ``` ``````