Re: [boost] Re: lambda and maps

From: Joel de Guzman (djowel_at_[hidden])
Date: 2003-10-06 03:25:27

Howard Hinnant <hinnant_at_[hidden]> wrote:
> On Oct 5, 2003, at 3:10 PM, David Abrahams wrote:
> 
>> Howard Hinnant <hinnant_at_[hidden]> writes:
>> 
>>>>> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1403.pdf
>>>> 
>>>>> to operate on tuple-like types instead of just tuple types.
>>>> Then once
>>>>> tuple is standardized (and put in namespace std), then I/O would
>>>> just
>>>>> work for std::pair, and enjoy all the benefits of the tuple I/O
>>>>> manipulators.
>>>> 
>>>> Can't wait :)
>>> 
>>> I realized after I wrote this that my English was ambiguous (C++ is
>>> sooo much easier to work with! :-) ).  The proposal does not have the
>>> modification I suggest.  I wish it did.
>> 
>> I think we can bring it back during drafting, though.  Joel de Guzman
>> has just done some work on tuple algorithms and iterators which may
>> justify that.
> 
> Sounds very interesting!  Fwiw, Metrowerks has shipped such a
> std::tr1::tuple on Mac, however the hookup to pair I/O doesn't work
> unless you reconfigure the lib to put the std::tr1 stuff into std
> (there is a switch to do just that).

Hi,

If anyone's interested, here's the prototype. See: 
http://spirit.sourceforge.net/dl_more/fusion.zip 

It is a work in progress. It is based on the TR1 tuple implementation that
Jaakko and I wrote a few months ago (see the boost-sandbox). This is a re-
implementation of the TR1 tuples with iterators, views and algorithms. The
structure is somewhat modeled after MPL. I code-named it "Fusion" because
the library reminds me of the "Fusion" of compile time metaprogramming with
runtime programming. Right now, for the purpose of testing and
experimenting, I have placed it under the Spirit directory (like Phoenix).

Here's the overall structure:

Tuples:

    tuple       : the basic tuple structure
    tuple-i/o   : tuple I/O
    make-tuple  : make_tuple and tie
    operator    : tuple operators
    generator   : generate a tuple given a begin/end iterators

    * Basically the same as the TR1 tuples in the boost-sandbox
      with the ability to construct and generate tuples from
      iterators.

Iterators:

    Generic iteration for heterogeneous types. This is not at all tied to
    tuples; the tuple-iterator is just a specific type. The library is
    based on iterators. There are iterators for MPL containers, filtering
    iterators, transforming iterators, etc.

Sequences and Views:

    Like in MPL, holds a begin/end iterator. Sequences and views may be
    composed to form more complex sequences and views. View/sequence
    composition is a very nice concept. These are extremely lighweight
    classes and can be passed around by value quite inexpensively. For
    instance, rather than working directly on tuples, the algorithms work
    on views and return views.

    const_value_sequence
        Wraps an MPL-like constant value sequence (e.g. iterators to
        mpl::vector_c and mpl::list_c).

    type_sequence
        Wraps an MPL-like type sequence (e.g. iterators to
        mpl::vector and mpl::list).

    tuple_view
        Wraps a reference to a tuple. 

    filter_view
        given an MPL predicate, filters the view to present only the items
        that passes the predicate.

    single_view
        a single element view (similar to MPL's)

    joint_view
        a two-sequence view (similar to MPL's). Quite nifty, for example
        here's how push back is implemented:

        template <typename ViewT, typename T>
        inline typename push_back_result<ViewT, T>::type
        push_back(ViewT const& view, T const& x)
        {
            typedef typename make_single_view<T>::type insert_type;
            typedef joint_view<ViewT, insert_type> result;
            return result(view, insert_type(x));
        }

    slice_view
        a sliced sequence/view.

    transform_view
        Like, MPL's: a sequence wrapper that allows one to operate on the
        transformed sequence without actually creating one. However, this
        uses half-runtime transform functions. Here's an example of a
        transform:

        struct square
        {
            template <typename T>
            struct result
            {
                typedef T type;
            };

            template <typename T>
            T operator()(T x) const
            {
                return x * x;
            }
        };

        << The nice thing is that you can use Lambda/Phoenix polymorphic
        functors for the transform >>

Algorithms:

    With very complex composition of algorithms, it is not desirable to
    work directly on tuples. Like MPL, and unlike STL, the algorithms take
    in sequences/views and *return* the result by value; the algorithms are
    purely functional and do not (cannot) have side effects. We cannot have
    an out parameter that is passed by reference where the result is
    placed. The algorithms, instead, work on sequences and views and
    generate views.

    This strategy is very efficient. You can think of the algorithms as
    "lazy". The values are generated only when they are needed -for example
    when generating a tuple. When you are sure that you need a tuple, you
    can "generate" it from the view: generate(view);

    Currently, these algorithms are defined:

        fold
        find
        find_if
        transform
        filter
        count
        count_if
        contains
        append
        push_back
        push_front
        insert
        remove
        replace
        remove_if
        for_each

    Each of these algorithms has its result metaprogram. For instance,
    here's the transform algorithm:

        template <typename ViewT, typename F>
        struct transform_result
        {
            typedef transform_view<ViewT, F> type;
        };

        template <typename ViewT, typename F>
        inline transform_view<ViewT, F>
        transform(ViewT const& view, F const& f)
        {
            return transform_view<ViewT, F>(view, f);
        }

    transform_result<ViewT, F>::type is the result type when transform is
    called given a view ViewT and a transform functor F.

Example, squaring an MPL list_c and storing it in a tuple:

    typedef boost::mpl::range_c<int, 5, 9> mpl_list1;
    typedef const_value_sequence<mpl_list1> sequence_type;
    sequence_type sequence;

    std::cout << generate(transform(sequence, square())) << std::endl;
    BOOST_TEST((generate(transform(sequence, square()))
        == make_tuple(25, 36, 49, 64)));

More tests/examples can be found in the test directory.

Regards,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net