Subject: Re: [boost] Interest in a list comprehension library?
From: Brent Spillner (spillner_at_[hidden])
Date: 2010-12-22 00:40:18
On 21/12/2010 09:09, Mathias Gaunard wrote:
>Can you explain the difference with the Boost.Range adaptors?
I think these are the most important ones:
* Lazy evaluation of every comprehension. In contrast,
boost::filter_iterator applies the filter predicate to the entire
wrapped range at construction time (via satisfy_predicate().)
* As a consequence, there are several ways to limit the amount of
computation based on the amount of output required rather than the
length of the input ranges.
* Predictable backtracking behavior that allows filter criteria to
depend on each other. This enables a number of computations (e.g.
looping over the elements within a range of ranges) that are otherwise
difficult or impossible to express, and even in straightforward cases
permits some efficiency improvements. For instance, your example
Pythagorean triple comprehension using Boost.Range evaluates a number
of combinations of the three indices equal to the n'th cubic number,
while the 'i <<= range(1,n), j <<= range(i,n), k <<=range(j,n)'
version evaluates the n'th tetrahedral number's worth of combinations.
The ratio of these quantities approaches 6 as n increases, and is in
fact greater that 5 by n=16. A factor of 5 speedup is surely worth
* Somewhat more concise and I believe more readable syntax. My goal
was to require fewer characters than a Python comprehension and
ideally not many more than Haskell, and I think I'm there in the
simple cases. (Neglecting the variable declarations, naturally.)
>It is true Boost.Range is quite lacking in terms of range generators, and maybe your solution is what we need.
Don't get me wrong; I think Boost.Range is great, and the iterator
adapters are a fantastic way to improve the iterator-based algorithms
that tend to be somewhat clumsily expressed in a lot of traditional
C++ code. I just don't think they're a fully satisfying substitute
for the comprehension syntax (and backtracking, etc.) provided or
easily defined in most functional languages.
>It would be nice however, if it didn't reinvent the wheel and can be based on Phoenix for the functional part.
I definitely don't want to reinvent the wheel, and I was a little
hesitant to publish this in case it largely duplicated work that
someone else had done in Range or Phoenix or somewhere else. I've
never used Phoenix; it seems fascinating but I'm a little wary of
making it a dependency just to get something simple like a
comprehension syntax. I also took a look at using Boost.Proto to
provide the expression trees, but it seemed that the syntax was a
little more verbose than it needs to be for things that will be
evaluated only in the context of a comprehension expression. Either
one of those libraries could likely replace most of the boilerplate in
my expressions.hpp and operators.hpp; on the other hand, being
boilerplate, it wasn't that hard to write or to get it to work exactly
as I needed. At this point I'm leaning more toward providing adaptors
to permit Proto or Phoenix expressions within a comprehension, rather
than absolutely requiring the use of either.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk