Re: [boost] [Hana] Informal review request

17 Mar 2015

      Eric Niebler  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 
    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 
    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