<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>Dear Pieter,<br><br>> the array elements will be updated too often.<br><br>I thought that <br> | a.[n] > 0 = a![n]<br>in Fib3_ avoided that, asking first if one ever computed (f n) before. Of course only works for strictly positive f :: Int -> Int<br><br>> using some accumulators the use of an array can be avoided (as Attila <br>> pointed out):<br><br>Sure, I think the exercise here is implementing memoization in Clean. No?<br><br>Actualy, this is what I think is a "general" memoization technique in Clean. (general in quotes because it only works for strictly positive Int->Int)<br><br>--------------------------------------------------<br>module fib<br><br>import StdEnv<br><br>/* the general function */<br>fib :: Int -> Int<br>fib n
<br> | n <= 1 = 1<br> | otherwise = fib (n - 1) + fib (n - 2)<br><br>/* "general" memoization */ <br>memo :: *{Int} (Int -> Int) Int -> (Int, *{Int})<br>memo a f n<br> | size a < n = abort "n out of range"<br> | a.[n] > 0 = a![n]<br> = {a & [n] = (f n)}![n] <br><br>/* this is our memoizated fib */<br>memoFib = memo (createArray 100 0) fib<br><br>/* and this shows my ignorance on how to select the second item in a tuple as I need this down there ;-) */<br>sec (x, _) = x<br><br>Start :: {Int}<br>Start = {fibm 7, fibm 10}<br> where<br> fibm n = sec (memoFib n)<br>--------------------------------------------------<br></div><div
style="font-family: times new roman,new york,times,serif; font-size: 12pt;"><br>So, my claim is that in Start, fib 7 is computed only once. Is this right? <br><br>By the way, is there any easy (ala unsafeIO or something) to check this in fib or its friends?<br><br>cheers<br>Carlos<br><br><div style="font-family: arial,helvetica,sans-serif; font-size: 13px;">----- Original Message ----<br>From: Pieter Koopman <pieter@cs.ru.nl><br>To: Carlos Aya <carlosayam@yahoo.com.au><br>Cc: clean-list@science.ru.nl; Attila Ondi <aondi@fit.edu><br>Sent: Monday, 20 October, 2008 11:02:19 PM<br>Subject: Re: [clean-list] Question on destructive array updates<br><br>Dear Carlos,<br><br>your code for Fib3 will work correctly, but due to the double recursions <br>the array elements will be updated too often. Hence the complexity will <br>be even bad as in a naive definition. This can be avoided by computing <br>from the low indices to the high
ones.<br><br>fibArray :: !Int -> Int<br>fibArray n<br> | n<0 = abort ("fibArray not defined for argument "+++toString n)<br> = g 2 (createArray (n+1) 1)<br>where<br> g :: !Int *{#Int} -> Int<br> g i array<br> | i<=n<br> # (a,array) = array![i-1]<br> (b,array) = array![i-2]<br> = g (i+1) {array & [i]=a+b}<br> = array.[n]<br><br>using some accumulators the use of an array can be avoided (as Attila <br>pointed out):<br><br>fibAcc :: !Int -> Int<br>fibAcc n<br> | n<0 = abort ("fibAcc not defined for argument "+++toString n)<br> = f n 1 1<br>where<br> f :: !Int !Int !Int -> Int<br> f 0 a b = a<br> f n a b = f (n-1) b (a+b)<br><br>Have fun,<br><br>Pieter Koopman<br><br>Carlos Aya
wrote:<br>> Hi Attila,<br>><br>> It's been a while for me too... I tried your code and the problem is<br>><br>> >>> a.[n] > 0 = (a.[n], a)<br>><br>> There are two uses of 'a' on the RHS. Fortunately, Clean comes with <br>> a![n], which does precisely what you want, returns a tuple with the <br>> value and the array for future use. So, if I understood what you <br>> wanted, the code ended like (omitting your other fib's, and I put <br>> Fib3_ top level ...)<br>><br>> ---<br>> module fib<br>><br>> import StdEnv<br>><br>> Fib3 :: Int -> Int<br>> Fib3 n<br>> | n < 0 = abort "Fib3: Called with negative parameter"<br>> | otherwise = res<br>> where<br>> (res, _) = Fib3_ n (createArray (n+1) 0)<br>><br>> Fib3_ :: Int *{Int} -> (Int, *{Int})<br>> Fib3_ n a<br>> | size a < n
= abort "cannot store fib(n) in a"<br>> | a.[n] > 0 = a![n]<br>> | n == 0 = {a & [0] = 1}![0]<br>> | n == 1 = {a & [1] = 1}![0]<br>> | otherwise<br>> # (res1, a) = Fib3_ (n-1) a<br>> # (res2, a) = Fib3_ (n-2) a<br>> = {a & [n] = res1 + res2}![n]<br>><br>><br>> Start :: Int<br>> Start = Fib3 7<br>> ---<br>><br>> Note also the use of # to reuse the 'a' variable. So, it is unique in <br>> the 'otherwise' branch as well.<br>><br>> This can be generalized to memorize any Int -> Int function, later...<br>><br>> Hope this helps<br>><br>> Carlos Aya<br>><br>>
-------------------------------<br>> Message: 1<br>> Date: Fri, 17 Oct 2008 15:02:25 -0400 (EDT)<br>> From: "Attila Ondi" <<a ymailto="mailto:aondi@fit.edu" href="mailto:aondi@fit.edu">aondi@fit.edu</a> <mailto:<a ymailto="mailto:aondi@fit.edu" href="mailto:aondi@fit.edu">aondi@fit.edu</a>>><br>> Subject: [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> <mailto:<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:3441.163.118.203.36.1224270145.squirrel@webaccess.fit.edu" href="mailto:3441.163.118.203.36.1224270145.squirrel@webaccess.fit.edu">3441.163.118.203.36.1224270145.squirrel@webaccess.fit.edu</a> <br>> <mailto:<a
ymailto="mailto:3441.163.118.203.36.1224270145.squirrel@webaccess.fit.edu" href="mailto:3441.163.118.203.36.1224270145.squirrel@webaccess.fit.edu">3441.163.118.203.36.1224270145.squirrel@webaccess.fit.edu</a>>><br>> Content-Type: text/plain;charset=iso-8859-1<br>><br>> Hi all,<br>><br>> I was trying to refresh my knowledge in Clean and picked to implement the<br>> Fibonacci series. The obvious recursive implementation (Fib) was trivial<br>> and then I tried to move on to use some tricks to speed up the<br>> computation. The first idea was to use lists to store the already<br>> computed values (Fib2). This worked, but did not prove any faster<br>> (according to the profiler) mostly because of the many list traversals.<br>><br>> Then I tried my hands using arrays as I remembered they provide constant<br>> access time to their elements and can also be updated destructively (to<br>> avoid
re-creating an almost identical array). The resulting function<br>> (Fib3) is pretty similar to the one using lists (Fib2), but I cannot get<br>> it to compile (complaining about type coercion in the line "| a.[n] > 0 =<br>> (a.[n], a)" in the function Fib3_ "Uniqueness error: attribute at<br>> indicated position could not be coerced *(Int,^{u:Int})"). No matter what<br>> I tired (e.g. unnamed uniqueness type annotations, strict and/or unboxed<br>> elements), I could not get rid of the compiler error. All my efforts to<br>> find some explanation to the problem through web search were futile, so<br>> I'd like to ask the list a few questions:<br>><br>> 1) Why does the compiler (just downloaded the latest 2.2) present me with<br>> an error when I don't reuse the array, only an element of it (or was<br>> trying to at least) -- shouldn't possible multiple references be handled<br>> properly by
the runtime?<br>><br>> 2) Can the calculation of the Fibonacci sequence be implemented with the<br>> use of a destructive array? If yes how (or how to fix my program) -- if<br>> not, why not?<br>><br>><br>> And finally, here is my program. It also includes a linear calculation of<br>> the Fibonacci numbers (Fib4) without using any array or list components<br>> (just accumulators) for completeness -- I hope my email client does not<br>> mess up the indentations too much.<br>><br>> Thanks,<br>> Attila Ondi<br>><br>><br>> =================<br>> module Fibonacci<br>><br>> import StdEnv<br>><br>> Fib :: Int -> Int<br>> Fib 0 = 1<br>> Fib 1 = 1<br>> Fib n = Fib (n-1) + Fib (n-2)<br>><br>><br>> Fib2 :: Int -> Int<br>> Fib2 n<br>> | n < 0 = abort "Fib2: Called with negative parameter"<br>> | otherwise =<br>> let<br>>
(res, _) = Fib2_ n []<br>><br>> Fib2_ :: Int [Int] -> (Int, [Int])<br>> Fib2_ 0 l=:[x0 : xs] = (x0, l)<br>> Fib2_ 0 _ = (1, [1])<br>> Fib2_ 1 l=:[x0, x1 : xs] = (x1, l)<br>> Fib2_ 1 _ = (1, [1, 1])<br>> Fib2_ n l<br>> | length l >= n+1 =<br>> let<br>> nth :: Int [Int] -> Int<br>> nth 0 [x : _] = x<br>> nth n [_ : xs] = nth (n-1) xs<br>> nth _ [] = abort "nth: Not enough elements in list"<br>>
in (nth n l, l)<br>> | otherwise =<br>> let<br>> (res1, resl1) = Fib2_ (n-2) l<br>> (res2, resl2) = Fib2_ (n-1) resl1<br>> in (res1 + res2, resl2)<br>> in res<br>><br>><br>> Fib3 :: Int -> Int<br>> Fib3 n<br>> | n < 0 = abort "Fib3: Called with negative parameter"<br>> | otherwise =<br>> let<br>> (res, _) = Fib3_ n (createArray n 0)<br>><br>> Fib3_ :: Int *{Int} -> (Int, *{Int})<br>> Fib3_ n a<br>> | size a < n+1 = abort "Fib3_: Array is smaller than required"<br>> | a.[n] < 0 = abort "Fib3_:
Invalid array value"<br>> | a.[n] > 0 = (a.[n], a)<br>> | otherwise =<br>> let<br>> (res1, resa1) = Fib3_ (n-1) a<br>> (res2, resa2) = Fib3_ (n-2) resa1<br>> in (res1 + res2, resa2)<br>> in res<br>><br>><br>> Fib4 :: Int -> Int<br>> Fib4 n<br>> | n < 0 = abort "Fib4: Called with negative parameter"<br>> | otherwise =<br>> let<br>> (_, _, res) = Fib4_ n 1 1<br>><br>> Fib4_ :: Int Int Int -> (Int, Int, Int)<br>> Fib4_ 0 tmp _ = (0, 0, tmp)<br>> Fib4_ 1 _ acc = (0, 0, acc)<br>>
Fib4_ n tmp acc<br>> | otherwise = Fib4_ (n-1) acc (acc + tmp)<br>> in res<br>><br>> Start :: [Int]<br>> Start = [Fib 7, Fib2 7, Fib3 7, Fib4 7]<br>> =================<br>><br>><br>><br>><br>> ------------------------------<br>><br>> _______________________________________________<br>> clean-list mailing list<br>> <a ymailto="mailto:clean-list@science.ru.nl" href="mailto:clean-list@science.ru.nl">clean-list@science.ru.nl</a> <mailto:<a ymailto="mailto:clean-list@science.ru.nl" href="mailto:clean-list@science.ru.nl">clean-list@science.ru.nl</a>><br>> <a href="http://mailman.science.ru.nl/mailman/listinfo/clean-list" target="_blank">http://mailman.science.ru.nl/mailman/listinfo/clean-list</a><br>><br>><br>> End of clean-list Digest, Vol 47, Issue 10<br>> ******************************************<br>><br>> Send instant messages to your
online friends <br>> <a href="http://au.messenger.yahoo.com" target="_blank">http://au.messenger.yahoo.com</a><br>> ------------------------------------------------------------------------<br>><br>> _______________________________________________<br>> clean-list mailing list<br>> <a ymailto="mailto:clean-list@science.ru.nl" href="mailto:clean-list@science.ru.nl">clean-list@science.ru.nl</a><br>> <a href="http://mailman.science.ru.nl/mailman/listinfo/clean-list" target="_blank">http://mailman.science.ru.nl/mailman/listinfo/clean-list</a><br>> <br></div></div></div><br>Send instant messages to your online friends http://au.messenger.yahoo.com </body></html>