[racket] fingertree / nested datatype

On 04/11/2013 08:51 AM, Sam Tobin-Hochstadt wrote:
> Yes, an explicit struct involves an explicit indirection, and thus
> produces a regular tree.

Thanks Sam. I'm glad I asked the question. I guess I did manage to bump
up against a limitation of the type system on my first time out.

And thanks to Eric for showing me a way around. Bummer that this adds a
spurious struct at runtime. Sam, I think the reason people are pressing
the question is that intuitively it appears as though the type system
would be appeased by a "phantom" struct for the indirection (which
didn't allocate anything at runtime), which would be just as good as a
non-regular datatype. Maybe the catch is in the subtype cases you mentioned?

Since I'm to naive to add anything intelligent myself, I'll give the
references for anyone interested:

Hinze and Patterson use nested (aka non-regular) datatypes in, "Finger
trees: a simple general-purpose data structure," J. Functional
Programming, they point to this reference on the topic: Bird, R. and
Meertens, L. (1998) Nested datatypes.

Hinze in Haskell:

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

Tommy McGuire shows it in Java like this:

public static class Deep<T> extends FingerTree<T>
  {
    public final Digit<T> left;
    public final FingerTree<Node<T>> spine;
    public final Digit<T> right;
    ...
  }

here:
  http://maniagnosis.crsr.net/2010/11/finger-trees.html
  http://maniagnosis.crsr.net/2010/12/measured-finger-trees.html

Thanks again.

-- 
Anthony Carrico

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
URL: <http://lists.racket-lang.org/users/archive/attachments/20130411/bc07a261/attachment.sig>