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

Copyright | (c) Luke Palmer 2008-2010
License | BSD3
Maintainer | Luke Palmer <lrpalmer@gmail.com>
Stability | experimental
Safe Haskell | Safe-Inferred
Language | Haskell98

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

- type Memo a = forall r. (a -> r) -> a -> r
- wrap :: (a -> b) -> (b -> a) -> Memo a -> Memo b
- memo2 :: Memo a -> Memo b -> (a -> b -> r) -> a -> b -> r
- memo3 :: Memo a -> Memo b -> Memo c -> (a -> b -> c -> r) -> a -> b -> c -> r
- memoSecond :: Memo b -> (a -> b -> r) -> a -> b -> r
- memoThird :: Memo c -> (a -> b -> c -> r) -> a -> b -> c -> r
- bool :: Memo Bool
- char :: Memo Char
- list :: Memo a -> Memo [a]
- boundedList :: Int -> Memo a -> Memo [a]
- either :: Memo a -> Memo b -> Memo (Either a b)
- maybe :: Memo a -> Memo (Maybe a)
- unit :: Memo ()
- pair :: Memo a -> Memo b -> Memo (a, b)
- enum :: Enum a => Memo a
- integral :: Integral a => Memo a
- bits :: (Num a, Ord a, Bits a) => Memo a
- switch :: (a -> Bool) -> Memo a -> Memo a -> Memo a
- type RangeMemo a = (a, a) -> Memo a
- arrayRange :: Ix a => RangeMemo a
- unsafeArrayRange :: Ix a => RangeMemo a
- chunks :: Ix a => RangeMemo a -> [(a, a)] -> Memo a

# 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.

bool :: Memo Bool Source #

char :: Memo Char Source #

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 #

unit :: Memo () 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.