racketcontract

recursive contract like Typed Racket's 'Rec' type

Typed Racket's Rec type is an easy way to make recursive types:

#lang typed/racket/base

(define (deep (n : Integer)) : (Rec T (U Integer (List T)))
  (if (zero? n)
    n
    (list (deep (- n 1)))))

Is there a similar way to make a recursive contract? Racket's recursive-contract is not the same.

Solution

  • Contract expressions are just expressions! You can write a macro that takes input like Typed Racket's Rec and replaces the "recursive identifier" with a self-reference.

    Here's an example rec/c combinator, where (rec/c id ctc) expands to ctc with all occurrences of id replaced with (recursive-contract id).

    #lang racket/base
(require racket/contract (for-syntax racket/base syntax/parse))

(define-syntax-rule (rec/c t ctc)
  (letrec ([rec-ctc
            (let-syntax ([t (syntax-parser (_:id #'(recursive-contract rec-ctc)))])
              ctc)])
      rec-ctc))

(define/contract (deep n)
  (-> integer? (rec/c t (or/c integer? (list/c t))))
  (if (zero? n)
    n
    (list (deep (- n 1)))))

(deep 4)

    Note: the pattern _:id matches any use of t as an identifier.