[clean-list] Question on destructive array updates
Pieter Koopman
pieter at cs.ru.nl
Tue Oct 21 13:59:31 MEST 2008
Dear Carlos,
you are completely right. Here you check if the value is computed and
prevent a new calculation if it is computed.
Sorry, Pieter
Carlos Aya wrote:
> 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>
> <mailto: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>
> <mailto: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>
> > <mailto: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>
> <mailto: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 <mailto: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