Hacker News Reader

Comment by harpocrates | Hacker News Reader

This is a fun data structure to implement in Haskell, and I've always been curious about how one would do it in C++, largely due to the fact that

    data FingerTree a = Empty
                      | Single a
                      | Deep (Digit a) (FingerTree (Node a)) (Digit a)

Has polymorphic recursion in the last case. What would be the C++ approach for dealing with this sort of thing? Pass in a compile time integer to represent the level of nesting?

View on HN

I've written this several times in several ways using C++ (and I'll probably write it at least once more to make it better). In an early version I used an integer level as you came to, but it made the compiler very unhappy as it recursively tried to expand nested types at compile time (it couldn't figure out the recursive types would terminate in practice). Max template recursion of 256 if I remember correctly, even though you'd never instantiate past 45 or so on any machine in the world.

In a later version, I implemented the specializations as inheritance on the abstract FingerTree base class (verbose, but it works), and I added Leafs and Nodes. Leafs are FingerTrees that hold your data, and Nodes are FingerTrees that point to other FingerTree instance. This dodges the recursive types problem. I don't know much Haskell, but I think it would be the C++ equivalent of:

    data FingerTree a = EmptyLeaf
                    | SingleLeaf a
                    | DoubleLeaf a a
                    | TripleLeaf a a a
                    | EmptyNode
                    | SingleNode (FingerTree a)
                    | DoulbeNode (FingerTree a) (FingerTree a)
                    | TripleNode (FingerTree a) (FingerTree a) (FingerTree a)
                    | FingerSpine (FingerTree a) (FingerTree a) (FingerTree a)

Virtual methods on each specialization took the place of pattern matching. Not super elegant.

When traversing the tree, I think you'll need at least one branch/virtual method dispatch to determine the type of the child node.

Given that, you could create a templated subclass for each type in the grammar, then instantiate it with the number of children. Eg:

template<N> class Node : TODO { type 'N'; int const count N; Node a[N]; }

Allocating Node<2> is a single malloc. You can add static asserts to get things like Node<4> to fail at compile time, change the c style array to std::array<Node, N> to get bounds checks, and so on.

At that point, you can get arbitrarily fancy with custom allocators, inlining the type to be stored in the tree, etc.

[edit: Note that my solution kinda sucks, because you need to pay for a virtual method dispatch to run code that has N compiled in, and I also rolled my own reflection with instance variables, so I'm bloating each node by two words instead of one, and also breaking constant propagation in the caller code.

Removing the implicit vtable or the extra instance variables is an exercise left to the reader.]

I think you'd have to use a pointer and allocate on the heap. Under the hood I think that's essentially what the compiled Haskell code would do.

The polymorphic recursion allows for compile-time checking of the invariant that "the left and right wings at depth n are 2-3 trees of depth n". In C++, I think you would forgo a compile-time check of that invariant and just write code that maintains it instead.

Reply on news.ycombinator.com