How to create a recursive contract - racket/racket GitHub Wiki

You can use flat-rec-contract to build a recursive flat contract.

As an example, let's say a value is considered a tree if it's either

• a symbol, representing content of a leaf node
• a list, representing an internal node, where
  • the first element of the list must be a symbol, representing content of the internal node, and
  • other elements must be trees, representing subtrees of the internal node.

A flat contract testing if a value is a tree tree/c can be defined as follows:

(define tree/c (flat-rec-contract t
                                  (or/c symbol?
                                        (cons/c symbol? (listof t)))))

Following shows usage of the contract that we defined.

EXAMPLES: WELL-FORMED TREES

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

       S1 

(tree/c 'S1) ;-> #t

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

        S1
        |
        S2

(tree/c '(S1 S2)) ;-> #t

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

       S1
   ____|____
   |   |   |    
   S2  S3  S4  
     __|__
    |     |
   S3-1  S3-2
  __|___
 |      |
 S3-1-1 S3-1-2   

(tree/c '(S1 S2 (S3 (S3-1 S3-1-1 S3-1-2) S3-2) S4)) ;->#t

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

COUNTEREXAMPLES: MALFORMED TREES

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(tree/c '((a b))) ;#->f

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(tree/c '((a b) (c d))) ;#->f

|#