Memoize a function: repeating calls to memoize f n would compute f n only once and cache the result in VChimera. This is just a shortcut for index . tabulate.

memoize f n = f n

Note that a could be a function type itself. This allows, for instance, to define

memoize2 :: (Word -> Word -> a) -> Word -> Word -> a
memoize2 = memoize . (memoize .)

memoize3 :: (Word -> Word -> Word -> a) -> Word -> Word -> Word -> a
memoize3 = memoize . (memoize2 .)

Since: 0.3.0.0

For a given f memoize a recursive function fix f, caching results in VChimera. This is just a shortcut for index . tabulateFix.

memoizeFix f n = fix f n

For example, imagine that we want to memoize Fibonacci numbers:

>>> fibo n = if n < 2 then toInteger n else fibo (n - 1) + fibo (n - 2)

Can we find fiboF such that fibo = fix fiboF? Just replace all recursive calls to fibo with f:

>>> fiboF f n = if n < 2 then toInteger n else f (n - 1) + f (n - 2)

Now we are ready to use memoizeFix:

>>> memoizeFix fiboF 10
55
>>> memoizeFix fiboF 100
354224848179261915075

This function can be used even when arguments of recursive calls are not strictly decreasing, but they might not get memoized. For example, here is a routine to measure the length of Collatz sequence:

>>> collatzF f n = if n <= 1 then 0 else 1 + f (if even n then n `quot` 2 else 3 * n + 1)
>>> memoizeFix collatzF 27
111

If you want to memoize all recursive calls, even with increasing arguments, you can employ another function of the same signature: fix . (memoize .). It is less efficient though.

To memoize recursive functions of multiple arguments, one can use

memoizeFix2 :: ((Word -> Word -> a) -> Word -> Word -> a) -> Word -> Word -> a
memoizeFix2 = let memoize2 = memoize . (memoize .) in Data.Function.fix . (memoize2 .)

Since: 0.3.0.0

Lazy infinite streams with elements from a, backed by a Vector v (boxed, unboxed, storable, etc.). Use tabulate, tabulateFix, etc. to create a stream and index to access its arbitrary elements in constant time.

Since: 0.2.0.0

Streams backed by boxed vectors.

Since: 0.3.0.0

Streams backed by unboxed vectors.

Since: 0.3.0.0

Create a stream of values of a given function. Once created it can be accessed via index or toList.

>>> ch = tabulate (^ 2) :: UChimera Word
>>> index ch 9
81
>>> take 10 (toList ch)
[0,1,4,9,16,25,36,49,64,81]

Note that a could be a function type itself, so one can tabulate a function of multiple arguments as a nested Chimera of Chimeras.

Since: 0.2.0.0

For a given f create a stream of values of a recursive function fix f. Once created it can be accessed via index or toList.

For example, imagine that we want to tabulate Catalan numbers:

>>> catalan n = if n == 0 then 1 else sum [ catalan i * catalan (n - 1 - i) | i <- [0 .. n - 1] ]

Can we find catalanF such that catalan = fix catalanF? Just replace all recursive calls to catalan with f:

>>> catalanF f n = if n == 0 then 1 else sum [ f i * f (n - 1 - i) | i <- [0 .. n - 1] ]

Now we are ready to use tabulateFix:

>>> ch = tabulateFix catalanF :: VChimera Integer
>>> index ch 9
4862
>>> take 10 (toList ch)
[1,1,2,5,14,42,132,429,1430,4862]

Note: Only recursive function calls with decreasing arguments are memoized. If full memoization is desired, use tabulateFix' instead.

Using unboxed / storable / primitive vectors with tabulateFix is not always a win: the internal memoizing routine necessarily uses boxed vectors to achieve a certain degree of laziness, so converting to UChimera is extra work. This could pay off in a long run by reducing memory residence though.

Since: 0.2.0.0

Fully memoizing version of tabulateFix. This function will tabulate every recursive call, but might allocate a lot of memory in doing so. For example, the following piece of code calculates the highest number reached by the Collatz sequence of a given number, but also allocates tens of gigabytes of memory, because the Collatz sequence will spike to very high numbers.

