Subject: Re: [boost] Interest in a list comprehension library?
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2010-12-22 05:46:30
On 22/12/2010 06:40, Brent Spillner wrote:
> * 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().)
satisfy_predicate() only advances the inner iterator until the first
element that satisfies the predicate is found, so as to skip the
elements that do not satisfy it.
It is indeed called at construction time, and also at each increment.
Doing it some other way (advancing in decrement) would lead to more
branches and data than is necessary.
> * 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
I hope this backtracking can be efficiently implemented. I'll have to
take a look at your implementation.
> * 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.)
You could predeclare a set of variables in a specific namespace to
reduce that boilerplate to a certain point.
> 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.
It shouldn't matter at all what is being used. You should really allow
any function object to be passed to define your criteria.
Phoenix is just a powerful way to create function objects in an inline
You just have to make sure the type you use for x, y, z etc. is
compatible with Phoenix.
> 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.
Using Proto would mean defining a grammar for your syntax, and defining
a transform that converts a C++ AST into the desired C++ code, here a
lazily evaluated range.
It's practical for various reasons: maintenance, validation,
reusability, and better interoperability with other embedded languages
defined using Proto.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk