Re: [boost] FC++ examples?

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-03-03 14:49:13

On Wed, Mar 03, 2004 at 08:03:20PM +0100, Giovanni Bajo wrote:
> Are there a couple of examples showing real-life C++ problems that can be
> solved with the help of FC++?

The paper
   FC++: Functional Tools for OO Tasks
on the FC++ web page talks about how to use FC++ in the implementation
of common OO design patterns.  The web page also points to the XR
library, which used FC++'s infrastructure (especially lazy evaluation 
support) to build an arbitrary-precision numeric library.

> help, within a normal C++ program. The quicksort example was very cool, but it
> turns out that the generated code is too slow to be used for everything. If I
> need FP everywhere, I change language.

The quicksort example and also the tree iterator example I posted are
interesting.  I posit that there are cases where shorter/easier code may
be more valuable than code that wins on raw performance, but perhaps
this is too-unpopular an idea among C++ people.

In any case, I failed to extol other (non-obvious) virtues of the
quicksort example.  A lazy quicksort can be used to calculate minimum
values efficiently, for example.  Given an unordered list of elements,
   head( quicksort(l) )
yields the minimum element in O(N) time.  Indeed, this generalizes to a
(constant) M elements:
   l = quicksort(l);
   x = at(l,0);
   y = at(l,1);
   z = at(l,2);
finds the smallest 3 elements in O(N) time.  This can't be done with a
standard quicksort(); since the standard quicksort is non-lazy, calling
it immediately costs you O(N^2) (worst case) time.  As a result, you'd
need to write a separate algorithm for finding the minimum M elements.
The lazy quicksort does work on demand, so you only pay for those
elements you choose to actually inspect.

Again, the overall point is that some of the "slower" elements of FC++
can offer you trade-offs: choices you wouldn't otherwise have.  Lists
and lazy evaluation may not always be the best choice for performance-
critical portions of applications, but for other cases they can often
yield novel and/or simpler designs.

-- 
-Brian McNamara (lorgon_at_[hidden])