recursion - Typed Racket: Natural Numbers -

recursion - Typed Racket: Natural Numbers -

i have solve problem unique definition of natural numbers:

(define-type nat (u 'zero succ)) (define-struct succ ([prev : nat]) #:transparent)

so basically, 0 = 'zero, 1 = (succ 'zero), 2 = (succ (succ 'zero)).... etc.

using form, without converting them integers, have write recursive functions add, subtract, , multiply natural numbers. add together function i've tried this

(: nat+ : nat nat -> nat) (define (nat+ n m) (match '(n m) ['('zero 'zero) 'zero] ['((succ p) 'zero) n] ['('zero (succ p)) m] ['((succ p) (succ t)) (nat+ p (succ m))]))

but error

p: unbound identifier in module in: p.

does have advice writing type of recursive function.

the problem utilize of quoting. when quote list, '(n m), doesn't mean "a list containing whatever n , whatever m - means list containing literal symbols n , m. quoting things ignores whatever bindings have , gives literal interpretation of whatever quote. when match '(n m), not matching list containing values n , m bound to, matching list containing symbols n , m. similar problems exist usage of quote everywhere else - in pattern matching clauses have utilize list instead of quote behavior expect:

(: nat+ : nat nat -> nat) (define (nat+ n m) (match (list n m) [(list 'zero 'zero) 'zero] [(list (succ p) 'zero) n] [(list 'zero (succ p)) m] [(list (succ p) (succ t)) (nat+ p (succ m))]))

note utilize of quote remains in 'zero - because zero not binding value, you're using literal symbol zero it's quoted.

additionally, can create more succinct using define/match form:

(: nat+ : nat nat -> nat) (define/match (nat+ n m) [('zero 'zero) 'zero] [((succ p) 'zero) n] [('zero (succ p)) m] [((succ p) (succ t)) (nat+ p (succ m))])

this form lets match against arguments directly, instead of having pack them list first.

recursion racket typed-racket