Hello all,
Inspired by exercise on the minimal value of a given list I tried
myself produce several versions of such a function:
exercise: using just ($), head, filter, null, id, map, (<) without
explicit recursion definition
direct-forward: direct implementation using forward recursion,
if-then-else, (<)
direct-backward: direct implementation using backward recursion,
if-then-else, (<)
foldl: using foldl, lambda abstraction, if-then-else, (<)
foldr: using foldr, lambda abstraction, if-then-else, (<)
From a recursion point of view, I see a similarity between
direct-forward and foldl. Of course, the same similarity is between
direct-backward and foldr. Am I right? If yes, then there is something
strange in the results I have gained (see below).
I did my measurements in winhugs (Version: Sep 2006) for lists of
length 10, 100, 1000 and 50 elements. I tested on list with the same
constant, list where the first number is minimal (these two cases are
from this point of view similar/the same), lists, where some element in
the "middle" is minimal, and finally lists, where the last element is
the minimal one. As for constant and first minimal element list I got
the same result, we can join them and have just three categories of
lists, let's call them first, mid, last.
Even if I know that using number of reductions and number of cells
does not provide exact results, I assume that impact of parameter and
printing of the result is the same for all tested functions and is
either constant for the result printing (always number 1 in the result)
and at most linear in the parameter processing (I would assume no direct
impact here, just algorithm influence, is that right?).
Thus, the results may be compared. First of all, the time/reduction
complexity (n is a length of the list):
first mid last
exercise 9n+34 <not evaluated> 4.5n^2+21.5n+17
direct-forward 7n+15 7n+15 7n+15
direct-backward 7n+15 7n+15 7n+15
foldl 8n+14 8n+14 8n+14
foldr 8n+14 8n+14 8n+14
There is nothing special on the results, the exercise solution was not
evaluated for the middle element lists as the position of the minimal
value in the list is a parameter of the function.
Now, let me show results for number of used cells:
first mid last
exercise 10n+54 <not evaluated> 5n^2+29n+26
direct-forward 8n+24 8n+25 9n+23
direct-backward 9n+22 9n+22 9n+22
foldl 11n+22 11n+22 11n+22
foldr 10n+23 10n+23 10n+23
Again, roughly looking at the results, there is nothing special, average
space complexity is as it may be expected. Looking at the exact
formulas, there are two things that come strange to me:
1) From a recursion point of view, there are pairs direct-forward ~
foldl and direct-backward ~ foldr. Nevertheless, from a space
consumption point of view, this doesn't hold and the pairs are swapped.
Why? Is this a winhugs specialty? Is this due to reduction strategy?
Laziness?
2) Direct-forward implementation provides three different formulas. Why?
Why the mid formula is fixed no matter where the minimal value is?
Thanks for any answers/hints/references. Especially, if this is RTFM
one. ;-)
Dusan
P.S.
I know, that sources may be helpful, but as this is an exercise I don't
want to provide them directly to the list. ;-) But I can provide them,
of course. :-)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
