[clean-list] Question on destructive array updates

[Carlos Aya]

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>
Subject: [clean-list] Question on destructive array updates
To: clean-list at science.ru.nl
Message-ID:
    <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
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 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.science.ru.nl/pipermail/clean-list/attachments/20081018/442f9e3b/attachment.html