Alessandro Vermeulen avatar Alessandro Vermeulen committed 222757d

Initial commit with the plan :)

Comments (0)

Files changed (1)

+%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
+        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{}
+          \item Stretching the storage manager: weak pointers and stable names in Haskell, SPJ, SM and Conal Elliot \url{}
+          \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.
+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.
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
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.