Alessandro Vermeulen avatar Alessandro Vermeulen committed 222757d

Initial commit with the plan :)

Comments (0)

Files changed (1)

+%options ghci -fglasgow-exts
+%if False
+\begin{code}
+module Memo where
+
+import Data.Maybe ( fromJust )
+\end{code}
+%endif
+
+\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})}
+%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 "}"
+
+\begin{document}
+\section{Target}
+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:
+
+\begin{itemize}
+  \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
+        it.
+  \item Compare my solution with the following papers
+        \begin{itemize}
+          \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
+        \end{itemize}
+  \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.
+        
+\end{itemize}
+
+How I came up with this idea is as follows:
+  
+\begin{code}
+fac :: Integer -> Integer
+fac 0 = 1
+fac x = x * fac (x-1)
+\end{code}
+
+We have the well known fib function.
+\begin{code}
+fib 0 = 0
+fib 1 = 1
+fib x = fib (x-1) + fib (x-2)
+\end{code}
+
+This is fib but with an extra parameter with which each result is multiplied.
+\begin{code}
+fibm m 0 = 0
+fibm m 1 = m
+fibm m x = (fibm m (x-1) + fibm m (x-2)) * m
+
+\end{code}
+
+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.
+\begin{code}
+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  
+\end{code}
+
+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
+|j|s. 
+
+\begin{code}
+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)
+\end{code}
+
+To make this work I wrote the following code: Now we have a multidimensional
+list, essentially a table. I switched back to using |!!| again.
+
+\begin{code}
+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
+\end{code}
+
+\section{Observations}
+
+\begin{itemize}
+  \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.
+\end{itemize}
+
+\end{document}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.