Re: [boost] [Hana] Informal review request

Subject: Re: [boost] [Hana] Informal review request
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2015-03-08 11:28:53

Le 07/03/15 21:00, Louis Dionne a écrit :
> Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
>
>> Le 07/03/15 17:38, Louis Dionne a écrit :
>>> Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> 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?
> For example, the Tuple data type could be implemented as
>
>      -- The different actual representations for tuples
>      data Tuple0 = Tuple0
>      data Tuple1 a = Tuple1 a
>      -- etc...
>
>      -- The Tuple generalized type representing all those guys
>      class Tuple t where
>          len :: t -> Int
>
>      instance Tuple Tuple0 where
>          len _ = 0
>
> Admittedly, the above is missing something fundamental if we want to
> implement other functions like `head`, but that reaches the limit of
> my Haskell-fu. I think looking at Haskell's type families [1] might
> provide more insight.
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?
>>> As I already
>>> said on this list during the last informal review, what I make
>>> is a tradeoff between mathematical correctness and usability
>>> of the library. While Hana provides structures that satisfy
>>> the laws rigorously, I want users to be able to use those
>>> structures in a quick and dirty way as a mean of being more
>>> productive when needed. For example, I would not object to
>>> someone writing [pseudocode]:
>>>
>>>       auto to_string = [](auto x) { /* convert x to a std::string */ };
>>>       auto xs = hana::make_tuple(1, 2.2, "abc");
>>>       auto ys = hana::transform(xs, to_string);
>>>
>>> Since `1`, `2.2` and `"abc"` do not share a common data type and
>>> the signature of `transform` is (for a Functor F)
>>>
>>>       transform : F(T) x (T -> U) -> F(U)
>>>
>>> , the above should normally be ill-formed. However, the library
>>> makes such usage possible because I kept in mind that we're
>>> working in a "dirty" heterogeneously-typed context. Bottom line:
>> I don't think heterogeneous types are dirty. We need just a different
>> type of function (Overloaded) to transform them.
>>
>> 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.
> 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<T,T>;

>
> 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<T ...> 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<T,T>, and list<T> tuple<T,T,T> can be seen as an instance of a Functor. But not its heterogeneous variants.

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

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

>
> The principle behind Hana's generalized types is really that
> we "lift" the types of the objects and then consider objects
> up-to-different-representations. I also think it can be seen
> as a quotient of the set of all types by the equivalence relation
>      
> T ~ U     if and only if     T and U model exactly the same concepts
>                                       in exactly the same way
>
> Concretely, the mathematical universe we're working with is not
> only a set; it's actually the C++ category where objects are Types
> and morphisms are functions. Hence, that "quotient" would have to
> also take morphisms into account. But I'm reaching the end of my
> math-fu now.
Thanks for the clarification. I believe I start to understand your 
generalized type design/concept.
I was looking for another design/concept closer to a "type constructor".
>
>> [...]
>>
>> How the fact to have either<A,B> 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 <typename Default, typename F, typename M>
>      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.
Does it mean that classes as experimental::optional<T> couldn't be seen 
as an instance of Hana Functor type class?

> m.is_nothing is not a constant expression inside the function.
> If it was, we could use `bool_<m.is_nothing>` 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.
>>> [...]
>>>
>>> Notice meta::quote.
>> I wonder if the meta::transform couldn't take care of quote.
> If it takes care of quote, then we need to always pass templates
> to higher order algorithms. Basically, that would be like accepting
> metafunctions instead of metafunction classes in the MPL interface.
> There are good reasons not to do that.
I see.
>
>> [...]
>>
>> 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(int)>([](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.

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?

Best,
Vicente