data-memocombinators-0.5.1: Combinators for building memo tables.

Copyright(c) Luke Palmer 2008-2010
LicenseBSD3
MaintainerLuke Palmer <lrpalmer@gmail.com>
Stabilityexperimental
Safe HaskellSafe
LanguageHaskell98

Data.MemoCombinators

Description

This module provides combinators for building memo tables over various data types, so that the type of table can be customized depending on the application.

This module is designed to be imported qualified, eg.

import qualified Data.MemoCombinators as Memo

Usage is straightforward: apply an object of type Memo a to a function of type a -> b, and get a memoized function of type a -> b. For example:

fib = Memo.integral fib'
   where
   fib' 0 = 0
   fib' 1 = 1
   fib' x = fib (x-1) + fib (x-2)

Synopsis

Documentation

type Memo a = forall r. (a -> r) -> a -> r Source

The type of a memo table for functions of a.

wrap :: (a -> b) -> (b -> a) -> Memo a -> Memo b Source

Given a memoizer for a and an isomorphism between a and b, build a memoizer for b.

memo2 :: Memo a -> Memo b -> (a -> b -> r) -> a -> b -> r Source

Memoize a two argument function (just apply the table directly for single argument functions).

memo3 :: Memo a -> Memo b -> Memo c -> (a -> b -> c -> r) -> a -> b -> c -> r Source

Memoize a three argument function.

memoSecond :: Memo b -> (a -> b -> r) -> a -> b -> r Source

Memoize the second argument of a function.

memoThird :: Memo c -> (a -> b -> c -> r) -> a -> b -> c -> r Source

Memoize the third argument of a function.

list :: Memo a -> Memo [a] Source

boundedList :: Int -> Memo a -> Memo [a] Source

Build a table which memoizes all lists of less than the given length.

either :: Memo a -> Memo b -> Memo (Either a b) Source

maybe :: Memo a -> Memo (Maybe a) Source

pair :: Memo a -> Memo b -> Memo (a, b) Source

enum :: Enum a => Memo a Source

Memoize an enum type.

integral :: Integral a => Memo a Source

Memoize an integral type.

bits :: (Num a, Ord a, Bits a) => Memo a Source

Memoize an ordered type with a bits instance.

switch :: (a -> Bool) -> Memo a -> Memo a -> Memo a Source

switch p a b uses the memo table a whenever p gives true and the memo table b whenever p gives false.

type RangeMemo a = (a, a) -> Memo a Source

The type of builders for ranged tables; takes a lower bound and an upper bound, and returns a memo table for that range.

arrayRange :: Ix a => RangeMemo a Source

Build a memo table for a range using a flat array. If items are given outside the range, don't memoize.

unsafeArrayRange :: Ix a => RangeMemo a Source

Build a memo table for a range using a flat array. If items are given outside the range, behavior is undefined.

chunks :: Ix a => RangeMemo a -> [(a, a)] -> Memo a Source

Given a list of ranges, (lazily) build a memo table for each one and combine them using linear search.