practical-language-learning

accumulator-style

;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-advanced-reader.ss" "lang")((modname accumulator-style) (read-case-sensitive #t) (teachpacks ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp") (lib "batch-io.rkt" "teachpack" "2htdp") (lib "web-io.rkt" "teachpack" "2htdp") (lib "dir.rkt" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp") (lib "batch-io.rkt" "teachpack" "2htdp") (lib "web-io.rkt" "teachpack" "2htdp") (lib "dir.rkt" "teachpack" "htdp")) #f)))
(define-struct node [left right])
; A Tree is one of: 
; – '()
; – (make-node Tree Tree)
(define example
  (make-node (make-node '() (make-node '() '())) '()))

; Exercise 498
; Tree -> N
; measures the height of abt0
(check-expect (height.v2 example) 3)
(check-expect (height.v2 example) 3)

(define (height.v2 abt0)
  (local (; Tree N N -> N
          ; measures the height of abt
          ; accumulator s is the number of steps 
          ; it takes to reach abt from abt0
          ; accumulator m is the maximal height of
          ; the part of abt0 that is to the left of abt
          (define (h/a abt s m)
            (cond
              [(empty? abt) s]
              [else
               (max (h/a (node-left abt)
                         (add1 s) (add1 m)) 
                    (h/a (node-right abt)
                         (add1 s) m))])))
    (h/a abt0 0 0)))

; Exercise 499
; [List-of Number] -> Number
; product if a list numbers
(check-expect (product '(1 2 3)) 6)

(define (product l)
  (local ((define (p/a l n)
            (cond
              [(empty? l) n]
              [else (p/a (rest l) (* n (first l)))])))
    (p/a l 1)))


; Exercise 500
; [List-of Number] -> Number
; determines the number of items on a list
(check-expect (how-many '(1 3 4)) 3)

(define (how-many l)
  (local ((define (h/a l n)
            (cond
              [(empty? l) n]
              [else (h/a (rest l) (add1 n))])))
    (h/a l 0)))


; Exercise 501
; N -> Number
; adds n to pi without using +
(check-within (add-to-pi 2) (+ 2 pi) 0.001)

(define (add-to-pi n)
  (local ((define (atp/a n0 x)
            (cond
              [(zero? n0) x]
              [else (atp/a (sub1 n0) (add1 x))])))
    (atp/a n pi)))


; Exercise 502
; [NEList-of 1String] -> [NEList-of 1String]
; constracts a palindrome by mirroring
; the list around the last item
(check-expect
  (palindrome (explode "abcd")) (explode "abcdcba"))

(define (palindrome l)
  (local ((define (p/a l0 s)
            (cond
              [(empty? l0) (append (reverse (rest (reverse l))) s)]
              [else (p/a (rest l0) (cons (first l0) s))])))
    (p/a l '())))


; Exercise 503
; Matrix -> Matrix
; rotates a Matrix until the first
; coefficient of the first row differs from 0
(check-expect (rotate* '((0 4 5) (1 2 3)))
              '((1 2 3) (0 4 5)))
(check-expect (rotate.v2 '((0 4 5) (1 2 3)))
              '((1 2 3) (0 4 5)))

(define (rotate* M)
  (cond
    [(not (= (first (first M)) 0)) M]
    [(andmap (lambda (t) (= (first t) 0)) M)
     (error "all rows start with 0")]
    [else
     (rotate* (append (rest M) (list (first M))))]))

(define (rotate.v2 M0)
  (local (; Matrix ... -> Matrix 
          ; accumulator ...
          (define (rotate/a M seen)
            (cond
              [(empty? M) seen] ; Can this be simplified to (empty? M)
              [else (rotate/a (rest M)
                              (cons (first M) seen))])))
    (rotate/a M0 '())))


; Exercise 504
; [List-of Number] -> Number
; produces corresponding number
(check-expect (to10 '(1 0 2)) 102)

(define (to10 ld)
  (local ((define (to10/a l d e)
            (cond
              [(empty? l) d]
              [else (to10/a (rest l)
                            (+ (* (first l) (expt 10 e)) d)
                            (sub1 e))])))
    (to10/a ld 0 (sub1 (length ld)))))


; Exercise 505
; N [>=1] -> Boolean
; whether number is prime
(check-expect (is-prime? 3) #true)
(check-expect (is-prime? 6) #false)

(define (is-prime? n)
  (local ((define (is-prime/a s r)
            (cond
              [(= r 1) #true]
              [else (and
                     (not (= (remainder s r) 0))
                     (is-prime/a s (sub1 r)))])))
    (is-prime/a n (sub1 n))))


; Exercise 506
; accumulator-style version of map
(check-expect (map/a add1 '(1 2 3)) '(4 3 2))

(define (map/a f l)
  (local ((define (h/a f* l* seen)
            (cond
              [(empty? l*) seen]
              [else (h/a f*
                         (rest l*)
                         (cons (f (first l*)) seen))])))
    (h/a f l '())))