+%options ghci -fglasgow-exts

+import Data.Maybe ( fromJust )

+\documentclass[a4paper,10pt]{article}

+\usepackage[pdftex]{graphicx}

+\usepackage[english]{babel}

+\usepackage{color,amsmath, verbatim, fullpage, parskip, url}

+\definecolor{syntax}{RGB}{0, 0, 100}

+\definecolor{datatype}{RGB}{196, 6, 11}

+\definecolor{class}{RGB}{168,37,39}

+\definecolor{fieldname}{RGB}{0,0,162}

+\definecolor{prelude}{RGB}{64,80,117}

+\definecolor{numeral}{RGB}{0,0,205}

+\definecolor{infixoperator}{RGB}{19, 19, 168}

+\definecolor{constructor}{RGB}{196, 6, 11}

+\definecolor{keyword}{RGB}{4, 58, 252}

+\definecolor{special1}{RGB}{159,138,0}

+\definecolor{string}{RGB}{3, 106, 7}

+\definecolor{char} {RGB}{3, 106, 7}

+\newcommand{\lhsCHsyntax}[1]{\color{syntax}{{#1}}}

+\newcommand{\lhsCHclass}[1]{\color{class}{{#1}}}

+\newcommand{\lhsCHfield}[1]{\color{fieldname}{{#1}}}

+\newcommand{\lhsCHfunction}[1]{\color{black}{{#1}}}

+\newcommand{\lhsCHinfixoperator}[1]{\color{infixoperator}{{#1}}}

+\newcommand{\lhsCHprelude}[1]{\color{prelude}{\mathbf{#1}}}

+\newcommand{\lhsCHkeyword}[1]{\color{keyword}{\textbf{#1}}}

+\newcommand{\lhsCHconstructor}[1]{\color{constructor}{\textbf{#1}}}

+\newcommand{\lhsCHlitNumber}[1]{\color{numeral}{{#1}}}

+\newcommand{\lhsCHtype}[1]{\color{datatype}{{#1}}}

+\def\thesubsection {\thesection.\alph{subsection})}

+%subst char a = "\color{char}\text{\tt ''" a "''}"

+%subst string a = "\color{string}\text{\tt \char34 " a "\char34}"

+%subst numeral a = "\color{numeral}{" a "}"

+I want to write a memoisation library which you can pass a function and that

+will return to you the memoised version of the function.

+What I want to do is the following:

+ \item Set up the library with |memo :: ((a -> b) -> a -> b) -> IO (a -> b)| first so that it accepts functions in fix-point-notation

+ \item Provide a way to get rid of IO.

+ \item Figure out which function types to support

+ \item Check whether the checking of equality is done breadth-first. (Would this work with just having a map where the key is the curried version of the arguments?)

+ \item I believe this can be done with unsafePerformIO but I'll have to prove

+ \item Compare my solution with the following papers

+ \item Fun with type functions, Oleg Kiselyov Simon Peyton Jones Chung-chieh Shan: \url{http://research.microsoft.com/en-us/um/people/simonpj/papers/assoc-types/fun-with-type-funs/typefun.pdf}

+ \item Stretching the storage manager: weak pointers and stable names in Haskell, SPJ, SM and Conal Elliot \url{http://community.haskell.org/~simonmar/papers/weak.pdf}

+ \item Memo functions, polytypically! - Ralf Hinze

+ \item Compare with sharing? Is memoisation really the same as sharing in the

+ sense that with sharing you `memo' address space and with memoisation

+ you remember the results of functions?

+ \item Built-in supoprt for UHC so that we can memoise functions that are not

+ written in fix-point notation.

+ \item Check whether the insertion of the memo-fix function causes

+ optimalisations to fail.

+How I came up with this idea is as follows:

+fac :: Integer -> Integer

+We have the well known fib function.

+fib x = fib (x-1) + fib (x-2)

+This is fib but with an extra parameter with which each result is multiplied.

+fibm m x = (fibm m (x-1) + fibm m (x-2)) * m

+The memoisation of fib. Straightforward. We use elements of the same type in the

+list as the parameter of the function. We then use the convenient |!!| to get

+the resulting value from the list. This only works in the case of |Int| type

+parameters. For |Integer| or |Bool| we would need to use |lookup| and store the

+values in a |(Key,Value)| pair.

+mfib = let memo = map (fib' mfib) [0..]

+ fib' :: (Int -> Int) -> Int -> Int

+ fib' f x = f (x-1) + f (x-2)

+The following code is derived from the previous example. It follows the same

+principles but now we store two integers in the list. However this does not work

+in this way as the list comprehension will first pick one |i| and then all other

+mfibm :: Int -> Int -> Int

+mfibm = let memo = map (\ (i,j) -> ((i,j), fib' mfibm i j)) [(i,j) | i <- [0..] , j <- [0..]]

+ fib' :: (Int -> Int -> Int) -> Int -> Int -> Int

+ fib' f m x = (f m (x-1) + f m (x-2)) * m

+ in \ m i -> fromJust (lookup (m,i) memo)

+To make this work I wrote the following code: Now we have a multidimensional

+list, essentially a table. I switched back to using |!!| again.

+mfibm_2 :: Int -> Int -> Int

+mfibm_2 = let memo :: [[Int]]

+ memo = map (\ (i, xs) -> map ( fib' mfibm_2 i ) xs)

+ [(i , [0..]) | i <- [0..]]

+ fib' :: (Int -> Int -> Int) -> Int -> Int -> Int

+ fib' f m x = (f m (x-1) + f m (x-2)) * m

+ in \ m i -> (memo !! m) !! i

+ \item The use of |!!| is limited to |Int| or |Integer|

+ \item The use of these nested lists is not nice for looking up the result. In

+ terms of performance it would rather quickly be `slow' to memoise when

+ you are using multiple parameters. Using a map is not desirable as maps

+ \item This method requires that you can enumerate over the datatypes of the

+ parameters. If you would have a lot of possibilities and you cannot use

+ |!!| as in the fib example as you don't have a mapping from input to

+ position in the list you would need to use |lookup|. This could be