Darren New wrote:

> Which is what I was suggesting be done with Haskell, when I said "write 
> a more iterative version".

Yeah, if it bothers you that much, you could manually say something like

   my_fold fn x0 i0 i1 list
     | x0 > 0 = my_fold fn x0 (i0-1) (i1-1) (tail list)
     | x1 > 0 = fn (head list) (my_fold fn x0 0 (i1-1) (tail list))
     | otherwise = x0

while will skip over list elements until i0 counts down to 0, then it 
starts folding until i1 counts down to zero, then it stops.

> If you don't want to copy the list, don't separate 
> out the function of copying the subset from the function of applying the 
> operator. (I don't know, Haskell might even be smart enough to lazily do 
> the Right Thing there even if you do it naively.)

In Haskell, writing

   list_function_1 . list_function_2 . list_function_3

is an extremely common idiom, and one which the compiler is designed to 
handle well. GHC has had produce/consume fusion for years, but now 
there's the stream-fusion library, which does even better:

   http://www.cse.unsw.edu.au/~dons/papers/CLS07.html

The fundamental idea is to take list-processing functions, remove the 
recursive part, let the compiler inline like hell, wrap the recursion 
around it, and you end up with something like a single for-loop with all 
the work inside it. No copying involved. (And if the thing that produces 
the list can be fused, the list might not actually exist in memory at 
all. It might be kept in CPU registers. Depending on type, obviously.)

Post a reply to this message