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