Boost logo

Boost :

Subject: Re: [boost] [Hana] Informal review request
From: Edward Diener (eldiener_at_[hidden])
Date: 2015-03-21 10:40:36

On 3/21/2015 10:20 AM, Louis Dionne wrote:
> Steven Watanabe <watanabesj <at>> writes:
>> On 03/17/2015 11:39 AM, Louis Dionne wrote:
>>> <snip>
>>> template <typename Sequence, typename State, typename F>
>>> auto foldr(Sequence xs, State s, F f) {
>>> if (is_empty(xs))
>>> return s;
>>> else
>>> return f(head(xs), foldr(tail(xs), s, f));
>>> }
>>> <snip>
>>> since `f` never uses the value of its second argument, this argument
>>> is never evaluated. So the "else" branch inside the `foldr` becomes:
>>> return f(thunk[head(xs)], thunk[foldr(tail(xs), s, f)]);
>>> --> return head(xs);
>>> and the recursive call to `foldr` is never evaluated. This allows
>>> processing infinite lists lazily and writing short-circuiting algorithms
>>> such as
>>> template <typename Sequence, typename Predicate>
>>> bool any_of(Sequence xs, Predicate pred) {
>>> return foldr(xs, false, [](auto x, auto y) {
>>> return pred(x) || pred(y);
>>> });
>>> }
>> I know this looks cool, but it's actually a perfect
>> example of why foldr on an infinite sequence isn't
>> a good idea. On an infinite sequence, this any_of
>> will either return true or will go into infinite
>> recursion. I can't see any practical use for such
>> behavior. If I ever needed to use any_of on an
>> infinite sequence, I doubt that having the false
>> case fail would be acceptable. An any_of that
>> actually handles the false case for infinite sequences
>> can't be implemented generically. IMHO, foldr
>> makes it much too easy to write algorithms like
>> this that almost work.
> Sorry for the late reply. Well, any_of might not have been the best
> example, but lazy right folds still make sense in a number of contexts.
> Being lazy when right-folding also allows interesting optimizations to
> take place (for example, see [1]), but that's a different story and
> we're far from there in Hana.
> On another note, I dismantled my germ of thought that lazy folding
> is just monadic folding with the Lazy monad; it's not that simple.
> I think achieving lazy right folds generically would require adding
> a generic expression evaluator that would be used everywhere to
> evaluate expressions, and then by overriding it one could pick
> between lazy and strict algorithms. I'm not sure though; I'm still
> trying to understand F-Algebras as presented by Bartosz in [2].
> Anyway, so the conclusion is that lazy right folds won't be supported
> in Hana, at least not for a while. So this opens the door for renaming
> foldl/foldr to fold/reverse_fold. I'll probably start by adding aliases
> and then consider removing foldl/foldr, because renaming them all at
> once would require more work, especially with the new naming scheme
> with no-state overloads that was discussed in the poll at [3].
> I hope this sounds reasonable.

I would like to urge you to use easily understandable names in your
library rather than shortened and more cryptic names. Any extra typing a
user of your library may have to do is easily offset by the fact that
more easily understandable names make your library much more
understandable to use.

Boost list run by bdawes at, gregod at, cpdaniel at, john at