Re: [boost] [Hana] Informal review request

Vicente J. Botet Escriba writes:

Le 07/03/15 21:00, Louis Dionne a écrit :

...

Vicente J. Botet Escriba writes:

...

Le 07/03/15 17:38, Louis Dionne a écrit :

...

Vicente J. Botet Escriba writes: [...]

Do you have an equivalence in Haskell to your datatype/generalized type? No, but shooting from the hip you could approximate them with type classes.

A type class that is instantiated with another type class?

Like I said, I don't know Haskell well enough to tell whether there's a direct mapping between data types in Hana and something else in Haskell. Is there an equivalent to Fusion/MPL tags in Haskell?

[...]

Does it means that you are associating a "principal" type class (obtained by the function datatype) to a data type, that is used to instantiate the other type classes?

I was just using the Tuple type class as a hack to "group" the different TupleN representations under the same umbrella. Again, I'm not a Haskell wizard and there might be a clean way to do it.

...

...

[...] if you have an heterogeneous type as pair for example, the mathematical transform function should

transform : pair(T,U) x (T -> R) x (U -> S) -> pair(R, S)

As C++ has overloaded functions we don't need to pass two functions, but just an overloaded function. That's an interesting point of view. However, with this approach, you can't say that Pair is a Functor. It instead becomes a BiFunctor [2].

Right. A Functor has only one type parameter. In Haskell you can not overload functions so that the functions must be named differently. But in C++ we can use the same name, so we could have a transform : BiFunctor x BiCallable -> BiFunctor.

IIUC, BiCallable basically represents two functions with different domains stitched into a single function via C++ overloading, right? Then, I say we don't want that because it still represents two different functions with two different domains, instead of a single function with the proper domain.

...

Furthermore, let's say you have a pair(T, T). transform is then

transform : pair(T, T) x (T -> R) x (T -> S) -> pair(R, S)

transform should hence still receive two functions, regardless of the fact that we could provide a single overloaded function.

pair(T, T) can be seen as an instance of Functor as list(T) does.

We need an alias

template <class T> using pairT = pair;

See below.

...

Let me now use a tuple instead of a pair as an example because it sticks more closely to what happens in Hana (Pair is not a Functor in Hana). tuple shouldn't be a Functor neither. transform then becomes:

transform : Tuple(T1, ..., Tn) x (T1 -> R1) x ... x (Tn -> Rn) -> Tuple(R1, ..., Rn)

First, if you use this approach, you can't say that Tuple is a Functor. It has to be a N-Functor, which is the N-argument equivalent to the BiFunctor. Furthermore, you have to provide N different functions to be able to transform it. So for example, when transforming a tuple(int, int, int), you would have to say

transform(tuple(1, 2, 3), [](int i) { return i + 1; }, [](int i) { return i + 1; }, [](int i) { return i + 1; } )

As pair, and list<T> tuple can be seen as an instance of a Functor. But not its heterogeneous variants.

Fine, but what about tuple? Clearly, transform should receive three different functions: transform : tuple x (T -> A) x (U -> B) x (T -> C) -> tuple And hence we still have a 3-Functor (for w/e that means). I think I'm starting to understand where our views diverge: You keep on trying to see heterogeneous data structures like tuples as product types, which they are at the most basic level. I lift the type-system one level higher up and see tuples as a fixed-length arrays of objects with the same "type" (generalized type). This approach has some advantages, like being able to look at objects of the Type data type as objects of the same "type". Those objects all have a common interface, which corresponds to the .

...

That's not "heterogeneous" programming; it's just an equivalent way of writing

r1 = f1(t1) r2 = f2(t2) ... rn = fn(tn)

where `tk` are the elements of a tuple, and `fk` are the functions mapped on it by the N-Functor's `transform`. What we actually want is

r1 = f(t1) r2 = f(t2) ... rn = f(tn)

where `f` is defined as

f : (intersection of the data types of the tuple's elements) -> (some other type) I'm sure doing such kind of transformations is useful. However the semantic doesn't match to the transform(fmap) function associated to the Functor I know.

It's because Hana does not use the Functor _you_ know. It's pretty much a work in progress, but you might be interested in taking a look at my thesis [1]. I show how we can categorify Hana, and I'm about to explain how Functors materialize themselves. It is in essence exactly the same thing as what happens with the Hask category, except that you replace "type" by "generalized type".

...

In other words, `f` is a function whose domain is "the set of all objects with which I can do X". If there are objects in the tuple that don't support "X", then the program is ill-formed. Concepts will put us much closer to this.

Do you mean C++17/20 Concepts? Couldn't "type classes" help here?

Yes, C++ Concepts. I just meant that C++ Concepts would help us put constraints on families of types, without having to fix their representation.

...

...

[...]

How the fact to have either and maybe<A> makes it more dificult to interact with heterogeneous objects? Let's try to implement a type _maybe<A>:

template <typename A> struct _maybe { struct empty { };

union { A a; empty e; } val; bool is_nothing;

constexpr _maybe() : val{empty{}}, is_nothing{true} { } constexpr _maybe(A a) : val{a}, is_nothing{false} { } };

Now, let's try to implement, for example, the `maybe` function, which has signature maybe :: B x (A -> B) x _maybe<A> -> B. Remember that those A's and B's are actually generalized types, not usual C++ types (we're working with heterogeneous stuff):

