<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>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 a![n], which does precisely what you want, returns a tuple with the value and the array for future use. So, if I understood what you wanted, the code ended like (omitting your other fib's, and I put 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 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></div><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;"><br><div style="font-family: arial,helvetica,sans-serif; font-size: 13px;">-------------------------------<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>><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><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>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><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></div></div></div><br>Send instant messages to your online friends http://au.messenger.yahoo.com </body></html>