Natural Number Encoding by Little Endian Binary List / 二進数リストによる自然数の符号化（LSB を先頭とするので逆順に見える）

binary-list-encoding.scm

;;;;
;;;; little endian binary list style
;;;;

(define (succ xs)
  (cond [(null? xs)     (cons 1 xs)]
        [(= (car xs) 1) (cons 0 (succ (cdr xs)))]
        [else           (cons 1 (cdr xs))]))

(define zero '())
(define one   (succ zero))    ; (1)
(define two   (succ one))     ; (0 1)     = #b10
(define three (succ two))     ; (1 1)     = #b11
(define four  (succ three))   ; (0 0 1)   = #b100
(define five  (succ four))    ; (1 0 1)   = #b101
(define six   (succ five))    ; (0 1 1)   = #b110
(define seven (succ six))     ; (1 1 1)   = #b111
(define eight (succ seven))   ; (0 0 0 1) = #b1000
(define nine  (succ eight))   ; (1 0 0 1) = #b1001
(define ten   (succ nine))    ; (0 1 0 1) = #b1010

(define (pred xs)
  (cond [(null? xs)       zero]
        [(null? (cdr xs)) zero]
        [(= (car xs) 1)   (cons 0 (cdr xs))]
        [else             (cons 1 (pred (cdr xs)))]))

(define (number->code n)
  (if (zero? n)
      zero
      (succ (number->code (- n 1)))))

;;;
;;; The quick version of number->code
;;;
(define (encode n)
  (cond [(zero? n) '()]
        [(even? n) (cons 0 (encode (quotient n 2)))]
        [else      (cons 1 (encode (quotient n 2)))]))

;;;
;;; inverse of the above.
;;;
(define (decode xs)
  (if (null? xs)
      0
      (+ (car xs)
         (* 2 (decode (cdr xs))))))