Beginner's question: Memo functions in Haskell
Hello, In a machine learning application I am currently playing with string kernels which are recursively defined functions operating on strings. In Haskell the implementation of these functions is very pleasing as it is a one-to-one translation of the mathematical definition (see code below [2] and reference [1], p.424). However, the runtime performance is less pleasing as certain subexpressions are computed over and over again (profiling with ghc showed that the function k' (see code below) is called 1425291 times in a toy example). In a non-functional implementation I would now set up an auxillary data structure (e.g. a hash table) for caching/memorizing some intermediate results. How would this be done (elegantly, efficiently, by a Haskell-beginner) in Haskell? So far, I have seen code using lists to speed up fib(n). In my case the arguments of k' are Int -> String -> String, and I don't expect a simple list of tuples (Int, String, String, RESULT) to be efficient. Thank you very much for you help, Matthias [1] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, Chris Watkins: "Text Classification using String Kernels", Journal of Machine Learning Research, 2(Feb):419-444, 2002. Available online at http://www.ai.mit.edu/projects/jmlr/papers/volume2.html [2] My code (actually the first 'real' piece of code I wrote in Haskell) is the following: ------------------------------------------------------------ module SKernel where k' :: Double -> Int -> String -> String -> Double k' lambda 0 s t = 1 k' lambda i s t = if min (length s) (length t) < i then 0 else (lambda * (k' lambda i s' t)) + sum [ lambda^((length t) - j + 2) * (k' lambda (i-1) s' t') | j <- [1..length t], t!!(j-1) == last s, t' <- [take (j-1) t] ] where s' = take ((length s) - 1) s k :: Double -> Int -> String -> String -> Double k lambda i s t = if min (length s) (length t) < i then 0 else k lambda i s' t + sum [ lambda^2 * (k' lambda (i-1) s' t') | j <- [1..length t], t!!(j-1) == last s, t' <- [take (j-1) t] ] where s' = take ((length s) - 1) s nk :: Double -> Int -> String -> String -> Double nk lambda n s t = (k lambda n s t) / sqrt ((k lambda n s s) * (k lambda n t t)) -- a toy example would be the call nk 0.5 5 "This is a string." "Here we have another string." ------------------------------------------------------------
Hallo Matthias,
However, the runtime performance is less pleasing as certain subexpressions are computed over and over again
There is a Memo module included with Hugs. I justed (profiling with ghc
showed that the function k' (see code below) is called 1425291 times in a toy example).
In a non-functional implementation I would now set up an auxillary data structure (e.g. a hash table) for caching/memorizing some intermediate results. How would this be done (elegantly, efficiently, by a Haskell-beginner) in Haskell?
So far, I have seen code using lists to speed up fib(n). In my case the arguments of k' are Int -> String -> String, and I don't expect a simple list of tuples (Int, String, String, RESULT) to be efficient.
Thank you very much for you help,
Matthias
[1] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, Chris Watkins: "Text Classification using String Kernels", Journal of Machine Learning Research, 2(Feb):419-444, 2002. Available online at http://www.ai.mit.edu/projects/jmlr/papers/volume2.html
[2] My code (actually the first 'real' piece of code I wrote in Haskell) is the following:
------------------------------------------------------------ module SKernel where
k' :: Double -> Int -> String -> String -> Double k' lambda 0 s t = 1 k' lambda i s t = if min (length s) (length t) < i then 0 else (lambda * (k' lambda i s' t)) + sum [ lambda^((length t) - j + 2) * (k' lambda (i-1) s' t') | j <- [1..length t], t!!(j-1) == last s, t' <- [take (j-1) t] ] where s' = take ((length s) - 1) s
k :: Double -> Int -> String -> String -> Double k lambda i s t = if min (length s) (length t) < i then 0 else k lambda i s' t + sum [ lambda^2 * (k' lambda (i-1) s' t') | j <- [1..length t], t!!(j-1) == last s, t' <- [take (j-1) t] ] where s' = take ((length s) - 1) s
nk :: Double -> Int -> String -> String -> Double nk lambda n s t = (k lambda n s t) / sqrt ((k lambda n s s) * (k lambda n t t))
-- a toy example would be the call nk 0.5 5 "This is a string." "Here we have another string." ------------------------------------------------------------
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Oops, previous message left too soon
However, the runtime performance is less pleasing as certain subexpressions are computed over and over again (profiling with ghc
There is a Memo module in Hugs, which I just used for fib. It doesn't seem to speed it up, though: -- module Fib where import Memo slow 0 = 0 slow 1 = 1 slow n = slow (n-1) + slow (n-2) fast n = memo slow n -- Maybe I'm doing something wrong. If it would work, it might be useful for your function, too. Arjan
"Arjan van IJzendoorn" <afie@cs.uu.nl> writes:
There is a Memo module in Hugs, which I just used for fib. It doesn't seem to speed it up, though:
You need to call the memoised version in the recursive case.
module Fib where
import Memo
slow 0 = 0 slow 1 = 1 slow n = slow (n-1) + slow (n-2)
slow n = fast (n-1) + fast (n-2)
fast n = memo slow n
Regards, Malcolm
Malcolm Wallace wrote:
You need to call the memoised version in the recursive case.
module Fib where
import Memo
slow 0 = 0 slow 1 = 1 slow n = slow (n-1) + slow (n-2)
slow n = fast (n-1) + fast (n-2)
fast n = memo slow n
It would also seem that one needs to write fast = memo slow instead, because otherwise a new memo-version of slow might be created for every call with some n (subject to let-floating?). However, the version: module Fib where import Memo slow 0 = 0 slow 1 = 1 slow n = fast (n-1) + fast (n-2) fast = memo slow is not particularly fast easier. Quite in contrary... strange. Janis. -- Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de
Janis Voigtlaender wrote:
It would also seem that one needs to write
fast = memo slow
instead, because otherwise a new memo-version of slow might be created for every call with some n (subject to let-floating?). However, the version:
module Fib where
import Memo
slow 0 = 0 slow 1 = 1 slow n = fast (n-1) + fast (n-2)
fast = memo slow
is not particularly fast easier. Quite in contrary... strange.
Janis.
It works under hugs98, but not under ghc5.02.2, I CC'd the ghc bugs list. Actually, I was also expecting "fast n = memo slow n" to work ? Jan
| Actually, I was also expecting "fast n = memo slow n" | to work ? In most lazy implementations, the idea is that sharing only occurs between computations with the same name. A computation declaration always has the form: x = ... So, if you want sharing to occur between different uses of a function f, you have to define f as follows (even if it is a function): f = ... If you however declare f as follows: f x = (...) x This means (in most implementations) that the expression (...) will be evaluated every time the function f is called with an argument. To understand memo better, we can make a special version of memo that only works on booleans: memo :: (Bool -> b) -> (Bool -> b) memo f = let fTrue = f True fFalse = f False in \x -> if x then fTrue else fFalse We can see now that the computations "fTrue" and "fFalse" are shared between calls to "memo f". So when we define: expensive b = <some very expensive thing> f = memo expensive f' b = memo expensive b We can see that "memo expensive" is reused between different calls of "f", and therefore are "expensive True" and "expensive False" remembered. We can also see that "memo expensive" is recomputed between calls of "f'", so the introduction of the memo function has no effect. /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen Chalmers University, Gothenburg, Sweden.
participants (6)
-
Arjan van IJzendoorn -
Jan Kort -
Janis Voigtlaender -
Koen Claessen -
Malcolm Wallace -
Matthias Heiler