Eric Niebler <eniebler <at> boost.org> writes:
On 3/16/2015 4:43 PM, Louis Dionne wrote: <snip>
However, there is a more serious incompatibility stemming from how `reverse_fold` is usually specified and understood: as starting from the end. This causes a problem for infinite data structures, which obviously have no reachable end. Instead, `foldr` is usually specified recursively in a way that makes it possible to right-fold infinite data structures (and it is indeed possible to do so in Haskell and with MPL11). There is no real support for infinite data structures in Hana right now, but simple Concept generalizations which I have been thinking about might make this possible. In summary, I want to make sure I'm not blocking myself if I make the `foldl/foldr` change, but rest assured that I understood very well the people's desire.
I personally don't see a problem with keeping foldr's semantics but changing the name to reverse_fold, if that's what people want.
The problem is that in the infinite case, it's not a "reverse" fold anymore, and hence the name becomes very misleading. For those that might be reading this and wondering what I mean by non-strict folds, here's how `foldr` can be defined recursively: 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)); } In a strict evaluation context, when the else branch is taken, the foldr(tail(xs), s, f) is always evaluated. However, in a non-strict context, a "thunk" (a deferred computation) is built instead and the else branch looks more like return f(thunk[head(xs)], thunk[foldr(tail(xs), s, f)]); where thunk[expr] is just an `expr` that will be evaluated if its value is required inside of f. So, for example, if `f` is (pseudo) defined as auto f(auto x, auto ignored) { return x; } 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); }); } implicitly. In the above example, if `pred(x)` returns true for some `x`, then the corresponding `pred(y)` is never evaluated because `||` short-circuits. Because we're in a hypothetical non-strict evaluation world, this causes `y` not to be evaluated at all. However, if you go back to the definition of `foldr` above, the `y` was an expression of the form foldr(tail(xs), s, f) where f is our lambda in the `any_of` algorithm. So basically, we're saying that the recursive call to `foldr` is not evaluated, and hence our `any_of` algorithm short-circuits automatically. So anyway, my point is that seeing right-folds as f(x1, f(x2, f(x3, ...f(xN, state))) is slightly more general than seeing them as starting from the end, because it allows for the case where there's no end. That being said, I'm aware that we're _not_ in Haskell and so it does not really apply to Hana. I'd just like to make sure that I (or someone else) won't find a nice application for infinite data structures in Hana that would make me regret that choice. But writing this, I have the germ of an idea that these lazy folds might be nothing more than a monadic fold with the Lazy Monad, which would resolve the issue. I have to look into this further before I can say anything.
7. In a different thread [6], it was suggested that the Logical concept should interact well with Lazy computations. I have begun to investigate possible ways of nicely tying both together, as can be seen at [7], and will try to have something definitive before a formal review.
[7] http://ldionne.github.io/2015/03/16/laziness-as-a-comonad
Awesome. I'm really looking forward to reading this.
As it stands, I find the post to be a bit boring because there's no interesting use case at the end. I'm thinking about expanding on how we can compose lazy computations (as Applicatives and Monads), which is really the fun part and also the part that gives us pretty semantics for composing arbitrary lazy computations. Locally, I have prototyped a new `if_` with both lazy and non-lazy semantics which I think will be going into Hana. Anyway, will do if time permits!
8. In the same thread [6], it was also suggested that Hana provides a way to write inline metafunctions, pretty much like MPL's lambda expressions. I think this is an interesting idea that could make simple type-level computations super easy to write and I will try to explore it in time for the formal review.
I'll be interested to see if/how you avoid Boost.MPL's lambda evaluation semantics quagmire. I find the business of tracking whether/where substitutions were done, conditionally probing for ::type, then conditionally selecting the substitution, to be pretty unsatisfactory. Too much magic, too difficult to grok, and could even cause errors by causing inadvertent instantiations of things not meant to be instantiated -- which means things need to be protect'ed, etc, etc. I would prefer a simpler, more predictable algorithm, even at the expense less pithy lambdas.
I too agree that MPL's lambda expressions are no fun, especially to implement. For Hana, I would aim for something much simpler because it would just be a way to quickly compose type-level computations in order to save a couple of lines. For more complex computations, my opinion is still that one should use plain functions. Regards, Louis