[clean-list] Question on destructive array updates

Attila Ondi aondi at fit.edu
Tue Oct 21 23:23:13 MEST 2008


More questions :)

I was playing around with Carlos's memoization implementation, especially
after I realized it will store only the result of the topmost call (see f
n in his memo function).  After a little fiddling, this is what I came up
with to store all intermediate values:

:: *ArrayTuple a :== (a, *{a})

Memoize :: (Int -> ((Int -> (*{Int} -> ArrayTuple Int)) -> (*{Int} ->
ArrayTuple Int))) Int *{Int} -> ArrayTuple Int
Memoize f n a
| size a < n+1 = abort ("Memoize: Array is smaller than required (size: "
+++ (toString (size a)) +++ ", n: " +++ (toString n) +++ ")")
| a.[n] < 0 = abort ("Memoize: Invalid array value (n: " +++ (toString n)
+++ ", a[n]: " +++ (toString (a.[n])) +++ ")")
| a.[n] > 0 = a![n]
# (res, resa) = f n (Memoize f) a
| otherwise = {resa&[n] = res}![n]

Fib5 :: Int -> Int
Fib5 n
| n >= 0 =
	let
		(res, _) = Memoize Fib5_ n (createArray (n+1) 0)

		Fib5_ :: Int (Int -> (*{Int} -> ArrayTuple Int)) *{Int} -> ArrayTuple Int
		Fib5_ 0 _ a = (1, a)
		Fib5_ 1 _ a = (1, a)
		Fib5_ n g a
		# (res1, resa1) = g (n-1) a
		# (res2, resa2) = g (n-2) resa1
		= (res1 + res2, resa2)
	in res
| otherwise = abort ("Fib5: Called with negative parameter (n : " +++
(toString n) +++ ")")


As (obviously) the type of the function Memoize takes is the same as
Fib5_, I was trying to name that type:

:: MemoizeFun a :== a (a -> (*{a} -> ArrayTuple a)) *{a} -> ArrayTuple a
Memoize :: (MemoizeFun Int) Int *{Int} -> ArrayTuple Int
Fib5_ :: (MemoizeFun Int)

However, the compiler now treats Fib5_ as a constant.  So my question is,
is there a way to name the types of functions so I don't have to type the
full arrow and its two sides(*)?

(*) I know I don't _have_ to, but since I'm not that close to functional
programming yet, I like to see (and understand) what's going on.


Also, according to the profiler, the program spends the most time in
Memoize (compared to all other Fibonacci implementations of mine), which
is surprising to me as the implementation of Fib5 is practically the same
as my earlier attempt to use arrays (which was a specialized, interwoven
case of computation and memoization as Carlos pointed it out).  So my
question is: what is the reason for this result?

Actually, upon measuring some re-run, the time spent in Memoize varies a
lot.  Is this normal?  I know lazy evaluation allows the compiler/runtime
to do some tricks, but I expected the performance to stay the same if
running without recompilation.  Could memory allocation be the reason?

Thank you,
Attila

> 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
>
>
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl
> http://mailman.science.ru.nl/mailman/listinfo/clean-list
>
>




More information about the clean-list mailing list