[boost] LL: Case study

From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-03-29 13:34:26

Hi,

May I congratulate Jaakko and Gary for the inclusion of LL in Boost.

Aleksey requested that we reminded him of any important omissions from the review period that were not adressed in the review result. In this context, may I request that Jaako and Gary resolve the scoping issue in one of two ways:

* Either scoped lambda-expressions are implemented, as in FC++, FACT! and Phoenix
* Or it is documented more clearly that the lambda-expressions are not scoped

Although the review period is over, I hope the discussion will continue a bit more, because I think it has been fruitful so far.

To improve my understanding of functional programming in C++, I have tried to solve a set of problems that are prototypical for functional programming.

I simply took my "Functional programming with Miranda" book, and picked some examples at random, and tried to reimplement them in C++, using LL version 2. Obviously, I did not compile any of this.

Problem 1: Implement map, which applies a function to each element of a container, and returns a new container with the resulting values.

First try:

template<typename X>
X map(X const & x, boost::function f) {
  X result;
  for_each(x.begin(), x.end(), result.push_back(f(_1)));
  return result;
}

Doesn't work. We have to use bind (syntax from memory):

template<typename X>
X map(X const & x, boost::function f) {
  X result;
  for_each(x.begin(), x.end(), 
    bind(&X::push_back, result, f(_1)));
  return result;
}

Then, it is arguably better to use transform:

template<typename X>
X map(X const & x, boost::function f) {
  X result(x.size());
  transform(x.begin(), x.end(), result.begin(), f);
  return result;
}

So, LL did not really win this one, because we do not have the syntax, we would like. Oh well.

Problem 2: From a container x, create the container with each element squared.

First, we try this:

template<typename X>
X square_container(X const & x) {
  return map(x, _1 * _1);
}

That's pretty neat, but it doesn't work, because _1 * _1 is not compatible with boost::function.

Hmm, so we have to use the strange unlambda:

template<typename X>
X square_container(X const & x) {
  return map(x, unlambda(_1 * _1));
}

It would be nicer if LL worked together with boost::function.

If that is not possible, may I then suggest that the name of "unlambda" is changed? Technically, it seems that the semantics of the function is related to beta-reduction as known from lambda calculus. That might be a bit too technical a name -- maybe "instantiate" would be better?

Problem 3: Implement concat, which joins a container of containers into a single container.

First, let's wrap up accumulate in a functional style to get the traditional "fold":

template<typename L>
L::value_type fold(boost::function op, L::value_type c, L const & l) {
  return accumulate(l.begin(), l.end(), c, op);
}

Now, it could be nice to do this:

template<typename L>
L::value_type concat(L const & x) {
  boost::function append = 
    L::value_type l(_1), 
    l.insert(l.end(), _2.begin(), _2.end()), 
    l; // Or maybe "return l;"
  return fold(append, L::value_type(), x);
}

But we do not have local variables in LL, so it is not possible to define append like that. Maybe it is possible to use the new/delete stuff, but I wouldn't know how to write that, and I strongly think it would be bad style.
Instead, I just do this:

template<typename L>
L append(L const & l1, L const & l2) {
  L result(l1);
  result.insert(result.end(), l2.begin(), l2.end();
  return result;
}

template<typename L>
L::value_type concat(L const & x) {
  return fold(append, L::value_type(), x);
}

Conclusion: Local variables would help.

Problem 4: Implement merge-sort.

First we need a routine to merge two sorted lists in order:

template<typename L>
L merge(L const & l1, L const & l2) {
  if (l1.size() == 0) return l2;
  if (l2.size() == 0) return l1;
  return if_(l1[0] < l2[0])[
           append(L(1, l1[0]), 
                  merge(L(l1.begin() + 1, l1.end()),
                        l2
                  )
           )
         ].else_[
           append(L(1, l2[0]), 
                  merge(l1,
                        L(l2.begin() + 1, l2.end())
                  )
           )
         ];
}

In this example, LL does well. The syntax is bareable, and the code is reasonably clear. (Notice, however, that without append, we could not do this.)
The main problem is that it is inefficient as hell, since current C++ compilers probably can not optimize the temporary lists away like functional programming languages can today.
Instead, we are better off by implementing merge without recursion:

template<typename L>
L merge(L const & l1, L const & l2) {
  L result;
  L::const_iterator i1 = l1.begin();
  L::const_iterator i2 = l2.begin();
  while( i1 != l1.end() && i2 != l2.end() ) {
    if ( (*i1) < (*i2) ) {
      result.push_back(*i1);
      ++i1;
    } else {
      result.push_back(*i2);
      ++i2;
    }
  }
  result.insert(result.end(), i1, l1.end());
  result.insert(result.end(), i2, l2.end());
  return result;
}

So, LL does not even win this one.

Anyway, we are ready for the pretty sorting routine, even if it does not use LL:

template<typename L>
L merge_sort(L const & l) {
  if (l.size() <= 1) return l;
  int half = l.size() / 2;
  return merge( merge_sort(L(l.begin(), l.begin() + half))),
                merge_sort(L(l.begin() + half, l.end()));
}

This has obviously rotten performance due to excessive copying. You can not really blame LL for the performance issue, but it does illustrate that functional style programming in C++ is not as high-level as in functional programming languages. You have more responsibility to insure that performance is sufficient, because you can not rely on a clever optimizing compiler to weed out all the excessive copying. As expected, of course.

Greets,

Asger Alstrup Nielsen