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
signature.asc
Description: OpenPGP digital signature
____________________ Racket Users list: http://lists.racket-lang.org/users
