gistfile1.rkt

#lang typed/racket

;; from Wikipedia

(struct: (A B) :<: ([left : A] [right : B])
         #:transparent)
(struct: Epsilon ())

(define-type (Nested A)
  (U (:<: A (Nested (Listof A))) Epsilon))

(: nested (Nested Integer))
(define nested
  (:<: 1 (:<: (list 2 3 4) (:<: (list (list 4 5) (list 7) (list 8 9)) (Epsilon)))))

;; inference loops forever for this one...
(: nested-length (All (A) ((Nested A) -> Integer)))
(define (nested-length n)
  (if (Epsilon? n)
      0
      (add1 ((inst nested-length (Listof A)) (:<:-right n)))))

(provide nested nested-length :<: Nested Epsilon)