>>> collatzF :: (Word -> Word) -> (Word -> Word)
>>> collatzF _ 0 = 0
>>> collatzF f n = if n <= 2 then 4 else n `max` f (if even n then n `quot` 2 else 3 * n + 1)
>>> 
>>> maximumBy (comparing $ index $ tabulateFix' collatzF) [0..1000000]
...

Using memoizeFix instead fixes the problem:

>>> maximumBy (comparing $ memoizeFix collatzF) [0..1000000]
56991483520

Since tabulateFix' memoizes all recursive calls, even with increasing argument, you most likely do not want to use it with anything else than boxed vectors (VChimera).

Since: 0.3.2.0

iterate f x returns an infinite stream, generated by repeated applications of f to x.

It holds that index (iterate f x) 0 is equal to x.

>>> ch = iterate (+ 1) 0 :: UChimera Int
>>> take 10 (toList ch)
[0,1,2,3,4,5,6,7,8,9]

Since: 0.3.0.0

iterateWithIndex f x returns an infinite stream, generated by applications of f to a current index and previous value, starting from x.

It holds that index (iterateWithIndex f x) 0 is equal to x.

>>> ch = iterateWithIndex (+) 100 :: UChimera Word
>>> take 10 (toList ch)
[100,101,103,106,110,115,121,128,136,145]

Since: 0.3.4.0

unfoldr f x returns an infinite stream, generated by repeated applications of f to x, similar to unfoldr.

>>> ch = unfoldr (\acc -> (acc * acc, acc + 1)) 0 :: UChimera Int
>>> take 10 (toList ch)
[0,1,4,9,16,25,36,49,64,81]

Since: 0.3.3.0

Return an infinite repetition of a given vector. Throw an error on an empty vector.

>>> ch = cycle (Data.Vector.fromList [4, 2]) :: VChimera Int
>>> take 10 (toList ch)
[4,2,4,2,4,2,4,2,4,2]

Since: 0.3.0.0

Create a stream of values from a given prefix, followed by default value afterwards.

Since: 0.3.3.0

Create a stream of values from a given prefix, followed by default value afterwards.

Since: 0.3.3.0

Create a stream of values from a given infinite list.

Since: 0.3.4.0

Intertleave two streams, sourcing even elements from the first one and odd elements from the second one.

>>> ch = interleave (tabulate id) (tabulate (+ 100)) :: UChimera Word
>>> take 10 (toList ch)
[0,100,1,101,2,102,3,103,4,104]

Since: 0.3.3.0

Prepend a given vector to a stream of values.

Since: 0.4.0.0

Index a stream in a constant time.

>>> ch = tabulate (^ 2) :: UChimera Word
>>> index ch 9
81

Since: 0.2.0.0

Right-associative fold, necessarily lazy in the accumulator. Any unconditional attempt to force the accumulator even to WHNF will hang the computation. E. g., the following definition isn't productive:

import Data.List.NonEmpty (NonEmpty(..))
toNonEmpty = foldr (\a (x :| xs) -> a :| x : xs) :: VChimera a -> NonEmpty a

One should use lazy patterns, e. g.,

toNonEmpty = foldr (\a ~(x :| xs) -> a :| x : xs)

Convert a stream to an infinite list.

>>> ch = tabulate (^ 2) :: UChimera Word
>>> take 10 (toList ch)
[0,1,4,9,16,25,36,49,64,81]

Since: 0.3.0.0

Convert a stream to a proper infinite list.

Since: 0.3.4.0

Monadic version of tabulate.

Since: 0.2.0.0

Monadic version of tabulateFix. There are no particular guarantees about the order of recursive calls: they may be executed more than once or executed in different order. That said, monadic effects must be idempotent and commutative.

Since: 0.2.0.0

Monadic version of tabulateFix'.

Since: 0.3.3.0

Monadic version of iterate.

Since: 0.3.0.0

Monadic version of iterateWithIndex.

Since: 0.3.4.0

Monadic version of unfoldr.

Since: 0.3.3.0

Map subvectors of a stream, using a given length-preserving function.

Since: 0.3.0.0

Map subvectors of a stream, using a given length-preserving function. The first argument of the function is the index of the first element of subvector in the Chimera.

Since: 0.4.0.0

Traverse subvectors of a stream, using a given length-preserving function.

Be careful, because similar to tabulateM, only lazy monadic effects can be executed in a finite time: lazy state monad is fine, but strict one is not.

Since: 0.3.3.0

Zip subvectors from two streams, using a given length-preserving function.

Since: 0.3.3.0

Zip subvectors from two streams, using a given monadic length-preserving function. Caveats for tabulateM and traverseSubvectors apply.

Since: 0.3.3.0

Take a slice of Chimera, represented as a list on consecutive subvectors.

Since: 0.3.3.0