Warp wrote:

>   Or I could simply make an overloaded version of the fold function which
> takes an iterator range.

Now what happens if you want to only process elements having some 
arbitrary property? (E.g., only the odd numbers.) Or what if the 
function you're trying to fold is non-associative, and you want to 
rearrange the list so the elements can be processed in a different order?

The idea behind Haskell's data processing function is that each function 
does *one* job, which makes it possible to combine them in any possible 
way. (This is not unlike the Unix idea of implementing complex 
functionallity by "piping" data between multiple simple utility 
programs, as seen in millions of shell scripts.) As soon as you start 
trying to rely on particular pre-combined functions, you lose that 
flexibility.

With lists in particular, the new stream-fusion library means that most 
if not all common combinations of list processing functions get 
automatically fused together by the compiler.

There used to be a function called "concatMap", which does the same 
thing as "concat . map", but more efficiently. It's actually still there 
for compatibility, but with stream fusion you don't actually need it any 
more [because "concat . map" gets optimised into the same thing].

If you really need killer performance on a critical region of your 
program... well actually, in that case you probably wouldn't be using 
lists anyway, but still... if you really need killer performance 
somewhere, you can manually fuse if the compiler somehow fails to do it 
for you. But otherwise, the code is much more maintainable if you don't.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Warp wrote:

> >   Or I could simply make an overloaded version of the fold function which
> > takes an iterator range.

> Now what happens if you want to only process elements having some 
> arbitrary property? (E.g., only the odd numbers.)

  I make the function take a functor which tells which elements to process.
This is a standard technique in C++.

> Or what if the 
> function you're trying to fold is non-associative, and you want to 
> rearrange the list so the elements can be processed in a different order?

  Then rearrange the list as you like and give it to the function?

> If you really need killer performance on a critical region of your 
> program... well actually, in that case you probably wouldn't be using 
> lists anyway, but still...

  There are algorithms for which linked lists are the most efficient
data container. You still don't want to be needlessly copying the elements
around, though.

-- 
                                                          - Warp

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> I can certainly see why the standard doesn't mandate anything either 
> way. Do you happen to know the "typical" behaviour of any well-known C++ 
> compilers? (Presumably it varies depending on the optimisation level you 
> select...)

  Compilers use some kind of heuristic to determine whether it's beneficial
to inline some function or not. What those heuristics are, I don't know.

  From the programmer's point of view, it doesn't really matter. The program
will behave identically in either case (except maybe a small difference in
execution speed).

-- 
                                                          - Warp

Post a reply to this message

>> Now what happens if you want to only process elements having some 
>> arbitrary property? (E.g., only the odd numbers.)
> 
>   I make the function take a functor which tells which elements to process.
> This is a standard technique in C++.

Right. And now what if the elements to process depends on the 
surrounding context and you have to make several passes of the list to 
identify them?

We're missing my point though. My point is that you can't write a 
specialised implementation for every possible combination of list 
processing operations. But with stream fusion, the compiler can generate 
those for you - and yet the source code stays easily readable and 
modifiably.

>   There are algorithms for which linked lists are the most efficient
> data container. You still don't want to be needlessly copying the elements
> around, though.

Agreed.

This is why people have spent years doing research and coming up with 
sophisticated optimisation techniques. :-)

Post a reply to this message

Warp wrote:

>   Compilers use some kind of heuristic to determine whether it's beneficial
> to inline some function or not. What those heuristics are, I don't know.
> 
>   From the programmer's point of view, it doesn't really matter. The program
> will behave identically in either case (except maybe a small difference in
> execution speed).

Right. Well I guess that more or less answers my question. I was just a 
little worried that maybe if you don't explicitly say "inline", the 
compiler will never attempt to inline it and hence introduce way too 
much overhead. It seems that's not the case...

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> fold goes from yadda.begin() to yadda.end(). If you don't want to do 
>> that, use a different function. Or write it more iteratively, so to 
>> speak. Think about your C++ implementation of fold - you would have to 
>> copy the list there too if you wanted to use that on a subset.
> 
>   Or I could simply make an overloaded version of the fold function which
> takes an iterator range.

Which is what I was suggesting be done with Haskell, when I said "write 
a more iterative version". Pass in a start index and a length, walk down 
the list "start" elements, apply the operator to "length" elements, 
return the result. 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.)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

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

Invisible wrote:

> Right. Well I guess that more or less answers my question.


http://yosefk.com/c++fqa/inline.html#fqa-9.1

(Warp will hate me for quoting that, but it's actually a pretty good 
explanation.  "inline" has nothing to do with inlining functions.)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> Now what happens if you want to only process elements having some
>> arbitrary property? (E.g., only the odd numbers.)
> 
> I make the function take a functor which tells which elements to
> process.
> This is a standard technique in C++.

You can even write a custom iterator that, when incremented, skips even
numbers. Then you can use it with the existing fold function.

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailcom> wrote:
> Warp wrote:
> > Invisible <voi### [at] devnull> wrote:
> >> Now what happens if you want to only process elements having some
> >> arbitrary property? (E.g., only the odd numbers.)
> > 
> > I make the function take a functor which tells which elements to
> > process.
> > This is a standard technique in C++.

> You can even write a custom iterator that, when incremented, skips even
> numbers. Then you can use it with the existing fold function.

  Good point. In fact, you can create iterators which do a lot of fancy
things, like for example one which traverses the container backwards
(a standard such iterator exists), if you need to perform an operation
in reverse order, or whatever you wish. And all this without having to
modify nor copy the data container.

  Well, I assume that when you say in Haskell "reverse the list and then
give it to this function" the compiler might be able to avoid copying the
list to another one with the elements in reverse order.

-- 
                                                          - Warp

Post a reply to this message