[racket] Cyclic data structures in Typed Racket

From: Benjamin Greenman (blg59 at cornell.edu)
Date: Mon Sep 29 14:00:12 EDT 2014

To be sure: Is there any TR analog to this OCaml code, initializing a
cyclic, 3-element list? I've tried using letrec in TR, but the typechecker
yells at me even if I annotate the a,b,c,d.

# type 'a mylist = Nil | Cons of 'a * 'a mylist;;
type 'a mylist = Nil | Cons of 'a * 'a mylist
# let mylist =
    let rec a = Cons(1, b)
    and     b = Cons(2, c)
    and     c = Cons(3, d)
    and     d = Cons(4, a) in
    a;;
val mylist : int mylist = Cons (1, Cons (2, Cons (3, Cons (4, <cycle>))))

On Mon, Sep 29, 2014 at 12:52 PM, Sam Tobin-Hochstadt <samth at cs.indiana.edu>
wrote:

> Ah, if you want to create truly cyclic structure with no base case
> like this, then you'll have to do more work. Either you'll need to
> expand the type of the `x` field in `foo` to allow an initial value,
> or you'll need to create a dummy `foo` with that extended type, and
> then copy the cyclic data once you've created it to a new version of
> `foo`, using hash tables to track cycles. That's basically how
> `shared` works, although I haven't tried implementing it in TR and it
> might not be possible.
>
> Sam
>
> On Mon, Sep 29, 2014 at 12:33 PM, Konrad Hinsen
> <konrad.hinsen at fastmail.net> wrote:
> > Sam Tobin-Hochstadt writes:
> >
> >  > I recommend doing the mutation yourself, and not using `shared`.
> >  > That's the most obvious solution.
> >
> > Not for me, unfortunately, but probably I am missing something
> > obvious.
> >
> > Here's explicit mutation in untyped Racket:
> >
> >    #lang racket
> >
> >    (struct foo (x) #:mutable)
> >    (struct bar (x))
> >
> >    (define f (foo (void)))
> >    (define b (bar f))
> >    (set-foo-x! f b)
> >
> >    (eq? (bar-x b) f)
> >    (eq? (foo-x f) b)
> >
> > That works fine. Moving to Typed Racket, this is rejected by the type
> > checker because (void) is of type Void.  Since I need a bar to make a
> > foo and a foo to make a bar, I don't see how I can ever initialize my
> > foo structure.
> >
> >  > The reason that your `require/typed` doesn't work is that it creates
> >  > new versions of the placeholder functions, but those aren't the ones
> >  > that `shared` uses internally, so Typed Racket doesn't use the types
> >  > you've given.
> >
> > That makes sense, thanks for the explanation!
> >
> > Konrad.
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140929/152cdf29/attachment-0001.html>

Posted on the users mailing list.