xp.memo / plan / memo.lhs

%options ghci -fglasgow-exts
%if False
module Memo where

import Data.Maybe ( fromJust )

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

\definecolor{syntax}{RGB}{0, 0, 100}
\definecolor{datatype}{RGB}{196, 6, 11}
\definecolor{infixoperator}{RGB}{19, 19, 168}
\definecolor{constructor}{RGB}{196, 6, 11}
\definecolor{keyword}{RGB}{4, 58, 252}
\definecolor{string}{RGB}{3, 106, 7}
\definecolor{char}  {RGB}{3, 106, 7}


\def\thesubsection       {\thesection.\alph{subsection})}
%include polycode.fmt 
%include colorcode.fmt
%include memo.fmt

%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{}
          \item Stretching the storage manager: weak pointers and stable names in Haskell, SPJ, SM and Conal Elliot \url{}
          \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
fac 0 = 1
fac x = x * fac (x-1)

We have the well known fib function.
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)

This is fib but with an extra parameter with which each result is multiplied.
fibm m 0 = 0
fibm m 1 = m
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  ::  Int -> Int
mfib  =   let  memo = map (fib' mfib) [0..]
               fib' :: (Int -> Int) -> Int -> Int
               fib' f 0 = 0
               fib' f 1 = 1
               fib' f x = f (x-1) + f (x-2)
          in   \ i -> memo !! i  

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 0 = 0
                  fib' f m 1 = m
                  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 0 = 0
                  fib' f m 1 = m
                  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
        should be finite.
  \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
        potentially very slow.