Gray binary codes

gray.rkt

#lang racket/base

;; Gray binary code, from TAOCP 7.2.1.1.
;;
;; Gray codes are sequences where adjacent elements are different in only one position.
;;
;; The gray codes of length n can be generated with the following recursive rules:
;;
;;    G_0 = epsilon
;;    G_{n+1} = 0 G_n, 1 ((G_n)^r)
;;
;; where ^r is notation for sequence reversal.
;;
;; Let's write this in code.

;; gamma: number -> (listof string)
(define (gamma n)
  (cond
    [(= n 0)
     (list "")]
    [else
     (define gamma_n-1 (gamma (sub1 n)))
     (append (for/list ([s gamma_n-1])
               (string-append "0" s))
             (for/list ([s (reverse gamma_n-1)])
               (string-append "1" s)))]))

;; For example:
(gamma 4)