[Haskell-cafe] List minimum - performance question

[Dusan Kolar]

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. :-)