I couldn’t help myself. So here is 90% of what John proposed in HtDP’s ISL+
language. Exercise for the reader: fix the failing tests.
#lang htdp/isl+
;; long division
;; Trace = [cons N [cons N [Listof [List N N]]]
;; N N -> Trace
;; compute the trace for the division of x and y
;; example, worked
;; 5432 : 12 = 452
;;-48
;;--
;; 63
;; -60
;; --
;; 32
;; -24
;; --
;; 8
;; =
(check-expect (long 5432 12) (list 452 8 (list 54 48) (list 32 24)))
(define (long x y)
(local ((define x-as-digits (number->digits x))
(define result (long-helper (list (first x-as-digits)) (rest
x-as-digits) y))
(define quotient (digits->number (first result))))
(list quotient (second result))))
;; [Listof Digit] [Listof Digit] N -> Trace
;; compute the trace of a long division of (digits->number (append fst-digits
rest-digits)) by y
(check-expect (long-helper '(5) '(4 3 2) 12) (list 452 8 (list 54 48) (list 32
24)))
(define (long-helper fst-digits rest-digits y)
(local ((define fst-number (digits->number fst-digits)))
(cond
[(< fst-number y)
(if (empty? rest-digits)
(list '() fst-number)
(long-helper (snoc fst-digits (first rest-digits)) (rest rest-digits)
y))]
[(= fst-number y) (list (list 1) 0)]
[else (local ((define next-digit (subtract-often-enough fst-number y))
(define remainder (- fst-number (* next-digit y)))
(define result (long-helper (list remainder) rest-digits
y))
(define quotient (first result))
(define remainder2 (second result)))
(list (cons next-digit quotient) remainder2))])))
;; N N -> [List N N]
;; subtract y from x until x < y
(check-expect (subtract-often-enough 54 12) 4)
(define (subtract-often-enough x y)
(cond
[(< x y) 0]
[else (+ (subtract-often-enough (- x y) y) 1)]))
;; [Listof X] X -> [Listof X]
;; add x to end of l
(check-expect (snoc '() 1) '(1))
(check-expect (snoc '(1) 2) '(1 2))
(define (snoc l x)
(append l (list x)))
;; [listof Digit] -> N
;; render the given sequence of digits as a number
(check-expect (digits->number '(1 2 3)) 123)
(define (digits->number digits)
(string->number (implode (map number->string digits))))
;; N -> [Listof Digit]
;; split number into sequence of digits
(check-expect (number->digits 123) '(1 2 3))
(define (number->digits x)
(map string->number (explode (number->string x))))
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
