purescript-open-memoize

Type classes for creating memoized functions.

Installation

spago install open-memoize

Documentation

Module documentation is published on Pursuit.

Building

$ npm run clean && npm run update-docs && npm run format && npm run build && npm run test

Example

The following Fibonacci function implementation is slow, because its call graph grows exponentially in the size of its argument:

let fibonacciSlow 0 = 0
    fibonacciSlow 1 = 1
    fibonacciSlow n = fibonacciSlow (n - 1) +
                      fibonacciSlow (n - 2)

The memoize function can be used to improve the performance of this function, by tabulating intermediate results:

let fibonacciSlow 0 = 0
    fibonacciSlow 1 = 1
    fibonacciSlow n = fibonacci (n - 1) +
                      fibonacci (n - 2)

    fibonacci = memoize $ \n -> fibonacciSlow n

Note that fibonacciSlow has been modified to call the faster fibonacci function.

The memoize function can be applied whenever there is a Tabulate instance for the function argument type. This library provides instances of the Tabulate type class for common types, such as Maybe, Either and Tuple.

Related resources

• Slides: Elegant memoization by Conal Elliott - @conal