Steven Watanabe
AMDG
On 03/17/2015 11:39 AM, Louis Dionne wrote:
<snip>
template
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
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