template constexpr auto maybe(Default def, F f, M m) { return m.is_nothing ? def : f(m.val.a); }

Seems legit? This works:

maybe(1, [](int i) { return i + 1; }, _maybe<int>{1});

But this does not, even though std::tuple<> and std::tuple<int> have the same generalized type:

maybe( std::tuple<>{}, [](int i) { return std::make_tuple(i); }, _maybe<int>{1} );

It fails with

error: incompatible operand types ('tuple<(no argument)>' and 'tuple<int>') return m.is_nothing ? def : f(m.val.a); ^ ~~~ ~~~~~~~~~~

This seems normal to me.

It _is_ normal, but it's not useful in a context of dealing with heterogeneous values, because you can't return objects of different types from that function. What we need is to store the information required to make that branch in the Maybe's type, and then we can return objects of different types from that function, because the conditional is actually implemented as an overload.

Does it mean that classes as experimental::optional<T> couldn't be seen as an instance of Hana Functor type class?

Yes, it can be a Functor. Just like std::vector is a Hana Functor (I added this recently). However, some types that are fundamentally useful at runtime can't model some concepts in Hana. For example, the current library requires the is_empty method (from Iterable) to return an IntegralConsant. For this reason, std::vector can't be made Iterable.

...

m.is_nothing is not a constant expression inside the function. If it was, we could use `bool_` to use overloading to pick which branch we're executing instead of doing it at runtime, like we do right now. This is explained in the section on the limitations of constexpr [3].

Does it means that your data types Maybe and Either are usable only as meta-programming tools? I don't see where could I use them at run-time.

You're right, they are mostly useless at runtime, just like boost::optional and boost::variant are completely useless at compile-time. That's exactly the point; Hana is a _metaprogramming_ library. Quoting from Maybe's documentation [2]: [...] However, there is an important distinction to make between Maybe and std::optional: just(x) and nothing do not share the same type. Hence, whether a just or a nothing will be returned from a function has to be known at compile-time for the return type to be computable at compile-time. This makes Maybe well suited for static metaprogramming tasks but very poor for anything dynamic.

...

...

[...]

My point was more on how the library is checking the fist argument of Transform is a Functor and that the second argument is a "function" from the Functor's underlying type T to another type U.

transform : Functor<T> x (T -> U) -> Functor(U)

If the implementation declares transform as

auto transform = [] (auto F, auto Fun)

Couldn't the the library check that the arguments passed in F and Fun respect the requirements? Yes, but that would require `Fun` stating that it is a function from data type T to data type U, which is impractical. In particular it means that this:

transform(make_tuple(1, 2, 3), [](int i) { return i + 1; });

would not work. Instead one would need to write

transform(make_tuple(1, 2, 3), hana::function([](int i) { return i + 1; }));

Then, say you have

transform(make_tuple(1, std::string{"abc"}, my_class{}), hana::function([](auto x) { ... }));

The way I see it, it's just not convenient. Doing it would definitely force us to be mathematically correct though. Instead, I aim to catch most programming errors by checking that F is a Functor (which is easy). If you send in a random function, then the compiler will tell you where you're wrong, but Hana won't.

Maybe it could be a different "transform" function that applies to ProductTypes instead of to Functors. The requirement on Fun could be that Fun is callable with any of the types on the ProductType and that each one of these overloads should have the same result U.

We're basically saying the same thing here. IIUC, your ProductTypes are basically what I call Functors, and saying that Fun is callable with any of the types in the ProductType is just saying they share a set of common concepts, which I try to embody in the concept of data type. There's a small generalization missing from my understanding to bridge the gap between concepts and data types, which I think are the same in the end. See the remark at the end of the section on generalized data types [3].

I think that I need to understand better the scope of the library, is Hana a pure functional programming library or another way to do pure meta-programming or both at the same time, but restricted to the limitations of the intersection?

Like Fusion, Hana is a library that bridges between runtime and compile-time. Basically, you can manipulate sequences with heterogeneous objects in them, but their length has to be known at compile-time. I know there's a way to generalize this so that it works with homogeneous sequences whose size is known at runtime too, but I'm not tackling this right now. Then, type-level computations come for free when you have heterogeneous sequences, but we had just never saw it as clearly as we do now. Hana is not just a "pure functional" library that works at runtime. It's a generalized Boost.Fusion which happens to use concepts from the functional paradigm because it's convenient. Regards, Louis [1]: https://github.com/ldionne/hana-thesis [2]: http://ldionne.github.io/hana/structboost_1_1hana_1_1_maybe.html [3]: http://ldionne.github.io/hana/index.html#tutorial-hetero