Re: [boost] Interest in a list comprehension library?

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
something.
  * 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.