chimera: Lazy infinite streams with O(1) indexing

[ bsd3, data, library, unclassified ] [ Propose Tags ]

There are plenty of memoizing libraries on Hackage, but they usually fall into two categories:

This package intends to tackle both issues, providing a data type Chimera for lazy infinite compact streams with cache-friendly O(1) indexing.

Additional features include:


[Skip to Readme]
Versions [faq] 0.2.0.0, 0.3.0.0
Dependencies base (>=4.9 && <5), vector [details]
License BSD-3-Clause
Copyright 2017-2019 Bodigrim
Author Bodigrim
Maintainer andrew.lelechenko@gmail.com
Category Data
Home page https://github.com/Bodigrim/chimera#readme
Source repo head: git clone https://github.com/Bodigrim/chimera
Uploaded by Bodigrim at Tue Dec 31 01:20:01 UTC 2019
Distributions NixOS:0.3.0.0, Stackage:0.2.0.0
Downloads 487 total (94 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-12-31 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for chimera-0.3.0.0

[back to package description]

chimera

Lazy infinite compact streams with cache-friendly O(1) indexing and applications for memoization.


Imagine having a function f :: Word -> a, which is expensive to evaluate. We would like to memoize it, returning g :: Word -> a, which does effectively the same, but transparently caches results to speed up repetitive re-evaluation.

There are plenty of memoizing libraries on Hackage, but they usually fall into two categories:

  • Store cache as a flat array, enabling us to obtain cached values in O(1) time, which is nice. The drawback is that one must specify the size of the array beforehand, limiting an interval of inputs, and actually allocate it at once.

  • Store cache as a lazy binary tree. Thanks to laziness, one can freely use the full range of inputs. The drawback is that obtaining values from a tree takes logarithmic time and is unfriendly to CPU cache, which kinda defeats the purpose.

This package intends to tackle both issues, providing a data type Chimera for lazy infinite compact streams with cache-friendly O(1) indexing.

Additional features include:

  • memoization of recursive functions and recurrent sequences,
  • memoization of functions of several, possibly signed arguments,
  • efficient memoization of boolean predicates.

Example 1

Consider the following predicate:

isOdd :: Word -> Bool
isOdd n = if n == 0 then False else not (isOdd (n - 1))

Its computation is expensive, so we'd like to memoize it:

isOdd' :: Word -> Bool
isOdd' = memoize isOdd

This is fine to avoid re-evaluation for the same arguments. But isOdd does not use this cache internally, going all the way of recursive calls to n = 0. We can do better, if we rewrite isOdd as a fix point of isOddF:

isOddF :: (Word -> Bool) -> Word -> Bool
isOddF f n = if n == 0 then False else not (f (n - 1))

and invoke tabulateFix to pass cache into recursive calls as well:

isOdd' :: Word -> Bool
isOdd' = memoizeFix isOddF

Example 2

Define a predicate, which checks whether its argument is a prime number, using trial division.

isPrime :: Word -> Bool
isPrime n = n > 1 && and [ n `rem` d /= 0 | d <- [2 .. floor (sqrt (fromIntegral n))], isPrime d]

This is certainly an expensive recursive computation and we would like to speed up its evaluation by wrappping into a caching layer. Convert the predicate to an unfixed form such that isPrime = fix isPrimeF:

isPrimeF :: (Word -> Bool) -> Word -> Bool
isPrimeF f n = n > 1 && and [ n `rem` d /= 0 | d <- [2 .. floor (sqrt (fromIntegral n))], f d]

Now create its memoized version for rapid evaluation:

isPrime' :: Word -> Bool
isPrime' = memoizeFix isPrimeF