From: jbn@lulea.trab.se (Johan Bengtsson)
Newsgroups: comp.std.c++
Subject: Re: Recursive templates
Date: 18 Nov 92 12:00:57 GMT
Organization: Telia Research AB, Aurorum 6, 951 75 Lulea, Sweden
X-Newsreader: Tin 1.1 PL4

pjl@cs.uiuc.edu (Paul Lucas) writes:
: In <5225@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
: 
: >pl2440@meibm31.cen.uiuc.edu (Paul Jay Lucas) writes:
: >: In <1992Nov16.220526.21566@borland.com> pete@borland.com (Pete Becker) writes:
: >: 
: >: >In article <83733@ut-emx.uucp> jamshid@emx.cc.utexas.edu (Jamshid Afshar) writes:
: >: >>Has ANSI decided anything about the expansion of a recursive template
: >: >>definition?
: >: 
: >: *****>	Has anyone got a *real* justification for this?  This is a very
: >: 	obfuscated way of writing factorial.
: 
: >You should be able to base binary trees on unary trees (which are degenerate
: >trees more commonly known as linked lists), trinary trees could be
: >based on binary trees, and n-ary trees could be based on (n-1)-ary trees.
: 
: *****>	I'm not convinced.  List, or unary trees as you call them, serve
: 	different purposes than do binary trees.  A List class would
: 	have "list-type" operations on it;

Agreed.  A full-blown List class is more than a unary tree.  Still,
the operations on unary trees map nicely to the operations on lists:
Child(0) --> next(), parent() --> prev(), top() --> first(),
leftMostBottom() --> last(),
in case you really want to integrate the List and Tree concepts.

: a BinaryTree class could have
: 	LeftChild() and RightChild() functions and wouldn't have
: 	list-type operations.

In this context, a binary tree is instantiated as GenericTree<2>,
and has Child(0) and Child(1) functions instead.  Deriving class
BinaryTree from GenericTree<2> is trivial. BinaryTree::LeftChild()
and RightChild() just forwards the request to GenericTree<2>::Child().
I would think it is difficult to make GenericTree<2> as efficient
as a hand-crafted class BinaryTree though (but that is not my point).

: 	
: 	Anyway, a Tree<class T,int noOfChildren> class can be
: 	implemented nicely without recursive templates; I don't see that
: 	the recursive definition buys you anything.

A bit stricter type checking.  Typing errors are caught at compile-time
rather than at run-time.  I sure don't need this for may everyday work,
but who knows what tomorrows programmers might need?

You lose performance though; at least I think that the recursive version
is difficult to get as fast at child lookup.

: >N-dimension matrixes should be possible to base on N-1-dimension matrixes,
: >with 1-dimensional matrixes (arrays) as the recursion-stopper.
: 
: *****>	What's a 5x3 matrix based on?  4x2, 3x1, 2x(oops!).

No, no.

You don't parameterize on the _size_ of the matrixes, you parameterize
on the number of dimensions.  5x3, 4x2 and 3x1 are all of type
GenericMatrix<2>.  Parameterizing (non-recursively) on the size in each
dimension may be an a useful exercise, if you do a lot of matrix work
(I don't).

Whether these recursive template definitions are really useful in
practical work is an open issue, but as someone pointed out, current
template compilers (some) support it, and why not?  It does give added
power to detect type errors at compile-time, rather than at run-time.

-- 
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------
Newsgroups: comp.std.c++