Re: Boost algorithm library (Was: [boost] New upload: algorithm.zip 1)

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-27 07:34:06

From: "John Max Skaller" <skaller_at_[hidden]>
> Vesa Karvonen wrote:
> >
> > From: "Fernando Cacciola" <fcacciola_at_[hidden]>
> > > From: Jeremy Siek <jsiek_at_[hidden]>
> > [...]
> > > I am not sure if a *standarized* container-like interface will have a
good
> > > impact on a program design.
> >
> > I'm not so sure. Functional languages do quite well without iterators.
Take a
> > look at functions such as 'foldr', 'map', 'filter', 'take', 'drop',
'rev',...
> > that you can find in most functional languages (in some functional
languages
> > they may be named differently).
>
> I don't really agree.

I'm surprised. You don't agree that "Functional languages do quite well
[...]"?

> First, lets call these functions
> 'functional iterators'. Lets take map as an example. The general form is
>
> map function list
>
> Note that Fish 2 is the only language I know of in which map is
> polymorphic on the data functor (Charity?)

I think that it is perfectly possible to create a map function that can be
parameterized with the type of the sequence it iterates. At least I know that
it is possible in C++ template metaprogramming, where you can create instances
of algebraic types and pass them as values.

Let's first consider a concrete algebraic type (I have omitted typename and
::template from the examples to make them more readable. I have also ignored
the issues of template instantiation and just assume that select<> (==if using
boolean<bool> as condition) is lazy.):

    // this is the algebraic type
    struct type_list
    { // constructor
      struct empty
      {
      };

      // constructor
      struct cons
      { template<class head, class tail>
        struct code
        { typedef code<head,tail> type;
          typedef head head_type;
          typedef tail tail_type;
        };
      };

      // function
      struct is_empty
      { template<class c>
        struct code
        { typedef boolean<is_same<c,empty>::value> type;
        };
      };

      // function
      struct head
      { template<class c>
        struct code
        { typedef typename c::head_type type;
        };
      };

      // function
      struct tail
      { template<class c>
        struct code
        { typedef typename c::tail_type type;
        };
      };
    };

Now, we can say that every algebraic type that provides the following
interface:

    // this is the algebraic type
    struct type_list
    { // constructor
      struct empty
      { /*..*/
      };

      // constructor
      struct cons
      { template<class head, class tail>
        struct code
        { typedef /*..*/ type;
        };
      };

      // function
      struct is_empty
      { template<class c>
        struct code
        { typedef boolean</*..*/> type;
        };
      };

      // function
      struct head
      { template<class c>
        struct code
        { typedef /*..*/ type;
        };
      };

      // function
      struct tail
      { template<class c>
        struct code
        { typedef /*..*/ type;
        };
      };
    };

is an instance of the class list_class. We can now implement a map function
that can manipulate any type of list_class:

    struct map
    { template<class list_class, class fun, class list>
      struct code
      { typedef typename
          select
          < list_class::is_empty::code<list>::type
          , list_class::empty
          , list_class::cons::code
            < fun::code
              < list_class::head::code<list>::type
              >::type
            , map::code<list_class, fun,
list_class::tail::code<list>::type>::type
            >::type
          >::type;
      };
    };

(Like I said, the above function assumes lazy expansion, so the actual
implementation would look somewhat more complicated, but would still have the
same flexibility.)

Using this technique, it is possible to implement list manipulation functions
that can manipulate type lists of any other template metaprogramming library.
In order to take advantage of the functionality, you simply have to write the
algebraic type adapter for the list.

For example, in Loki, type lists are represented using these namespace scope
constructors:

    template <class T, class U>
    struct Typelist
    {
       typedef T Head;
       typedef U Tail;
    };

    class NullType {};

Let's now wrap them into an algebraic type:

    struct loki_type_list
    { typedef Loki::NullType empty;

      struct cons
      { template<class head, class tail>
        struct code
        { typedef Loki::Typelist<head,tail> type;
        };
      };

      struct is_empty
      { template<class c>
        struct code
        { typedef boolean<is_same<c,empty>::value> type;
        };
      };

      struct head
      { template<class c>
        struct code
        { typedef typename c::Head type;
        };
      };

      struct tail
      { template<class c>
        struct code
        { typedef typename c::Tail type;
        };
      };
    };

Unfortunately, I have to stop now, because I have other duties. I may have
something to say about your other points.