[clean-list] Question on destructive array updates

[Attila Ondi]

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]
=================