Cart
[Home] [By Thread] [By Date] [Recent Entries]
> Do you have a feel for whether Java is powerful enough to implement finger
> trees in?
I have used Java only occasionally and even that was many years ago.
Good support of generics is required for the inplementation of a
finger tree. In particular, a finger tree is a recursive structure.
The following class definition (C#):
public class DeepFTree<T> : FTree<T>
{
protected Digit<T> frontDig;
protected FTree<Node<T>> innerFT;
protected Digit<T> backDig;
. . . . . . . . . . .
}
defines a DeepFTree<T> to have an "innerFT" member, which is of type
FTree<Node<T>>
This "innerFT" may have its own "innerFT" of type FTree<Node<Node<T>>>
and this second "innerFT" may have its own "innerFT" of type
FTree<Node<Node<Node<T>>>>,
... , etc.
The types Node<T>, Node<Node<T>>, Node<Node<Node<T>>>, ...
will need to be created at runtime, as it is impossible to know at
compile time how deep the type nesting will need to be (although in
the case of a finger tree we know this will be close to log2(N), where
N is the number of leaf nodes of the tree).
So, I am sure this cannot be achieved with C++ generics, which is
supported entirely at compile time. As for Java, I am not even aware
if it has any generics support at all.
A Scala implementation of the finger tree object is said to exist.
--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
On Sun, Sep 21, 2008 at 11:55 PM, Rick Jelliffe
<rjelliffe@a...> wrote:
> Dimitre Novatchev wrote:
>>
>> A good example of a problem that can be completely eliminated: use a
>> Finger-Tree-based sequence for all sequences, then there is no need to
>> worry
>> to convert from one sequence type to another (of course, the items still
>> need to be of the same type). Not to mention the gains in efficiency.
>>
>
> Do you have a feel for whether Java is powerful enough to implement finger
> trees in?
>
> Cheers
> Rick Jelliffe
>
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] |
