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