[boost] Hana Searchable

Subject: [boost] Hana Searchable
From: Robert Ramey (ramey_at_[hidden])
Date: 2014-08-03 17:51:26

I can't review the whole library. So I'm confining my observations to just a
couple of aspects. My method is 
to review some section of the documentation. it looks like a critique of the
documentation, but it's really 
observations on the underlying design of the library. 

In this post I'm addressing Searchable in the reference section of the
documentation.   

Searchable

>From the explanation of Type class - given a type T, I'm expecting to see
some sort of list of operations
such that

Searchable<T> will compile.

What I see is:

boost::hana::Searchable Struct Reference

Type classes
Description

Data structures that can be searched.

Searchables have a concept of keys and values. Searching is always done on
the keys and the result is always the associated value. There is no
requirement that the keys and values be different.

Synopsis of methods
constexpr auto 	any
         Return whether any key of the structure satisfies the predicate. More...

…

Instances and minimal complete definitions
struct  	instance< Map >
         A map can be searched by its keys with a predicate yielding a boolean
Integral. More...
 
struct  	instance< Maybe >
         Instance of Searchable for Maybes. More...
 
struct  	instance< Set >
         The keys and the values of a Set are its elements; the Searchable 
instance follows naturally from that. More...

My first thought is:

Searchable is (sort of) a C++ Concept (type constraints)

"Synopsis of methods" is what we customarily refer to as "valid expressions"

"Instances and minimal complete definitions" is what we customarily refer to
as "models"

But right away I have a problem - since "any" doesn't show a valid C++
expression at this level of the documentation I click "auto" and get:

Initial value:
= [](auto predicate, auto searchable) {
        return Searchable::instance<
            datatype_t<decltype(searchable)>
        >::any_impl(predicate, searchable);
    }

which is totally mystifying to me.  I realize that it's a C++ lambda
expression. But the only reference I see
to "any" is (maybe) Searchable::any_impl.  I'm guessing that any_impl has
some sort of code which uses predicate
and searchable to to return some static_assert - or not.  The usage of
any_impl seems designed to hide the vary
thing I'm interested it - what kind of type can I use as an argument to
Searchable.  This seems not at
helpful to the user.

Now "predicate" and "searchable" parameters are define (in text). All
"searchable" says is that it's a
structure to be searched - nothing about what constitutes such a structure. 
can std::vector<int> be used
as this "searchable" parameter? don't know - and the document doesn't tell
me.  "predict is a little better
in that it says that it's something that is called and that it returns a
type fulfilling the constraints of
"Logical" which itself linked (thank you).

Now I have a few examples which are a little more helpful.

    BOOST_HANA_CONSTEXPR_LAMBDA auto odd = [](auto x) {
        return x % 2_c != 0_c;
    };

So now I see what a predicate is supposed to look like - in this case it's a
function
which returns a bool.  The usage of auto certainly isn't helpful here. The
syntax
x % 2_c != 0_c is suggestive.  It seems that 2_c and 0_c refer to integer
constants
2 and 0 respectively.  I'm sort of wondering why we can't just use 2 and 0
themselves
since it seems we're using constexpr here.

    BOOST_HANA_STATIC_ASSERT(any(odd, list(1, 2)));

The above is interesting.  From the explanation of type class I expect this
to trap
at compile time - or not depending upon the type of list.  First of all, I
don't know
whether this refers to std::list or some type of compile time list of types. 
Again
the documentation leaves me mystified.

Documentation BOOST_HANA_STATIC_ASSERT leaves me even more befuddled. It
says that
it resolves to either static_assert or assert depending on whether the
argument
is a constexpr or not.  An interesting idea.  But here we're inside the
Searchable
type class definition - so wouldn't it make more sense to invoke
static_assert
directly?  

The most confusing thing about the example is that Searchable is never
mentioned.
Isn't the point of defining a Typeclass (C++ concept)?.  How it envisioned
that 
this be used.

Here is what I would expect to see using our customary way of looking at
things
in the customary way.  I realize that it's not an exact match but it's the
best
I can do from looking at the documentation.

#include "boost/concept/assert.hpp"

// define concept Searchable
template struct<class S, class P, class T>
struct Searchable {
        BOOST_CONCEPT_ASSERT((std::UnaryPredicate<P>));
        BOOST_CONCEPT_ASSERT((std::Sequence<T>));
};

// define any for searchable types

template<class S, class P, class T>
constexpr bool any(const S &s, const P & p){
        BOOST_CONCEPT_ASSERT((Searchable<S, P>));
}

// example
auto constexpr odd = [](auto x) {
        return x % 2 != 0;
};

?::list<1, 2, 3> l;

static_assert( any(list, odd) ); // should not trap

?::list<2, 4, 6> l2;

static_assert( any(list, odd) ); // should trap with error at compile time

There are lots of "holes" in my example above, I think this more or less
captures 
what you have in mind.  But it's much simpler to understand and use.

I confess I've failed to understand the runtime aspects of your library. 
This is
true even though I have worked with fusion more than most and a lot with
MPL. I
think this should be easy for me - but it's not.

BTW - I only used "Searchable" as it happened to be the first one I looked
at.
Personally I don't believe that thinks like "Searchable", and "Sortable"
don't
belong as models of type constraints.  Using "Sortable as a quick example, 
my complaint is that it's tautological.  Something is defined here as
"Sortable" 
if you can sort it.  Actually something like "Sortable should be defined as:

template<class Iterator>
void quicksort(Iterator begin, Iterator end){
        BOOST_CONCEPT_ASSERT((RandomAccessIterator<Iterator>));
        BOOST_CONCEPT_ASSERT((LessThanComparable<Iterator::value_type));
        …
}

while a different sorting algorithm
void mergesort(C &amp; c){
        BOOST_CONCEPT_ASSERT((ForwardIterator&lt;Iterator>));
        BOOST_CONCEPT_ASSERT((LessThanComparable<Iterator::value_type));
}

So the the idea of "Sortable" doesn't make any sense when not coupled with
the data structure which holds the data.

Although my example above is based on "Sortable" - it really applies to any
type constraints with names like "Searchable", "Foldable", etc.

Robert Ramey

--
View this message in context: http://boost.2283326.n4.nabble.com/Hana-Searchable-tp4665987.html
Sent from the Boost - Dev mailing list archive at Nabble.com.