chimera: Lazy, infinite streams with O(1) indexing.

[ bsd3, library, unclassified ] [ Propose Tags ]

[Skip to Readme]
Versions [faq] 0.2.0.0
Dependencies base (>=4.8 && <5), chimera, ghc-prim, transformers, vector [details]
License BSD-3-Clause
Copyright 2017-2018 Bodigrim
Author Bodigrim
Maintainer andrew.lelechenko@gmail.com
Revised Revision 1 made by Bodigrim at Fri Feb 22 22:23:02 UTC 2019
Home page https://github.com/Bodigrim/chimera#readme
Source repo head: git clone https://github.com/Bodigrim/chimera
Uploaded by Bodigrim at Tue Dec 4 00:23:12 UTC 2018
Distributions NixOS:0.2.0.0, Stackage:0.2.0.0
Executables find-foo
Downloads 114 total (23 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-12-04 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for chimera-0.2.0.0

[back to package description]

chimera

Lazy, infinite streams with O(1) indexing. Most useful to memoize functions.

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 Chimera using tabulate and access this stream via index instead of recalculation of isOdd:

isOddBS :: Chimera
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 :: Chimera
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 :: Chimera
isPrimeBS = tabulateFix isPrimeF

isPrime' :: Word -> Bool
isPrime' = index isPrimeBS