[clean-list] Question on destructive array updates
Pieter Koopman
pieter at cs.ru.nl
Mon Oct 20 14:02:19 MEST 2008
Dear Carlos,
your code for Fib3 will work correctly, but due to the double recursions
the array elements will be updated too often. Hence the complexity will
be even bad as in a naive definition. This can be avoided by computing
from the low indices to the high ones.
fibArray :: !Int -> Int
fibArray n
| n<0 = abort ("fibArray not defined for argument "+++toString n)
= g 2 (createArray (n+1) 1)
where
g :: !Int *{#Int} -> Int
g i array
| i<=n
# (a,array) = array![i-1]
(b,array) = array![i-2]
= g (i+1) {array & [i]=a+b}
= array.[n]
using some accumulators the use of an array can be avoided (as Attila
pointed out):
fibAcc :: !Int -> Int
fibAcc n
| n<0 = abort ("fibAcc not defined for argument "+++toString n)
= f n 1 1
where
f :: !Int !Int !Int -> Int
f 0 a b = a
f n a b = f (n-1) b (a+b)
Have fun,
Pieter Koopman
Carlos Aya wrote:
> Hi Attila,
>
> It's been a while for me too... I tried your code and the problem is
>
> >>> a.[n] > 0 = (a.[n], a)
>
> 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 ...)
>
> ---
> module fib
>
> import StdEnv
>
> Fib3 :: Int -> Int
> Fib3 n
> | n < 0 = abort "Fib3: Called with negative parameter"
> | otherwise = res
> where
> (res, _) = Fib3_ n (createArray (n+1) 0)
>
> Fib3_ :: Int *{Int} -> (Int, *{Int})
> Fib3_ n a
> | size a < n = abort "cannot store fib(n) in a"
> | a.[n] > 0 = a![n]
> | n == 0 = {a & [0] = 1}![0]
> | n == 1 = {a & [1] = 1}![0]
> | otherwise
> # (res1, a) = Fib3_ (n-1) a
> # (res2, a) = Fib3_ (n-2) a
> = {a & [n] = res1 + res2}![n]
>
>
> Start :: Int
> Start = Fib3 7
> ---
>
> Note also the use of # to reuse the 'a' variable. So, it is unique in
> the 'otherwise' branch as well.
>
> This can be generalized to memorize any Int -> Int function, later...
>
> Hope this helps
>
> Carlos Aya
>
> -------------------------------
> Message: 1
> Date: Fri, 17 Oct 2008 15:02:25 -0400 (EDT)
> From: "Attila Ondi" <aondi at fit.edu <mailto:aondi at fit.edu>>
> Subject: [clean-list] Question on destructive array updates
> To: clean-list at science.ru.nl <mailto:clean-list at science.ru.nl>
> Message-ID:
> <3441.163.118.203.36.1224270145.squirrel at webaccess.fit.edu
> <mailto:3441.163.118.203.36.1224270145.squirrel at webaccess.fit.edu>>
> Content-Type: text/plain;charset=iso-8859-1
>
> Hi all,
>
> I was trying to refresh my knowledge in Clean and picked to implement the
> Fibonacci series. The obvious recursive implementation (Fib) was trivial
> and then I tried to move on to use some tricks to speed up the
> computation. The first idea was to use lists to store the already
> computed values (Fib2). This worked, but did not prove any faster
> (according to the profiler) mostly because of the many list traversals.
>
> Then I tried my hands using arrays as I remembered they provide constant
> access time to their elements and can also be updated destructively (to
> avoid re-creating an almost identical array). The resulting function
> (Fib3) is pretty similar to the one using lists (Fib2), but I cannot get
> it to compile (complaining about type coercion in the line "| a.[n] > 0 =
> (a.[n], a)" in the function Fib3_ "Uniqueness error: attribute at
> indicated position could not be coerced *(Int,^{u:Int})"). No matter what
> I tired (e.g. unnamed uniqueness type annotations, strict and/or unboxed
> elements), I could not get rid of the compiler error. All my efforts to
> find some explanation to the problem through web search were futile, so
> I'd like to ask the list a few questions:
>
> 1) Why does the compiler (just downloaded the latest 2.2) present me with
> an error when I don't reuse the array, only an element of it (or was
> trying to at least) -- shouldn't possible multiple references be handled
> properly by the runtime?
>
> 2) Can the calculation of the Fibonacci sequence be implemented with the
> use of a destructive array? If yes how (or how to fix my program) -- if
> not, why not?
>
>
> And finally, here is my program. It also includes a linear calculation of
> the Fibonacci numbers (Fib4) without using any array or list components
> (just accumulators) for completeness -- I hope my email client does not
> mess up the indentations too much.
>
> Thanks,
> Attila Ondi
>
>
> =================
> module Fibonacci
>
> import StdEnv
>
> Fib :: Int -> Int
> Fib 0 = 1
> Fib 1 = 1
> Fib n = Fib (n-1) + Fib (n-2)
>
>
> Fib2 :: Int -> Int
> Fib2 n
> | n < 0 = abort "Fib2: Called with negative parameter"
> | otherwise =
> let
> (res, _) = Fib2_ n []
>
> Fib2_ :: Int [Int] -> (Int, [Int])
> Fib2_ 0 l=:[x0 : xs] = (x0, l)
> Fib2_ 0 _ = (1, [1])
> Fib2_ 1 l=:[x0, x1 : xs] = (x1, l)
> Fib2_ 1 _ = (1, [1, 1])
> Fib2_ n l
> | length l >= n+1 =
> let
> nth :: Int [Int] -> Int
> nth 0 [x : _] = x
> nth n [_ : xs] = nth (n-1) xs
> nth _ [] = abort "nth: Not enough elements in list"
> in (nth n l, l)
> | otherwise =
> let
> (res1, resl1) = Fib2_ (n-2) l
> (res2, resl2) = Fib2_ (n-1) resl1
> in (res1 + res2, resl2)
> in res
>
>
> Fib3 :: Int -> Int
> Fib3 n
> | n < 0 = abort "Fib3: Called with negative parameter"
> | otherwise =
> let
> (res, _) = Fib3_ n (createArray n 0)
>
> Fib3_ :: Int *{Int} -> (Int, *{Int})
> Fib3_ n a
> | size a < n+1 = abort "Fib3_: Array is smaller than required"
> | a.[n] < 0 = abort "Fib3_: Invalid array value"
> | a.[n] > 0 = (a.[n], a)
> | otherwise =
> let
> (res1, resa1) = Fib3_ (n-1) a
> (res2, resa2) = Fib3_ (n-2) resa1
> in (res1 + res2, resa2)
> in res
>
>
> Fib4 :: Int -> Int
> Fib4 n
> | n < 0 = abort "Fib4: Called with negative parameter"
> | otherwise =
> let
> (_, _, res) = Fib4_ n 1 1
>
> Fib4_ :: Int Int Int -> (Int, Int, Int)
> Fib4_ 0 tmp _ = (0, 0, tmp)
> Fib4_ 1 _ acc = (0, 0, acc)
> Fib4_ n tmp acc
> | otherwise = Fib4_ (n-1) acc (acc + tmp)
> in res
>
> Start :: [Int]
> Start = [Fib 7, Fib2 7, Fib3 7, Fib4 7]
> =================
>
>
>
>
> ------------------------------
>
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl <mailto:clean-list at science.ru.nl>
> http://mailman.science.ru.nl/mailman/listinfo/clean-list
>
>
> End of clean-list Digest, Vol 47, Issue 10
> ******************************************
>
> Send instant messages to your online friends
> http://au.messenger.yahoo.com
> ------------------------------------------------------------------------
>
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl
> http://mailman.science.ru.nl/mailman/listinfo/clean-list
>
More information about the clean-list
mailing list