[racket] fingertree / nested datatype

On Thu, Apr 11, 2013 at 9:18 AM, Anthony Carrico <acarrico at memebeam.org> wrote:
> 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?

This is indeed something we've run into before. See section 4.2 of
this paper: http://www.ccs.neu.edu/racket/pubs/sfp10-kth.pdf

We could probably also introduce something like Haskell's `newtype` to
address this, as you suggest, but it's not obvious to me how that
would work in interoperation with untyped code, for example.  There
are a lot of open questions here, and I think we can eventually give
better answers to them than we currently have, but we don't have them
yet.

Sam