lethevertさんに言及いただいた 「Java(のGenerics)は(DのTemplateと比べて)便利だなあ」発言 ですが、 そういえば、この記事書いた後ひとに突っ込みもらって、用語の選択ミス等々で伝えたいことを 上手く伝えられてなかったっぽいと気づいたことを今思い出しました。 というわけで、今頃になってフォロー記事を書いてみます。
件の Finger Tree でも使われてましたが、純粋関数型データ構造を作るときに頻出のテクニックの一つとして、 "Non-uniform type" / "Non-uniform recursion" ていうのがあります （Nested datatype とか Polymorphic recursion とか別の名前で呼ばれることもあります）。 あ、まずその前に、Non- じゃない "Uniform type" / "Uniform recursion" っていうのは要するにごく普通の再帰的なデータ型/再帰関数 のことです。たとえばツリーとか。
class Tree<E> { E data; Tree<E> left, right; }Treeの定義にTreeが登場してる…つまり再帰的な定義なんですが、 この再帰の時に型パラメタの部分はいっしょ （Tree<E> の定義には Tree<E> を使っている） なことを指して、uniform と呼ばれています。
さて、Non-uniform recursion というのは…もうおわかりだと思いますが、 型パラメタを変えながら再帰すること。 例えば、「キュー Queue<E> を実装するのに、 Queue<List<E>> を使うとすごい高速！」 というファンキーな技があります。 （c.f. このPowerPoint の"Bootstrapped Queue"あたり。前９章の内容前提な上に口頭で補足するの前提な資料なので わかりにくいですが。スミマセン）
// Java
class Queue<E> { ... Queue<List<E>> impl; ... }
// D
class Queue(E) { ... Queue!(List!(E)) impl; ... }
// C++
template<typename E>
class Queue { ... Queue< List<E> >* impl; ... }
を使うには Queue ※本当かな？と思って実際にC++やDで書いてみる人向け注意。
単に↑のように再帰的にimplというメンバを定義するだけだと、implは使われないので実体化もされず、
無限ループもしません。
「型を変えて適当にキャストを挟み込む」とか「実際に実行時に使われる再帰の段数は大抵logオーダーなので、
32段くらいで強制的に再帰をストップするようなテンプレートを書く」とか無理矢理なんとかする手は
あるんですが、まあ不便ですよね、という。
何かimplを使うメンバ関数
（例えば、bool empty() { return !impl || impl->empty(); } とかなんとか）
を適当に実装して呼び出してみるとコンパイルが止まらなくなって楽しい気分になれます。
追記： ちゃんとしたサンプルとして Java版 Booststrapped Queue を
実装 sub/BtsQ.java
（遅延評価してないのであんまり意味ないけど）しました。
これを C++/D に移植してみるとコンパイルが止まらなくなって楽しい気分になれます。
追記の追記：バグってた！ので修正。