>> So we can now write SplayTree, HeapTree, SearchTree, etc as subclasses
>> of Tree. But the thing is... you can only Union() two trees together if
>> they are THE SAME TYPE of tree. So you can take the union of two
>> SplayTrees, or the union of two HeapTrees, but NOT the union of a
>> SplayTree and a HeapTree.
>
> Well, this can easily be solved by making Union non-abstract and having
> it call more primitive abstract functions; e.g (using pseudocode as I
> currently don't have C# syntax memorized):
>
> public abstract class Tree
> {
>
> public abstract Tree copy();
> public abstract Iterator<Leaf> leaves();
> public abstract void addLeaf(Leaf l);
>
> public final Tree Union(Tree other)
> {
> Tree newTree = this.copy();
> foreach(Leaf i in other.leaves())
> newTree.addLeaf(i);
> }
> }
>
> There. Problem solved.

Note that taking the union of (say) two heap trees is a O(log N) 
operation, whereas what you just wrote is O(N).

You can, of course, NOT write an abstract interface, and just write a 
concrete Union() method [with a different type signature] for each 
concrete Tree class. That works just fine. [But now you can't write code 
that works over any Tree type and expect to do unions.]

But anyway. The example illustrates the problem. Taking the Bind() of 
two different monads isn't even *defined*. There's no sensible answer. 
So until I can find a solution to that...

Post a reply to this message