Re: [boost] [Hana] Informal review request

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> gmail.com> writes:

> 
> AMDG
> 
> 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.

Regards,
Louis

[1]: http://goo.gl/hHzkuJ
[2]: https://www.fpcomplete.com/user/bartosz/understanding-algebras
[3]: https://github.com/ldionne/hana/issues/18