Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-08-01 18:35:32

----- Original Message -----
From: "Fernando Cacciola" <fcacciola_at_[hidden]>

> I think that your arguments above are correct but incomplete. Let me
> explain:
>
> You are saying that mutating operations have different complexities on
> different data structures, which is correct as we all know, and that those
> complexity differences are irrelevant for FP (funtional programming).
> So far I agree. FP don't have truly mutating operations, only 'generative'
> operations, which are not the same.

No, I'm saying the entire structure has to be copied regardless.  It is not a
case of mutation at all--this is 'by value' modification pure and simple.

> If I understood you and Andrei correctly, generative operations won't
> benefit significantly from different data structures.
> Let's say I also agree here by taking your word for it.
>
> But that's not all...
>
> Different data structures have also different non-mutating and
> non-generative operation complexities.
> For instance:
>
> Vectors and Matrices have O(1) Access and Omin-Directional traversal.
> Singly-connected Lists and Directed Graphs have O(N) Access and
> Uni-Directional traversal.
> Doubly-connected Lists and Undirected Graphs have O(N) Access and
> Omni-Directional traversal
> Balanced-Trees have O(logN) Search  and Multi (but not necessarily
> Omni)-Directional traversal.

Okay, I will reiterate my point.  From the beginning of a container, a vector
has O(1) access time vs. a cons-style list that has O(n).  This is a question of
elegance vs. efficiency, because the vector will *always* be faster in every
type of operation.  The question is thus:  does the inefficiency of arbitrary
random access on a cons-style list significantly affect its performance?  If so,
why are we using cons-style lists at all?  If not, why are we using vectors at
all?

BTW, this argument has never been about non-sequence containers such as trees
and that ilk.  IMO, these types of containers apply only in a very limited
sense.  1) If the data must be in a tree structure, than the tree structure
itself must have some meaning.  This meaning gets lost every time that the tree
is converted into a sequence, and that *vastly* decreases the number of
'generic' sequence algorithms that apply.  Also, the algorithms that actually do
apply will likely be specialized anyway for efficiency reasons.  E.g. the STL
searching algorithms vs. the std::map's member functions.

> Furthermore, some specific structures support traversals which are just not
> supported at all by other structures.
> For example, Cycles support "Circulation" (that is, you can traverse all the
> elements of the sequence regardless of where you start).

All of these things can be implemented on top of a vector or a cons-style list.

> The question, I think, would be this: Do these differences in Access and
> Traversal Capabilities matter for Functional and/or Compile-Time
> programming?

Traversal capabilities are entirely defined in terms of what you want to do.  If
you define the capability, it will work--regardless of the underlying sequence
type.  Access times may well be relevant--and only realistic examples can prove
this.  If so, than vectors would suffice for every *sequencial* list.

> I understand Andrei suspicion and his appropriate request for sound examples
> in order to help answer the above.
> I myself, *a priori*, find hard to believe that such fundamental
> abstractions are useless in a different computational model. Their different
> mutating/generative properties might be irrelevant, but not their different
> access capabilities .

The only relevance here is speed of random access.  Everything else is
implementable either way.  As far as "fundamental abstractions" are concerned,
there is _no such thing_ in this medium.  The abstractions _haven't_ been proven
to be useful of 50+ years.

> I won't come up with a sound example in the short/mid term mainly because I
> might not find the need for it myself, but I think it will come eventually
> once MPL becomes widely used.
>
> Off the top of my head, I imagine that I could hard-code meta-graphs (not
> list-like nor tree-like) to express some relation between types (say,
> promotion rules), and code up special iterators so as to use MPL algorithms.
> Maybe MPL is not directly up to graph-related algorithms right now, probably
> because STL isn't either; but such extensions are likely to be easy to build
> upon the current model just like the BGL is built upon STL concepts.
> This could prove that the multiplicity of data-structures and the generic
> iterator-oriented algoritms were a good choice.

This is the kind of ideal that scares me.  It may well happen, but I think many
people have a mindset that this or that *might* be possible based on the
abstraction provided by the MPL.  IMO, you have to be careful when you look so
far ahead without a relatively clear path outlined.

> > Given that this is the case, the most efficient solution would be to
> always use
> > a tuple-like (i.e. vector-like) container that can hold a huge number of
> > elements.  On the other hand, the most extensible solution would be to use
> a
> > cons-style list.  One or the other is fine, but both is unnecessary.
> >
> I find this a bit odd: You are saying yourself that there are at least two
> possibilities with clearly different properties, but you conclude that even
> then, having both at the same time is unnecessary. How is that?
> If on one situation I only need to *look at*  a fixed, hard-coded sequence,
> I would like to use a tuple-like since it's efficient.
>
> If on a different context I need to *generate* a sequence I would use a
> cons-style list because it's flexible.
> Why wouldn't I want to have the two options to choose from?

A cons-list is no more *flexible* than a vector-like sequence.  It is only more
extensible in terms of it's own implementation.

Paul Mensonides