news

The data-memocombinators package provides combinators for creating memo tables. It can build up data similar to a lookup table. It is now available in Fedora. Install it using:

\$ sudo yum install ghc-data-memocombinators-devel

The time and memory consumption for a command execution can be viewed in ghci by setting the following:

ghci> :set +s

Suppose we wish to apply memoization to the Fibonacci function:

import qualified Data.MemoCombinators as Memo

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

The 10,000th Fibonacci number using the fib function is returned in a much shorter time in the second attempt:

ghci> fib 10000
...
(0.15 secs, 87703888 bytes)

ghci> fib 10000
...
(0.03 secs, 9652144 bytes)

We can also specify a range for which the memoization is to be applied. In the following example, it is applied only for the numbers between 1 and 1000:

import qualified Data.MemoCombinators as Memo

fib2 = Memo.arrayRange (1, 1000) fib'
where
fib' 0 = 0
fib' 1 = 1
fib' x = fib2 (x-1) + fib2 (x-2)

Using fib2 to return the 1000th Fibonacci number, we observe the following:

ghci> fib2 1000
...
(0.04 secs, 10804024 bytes)

ghci> fib2 1000
...
(0.02 secs, 7384584 bytes)

The mulHundred function takes an integer list as an argument and muliplies each element in the list with 100. We want to tabulate the values for faster lookup using:

import qualified Data.MemoCombinators as Memo

mulHundred = (Memo.list Memo.integral) b
where
b [] = []
b (x:xs) = [100 * x]  ++ mulHundred xs

Running the mulHundred function in ghci:

ghci> mulHundred [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[100,200,300,400,500,600,700,800,900,1000]
(0.03 secs, 9592680 bytes)

ghci> mulHundred [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[100,200,300,400,500,600,700,800,900,1000]
(0.02 secs, 8426040 bytes)

We can also apply memoization for quicksort. For example:

import qualified Data.MemoCombinators as Memo

quicksort = (Memo.list Memo.integral) quicksort' where
quicksort' [] = []
quicksort' (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs

Subsequent sorting of the input is faster:

ghci> let input = [x | x <- [100, 99..1]]
(0.02 secs, 7895376 bytes)

ghci> quicksort input
[1,2,..100]
(0.04 secs, 19918312 bytes)

ghci> quicksort input
[1,2,..100]
(0.01 secs, 7925856 bytes)

If we would like to create a table of results for the AND operation, we could use Memo.bool:

import qualified Data.MemoCombinators as Memo

andGate = Memo.bool new
where
new x y = x && y

For example:

ghci> False && True
False
(0.02 secs, 8537120 bytes)

ghci> andGate False True
False
(0.02 secs, 8442648 bytes)

ghci> andGate False True
False
(0.01 secs, 7376560 bytes)