Re: [boost] [Hana] Announcing Hana's formal review next week (June 10th)

Subject: Re: [boost] [Hana] Announcing Hana's formal review next week (June 10th)
From: Larry Evans (cppljevans_at_[hidden])
Date: 2015-06-20 14:00:13

On 06/17/2015 07:36 AM, Louis Dionne wrote:
> Larry Evans <cppljevans <at> suddenlink.net> writes:
> 
>>
>> On 06/13/2015 09:52 AM, Louis Dionne wrote:
>>> Larry Evans <cppljevans <at> suddenlink.net> writes:
>>>
>>>>
>>>> On 06/09/2015 11:00 AM, Louis Dionne wrote:
>>>> [snip]
>>>>>
>>>>> Indeed, you are using a Map when what you really want is a Tuple, since
>>>>> your keys are integers. Here's the version I would have written:
>>>>>
>>>>> [...]
>>>>>
>>>>> However, I can easily imagine another example where you actually need 
>>>>> the functionality of a Map. See below for performance comments.
>>>>>
>>>> [snip]
>>>> Why couldn't map be implemented as a tuple, as shown here:
>>>>
>>>> https://gist.github.com/cppljevans/8e545e8d83946cd74311
>>>>
>>>> Wouldn't that eliminate the difference in performance between
>>>> map and tuple?
>>>
>>> The problem with this approach is that equality of keys can't be more 
>>> general than type identity. In other words, in your example, writing
>>>
>>>     get<_ulong<1>>(mud)
>>>
>>> would fail because there is no _ulong<1> key, but only a _uint<1>, even 
>>> though they compare equal. I want to determine the equality of keys with 
>>> the `equal` function, which is more general. Of course, in the specific 
>>> case of a Map mapping types (and only types) to values, then your approach
>>> could be used, and it is in fact exactly what I had in mind.
>>>
>>
>> OK.  I hadn't thought of that.  OTOH, why not just patch the gist map
>> with a method for doing the get_key using the more general `equal`
>> function.  Then you could have both the fast find with get, and the
>> more general get_key using the `equal` function?
> 
> That's an idea. My initial idea was to simply detect when a map is created
> with all the keys being Types. In that case, lookup by == is just lookup
> by is_same, and you can use an optimized representation for the Map, and
> an optimized version of the lookup algorithm. Such a Map might be created
> with map_t<...> or something, I haven't figured that one out yet. It's 
> similar to the way you can use tuple_t<...> to create a tuple optimized
> for types.
> 
[snip]

Adding the following function after the gets works:

    template
    < typename KeyEqual
    , typename... Key
    , typename... Val
    >
    auto
  get_equal_key
    ( _map_tuple<key_val<Key,Val>...>const& a_map
    )
    {
      constexpr auto key_found_maybe_v
        =find(make_set(Key{}...),KeyEqual{});
      constexpr auto key_found_v
        =from_maybe(nothing,key_found_maybe_v);
      using key_found_t
        =typename decltype(key_found_v)::type;
      return get<key_found_t>(a_map);
    }

I assume it would suffer the same slow compile times
as the current map because it uses find.  If the
KeyEqual is not found, then the compiler errors
at the key_found_t definition with and error
about nothing not having a ::type.

-regards,
Larry