[clean-list] Question on destructive array updates
Carlos Aya
carlosayam at yahoo.com.au
Mon Oct 20 20:03:34 MEST 2008
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.science.ru.nl/pipermail/clean-list/attachments/20081020/6f0c8a7d/attachment-0001.html
More information about the clean-list
mailing list