Boost logo

Boost :

Subject: Re: [boost] [Hana] Informal review request
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-03-21 10:20:17

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.



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