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

[ bsd3, data, library ] [ Propose Tags ]

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

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.2.0.0, 0.3.0.0, 0.3.1.0, 0.3.2.0, 0.3.3.0, 0.3.4.0, 0.4.0.0, 0.4.1.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 2019-02-22T22:23:02Z
Home page https://github.com/Bodigrim/chimera#readme
Source repo head: git clone https://github.com/Bodigrim/chimera
Uploaded by Bodigrim at 2018-12-04T00:23:12Z
Distributions Arch:0.4.1.0, LTSHaskell:0.3.4.0, NixOS:0.3.4.0, Stackage:0.4.1.0
Reverse Dependencies 2 direct, 7878 indirect [details]
Executables find-foo
Downloads 4846 total (114 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-12-04 [all 1 reports]

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