<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:times new roman, new york, times, serif;font-size:12pt"><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;">Hi Atilla,<br><br>The point is that one needs to perform 'createArray' only once. Fib5_, and if I understood correctly, does that every time<br><br>...<br>Fib5 :: Int -> Int<br>Fib5 n<br>| n >= 0 =<br> let<br> (res, _) = Memoize Fib5_ n (createArray (n+1) 0)<br>more ...<br><br>This is: for every 'n', you are saying 'createArray (n+1) 0'. So, you are not using memoization at all. And probably Memoize
is calculating everything from scratch all the time...<br><br>That's
why I defined fibm = ... in the code at top level, so that way the
definition itself, I hoped, captured this. I know that in Clean there
are differences at the top level in the meaning of '='. Sometimes
recalculates, sometimes is a macro (calculated only once). If I
remember correctly, the way I did it is a macro definition and
therefore calculated only once.<br><br>cheers<br>Carlos<br><br><div style="font-family: arial,helvetica,sans-serif; font-size: 13px;">----- Original Message ----<br>Date: Tue, 21 Oct 2008 17:23:13 -0400 (EDT)<br>From: "Attila Ondi" <<a ymailto="mailto:aondi@fit.edu" href="mailto:aondi@fit.edu">aondi@fit.edu</a>><br>Subject: Re: [clean-list] Question on destructive array updates<br>To: <a ymailto="mailto:clean-list@science.ru.nl" href="mailto:clean-list@science.ru.nl">clean-list@science.ru.nl</a><br>Message-ID:<br> <<a ymailto="mailto:3217.163.118.203.36.1224624193.squirrel@webaccess.fit.edu" href="mailto:3217.163.118.203.36.1224624193.squirrel@webaccess.fit.edu">3217.163.118.203.36.1224624193.squirrel@webaccess.fit.edu</a>><br>Content-Type: text/plain;charset=iso-8859-1<br><br>More questions :)<br><br>I was playing around with Carlos's memoization implementation, especially<br>after I realized it will store only the result
of the topmost call (see f<br>n in his memo function). After a little fiddling, this is what I came up<br>with to store all intermediate values:<br><br>:: *ArrayTuple a :== (a, *{a})<br><br>Memoize :: (Int -> ((Int -> (*{Int} -> ArrayTuple Int)) -> (*{Int} -><br>ArrayTuple Int))) Int *{Int} -> ArrayTuple Int<br>Memoize f n a<br>| size a < n+1 = abort ("Memoize: Array is smaller than required (size: "<br>+++ (toString (size a)) +++ ", n: " +++ (toString n) +++ ")")<br>| a.[n] < 0 = abort ("Memoize: Invalid array value (n: " +++ (toString n)<br>+++ ", a[n]: " +++ (toString (a.[n])) +++ ")")<br>| a.[n] > 0 = a![n]<br># (res, resa) = f n (Memoize f) a<br>| otherwise = {resa&[n] = res}![n]<br><br>Fib5 :: Int -> Int<br>Fib5 n<br>| n >= 0 =<br> let<br> (res, _) = Memoize Fib5_ n (createArray (n+1) 0)<br><br> Fib5_ :: Int (Int
-> (*{Int} -> ArrayTuple Int)) *{Int} -> ArrayTuple Int<br> Fib5_ 0 _ a = (1, a)<br> Fib5_ 1 _ a = (1, a)<br> Fib5_ n g a<br> # (res1, resa1) = g (n-1) a<br> # (res2, resa2) = g (n-2) resa1<br> = (res1 + res2, resa2)<br> in res<br>| otherwise = abort ("Fib5: Called with negative parameter (n : " +++<br>(toString n) +++ ")")<br><br><br>As (obviously) the type of the function Memoize takes is the same as<br>Fib5_, I was trying to name that type:<br><br>:: MemoizeFun a :== a (a -> (*{a} -> ArrayTuple a)) *{a} -> ArrayTuple a<br>Memoize :: (MemoizeFun Int) Int *{Int} -> ArrayTuple Int<br>Fib5_ :: (MemoizeFun Int)<br><br>However, the compiler now treats Fib5_ as a constant. So my question
is,<br>is there a way to name the types of functions so I don't have to type the<br>full arrow and its two sides(*)?<br><br>(*) I know I don't _have_ to, but since I'm not that close to functional<br>programming yet, I like to see (and understand) what's going on.<br><br><br>Also, according to the profiler, the program spends the most time in<br>Memoize (compared to all other Fibonacci implementations of mine), which<br>is surprising to me as the implementation of Fib5 is practically the same<br>as my earlier attempt to use arrays (which was a specialized, interwoven<br>case of computation and memoization as Carlos pointed it out). So my<br>question is: what is the reason for this result?<br><br>Actually, upon measuring some re-run, the time spent in Memoize varies a<br>lot. Is this normal? I know lazy evaluation allows the compiler/runtime<br>to do some tricks, but I expected the performance to stay the same if<br>running without
recompilation. Could memory allocation be the reason?<br><br>Thank you,<br>Attila<br><br>******************************************<br></div></div></div><br>Send instant messages to your online friends http://au.messenger.yahoo.com </body></html>