[clean-list] Question on destructive array updates
Attila Ondi
aondi at fit.edu
Tue Oct 21 18:42:47 MEST 2008
Thanks so much for all!
I did not know about the a![n] notation before and that was the root of my
problem. Also, thanks Carlos for the generalized memoization function. I
might eventually have got there myself, but was on my mind yet :)
I think in your Start function below you will have to compute fib 7 twice
because you are operating on two different arrays: one created for fibm 7
and the other for fibm 10. Had you created a large enough array in the
beginning on which both fibm calls would then operate, fib 7 should be
computed only once (as far as I understand).
Interestingly, the destructive update in the Fibonacci case is only faster
than even the list traversal one (Fib2 of my functions) when n is larger
than about 15 (according to my profiler results).
My next goal is to understand and play with dynamics :)
Thanks,
Attila
> Dear Pieter,
>
>> the array elements will be updated too often.
>
> I thought that
> | a.[n] > 0 = a![n]
> in Fib3_ avoided that, asking first if one ever computed (f n) before. Of
> course only works for strictly positive f :: Int -> Int
>
>> using some accumulators the use of an array can be avoided (as Attila
>> pointed out):
>
> Sure, I think the exercise here is implementing memoization in Clean. No?
>
> 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)
>
> --------------------------------------------------
> module fib
>
> import StdEnv
>
> /* the general function */
> fib :: Int -> Int
> fib n
> | n <= 1 = 1
> | otherwise = fib (n - 1) + fib (n - 2)
>
> /* "general" memoization */
> memo :: *{Int} (Int -> Int) Int -> (Int, *{Int})
> memo a f n
> | size a < n = abort "n out of range"
> | a.[n] > 0 = a![n]
> = {a & [n] = (f n)}![n]
>
> /* this is our memoizated fib */
> memoFib = memo (createArray 100 0) fib
>
> /* and this shows my ignorance on how to select the second item in a tuple
> as I need this down there ;-) */
> sec (x, _) = x
>
> Start :: {Int}
> Start = {fibm 7, fibm 10}
> where
> fibm n = sec (memoFib n)
> --------------------------------------------------
>
>
> So, my claim is that in Start, fib 7 is computed only once. Is this right?
>
> By the way, is there any easy (ala unsafeIO or something) to check this in
> fib or its friends?
>
> cheers
> Carlos
>
>
> ----- Original Message ----
> From: Pieter Koopman <pieter at cs.ru.nl>
> To: Carlos Aya <carlosayam at yahoo.com.au>
> Cc: clean-list at science.ru.nl; Attila Ondi <aondi at fit.edu>
> Sent: Monday, 20 October, 2008 11:02:19 PM
> Subject: Re: [clean-list] Question on destructive array updates
>
> 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
>>
>
>
> Send instant messages to your online friends http://au.messenger.yahoo.com
More information about the clean-list
mailing list