arvb.net

Representing Naturals

2 min read

Using functional programming, we are able to represent any information as data by using the appropriate templates and methods. For example:

Imagine you have a programming language that does not include natural as a primitive. If you have access to other primitives such as cons and string (to use Racket as an example), you can create a new definition for naturals using the How To Design Data templates.

;; NATURAL is one of:
;; - empty
;; - (cons "!" NATURAL)
;; interp. a natural number, the number of "!" in the list is the number
(define N0 empty)         ;0
(define N1 (cons "!" N0)) ;1
(define N2 (cons "!" N1)) ;2
(define N3 (cons "!" N2)) ;...
(define N4 (cons "!" N3)) 
(define N5 (cons "!" N4)) 
(define N6 (cons "!" N5)) 
(define N7 (cons "!" N6)) 
(define N8 (cons "!" N7)) 
(define N9 (cons "!" N8))
 
;; These are the primitives that operate NATURAL:
(define (ZERO? n) (empty? n))  ; Any         -> Boolean
(define (ADD1 n) (cons "!" n)) ; NATURAL     -> NATURAL
(define (SUB1 n) (rest n))     ; NATURAL[>0] -> NATURAL
 
(define (fn-for-NATURAL n)
	(cond [(ZERO? n) (...)]
		  [else
			  (... n
				  (fn-for-NATURAL (SUB1 n)))]))
 
;; NATURAL NATURAL -> NATURAL
;; produce a + b
(check-expect (ADD N2 N0) N2)
(check-expect (ADD N0 N3) N3)
(check-expect (ADD N3 N4) N7)
 
;(define (ADD a b) N0) ; stub
 
 
(define (ADD a b)
	(cond [(ZERO? b) a]
		  [else
			(ADD (ADD1 a) (SUB1 b))]))
 
;; NATURAL NATURAL -> NATURAL
;; produce a - b
(check-expect (SUB N3 N0) N3)
(check-expect (SUB N4 N1) N3)
(check-expect (SUB N8 N5) N3)
 
#;
(define (SUB a b) N0)
 
(define (SUB a b)
	cond [(ZERO? b) a]
		[else
			(SUB (SUB1 a) 
				 (SUB1 b))]))

In ADD, the function adds one to to A and subtracts one from B until B is empty. Think of this as making a one-by-one transfer from B to A.

On the other hand, SUB removes one from both A and B but stops when B is empty, leaving whatever is left for A.

Graph View