Last updated: Mon, 9 Mar 2015 16:19:54 -0400
HTDP/2e, Part V, Chapters 29-32, 34
Here are some slides about generative recursion.
Note: These slides are from a previous semester. We provide them because learning is often aided by looking at different presentations of the same material. However, previous iterations of the course had a different structure and different style requirements. Read these slides for their ideas only. When there are discrepancies, follow the rules of our current course.
Understand how some programs do not follow the "Shape of the program follows the shape of the data" theme of the course so far.
Understand how to write functions that utilize generative recursion.
consists of three pegs,
has an initial stack of discs on one peg,
where the discs are sorted such that the widest peg is at the bottom and the smallest at the top.
; An PegLabeling is a (make-pegs Peg Peg Peg) ; Represents a labeling of the physical Hanoi pegs (left, middle, right) ; as logical "source", "target", or "helper" pegs. (define-struct pegs (src tgt help)) ; A Peg is one of: ; - LEFT ; - MIDDLE ; - RIGHT ; Represents a physical Hanoi peg. ; A Move is a (make-move Peg Peg) (define-struct move (from to)) ; Represents the movement of a the top Disc from the first peg to the second. ; solve-hanoi : PegLabeling Natural -> ListOf<Move> ; Computes the moves required to relocate n stacked Hanoi discs, ; from (pegs-src ps) to (pegs-tgt ps) ; Strategy: ??? (define (solve-hanoi pegs n) ...)
first move the top n-1 discs from the "source" to the "helper" peg,
then move the bottom disc from the "source" to the target" peg,
and finally move the original n-1 discs from the "helper" to the "target".
; Data Definitions — — — — — — — — — — — — — — — — — — - (define LEFT 'left) (define MIDDLE 'middle) (define RIGHT 'right) ; <peg pred> : Peg -> Boolean (define (l? p) (symbol=? p LEFT)) (define (m? p) (symbol=? p MIDDLE)) (define (r? p) (symbol=? p RIGHT)) (define INIT-PEGS (make-pegs LEFT MIDDLE RIGHT)) ; A World is a (make-world Towers ListOf<Move> ListOf<Move>) (define-struct world (towers moves-left moves-done)) ; A Towers is one of: (list Tower Tower Tower) ; Represents a state of the Hanoi game. ; WHERE: there is one each of left, middle, right towers (define mk-towers list) (define get-tower assq) (define EMPTY-TOWERS '((left ()) (middle ()) (right ()))) ; mk-init-towers : PegLabeling Natural -> Towers ; Makes an initial Hanoi state from a peg labeling ps and n discs (define (mk-init-towers ps n) (replace-tower EMPTY-TOWERS (mk-tower (pegs-src ps) (build-list n add1)))) ; replace-tower : Towers Tower -> Towers ; Replaces the discs of Peg p in ts with ds. (define (replace-tower ts t) (local ((define old-tower (get-tower (tower-peg t) ts))) (cons t (remove old-tower ts)))) ; A Tower is a (list Peg Discs) ; Represents one physical tower in a Hanoi game. (define mk-tower list) (define tower-peg first) (define tower-discs second) ; A Discs is a Listof<Disc> ; WHERE: the Discs are sorted on ascending order. ; A Disc is a PosInt ; The ratio of two Discs is the ratio of their widths. ; get-discs : Towers -> Discs (define (get-discs ts) (map second ts)) ; tower-top-disc : Tower -> Disc ; Returns the top Disc in t (define (tower-top-disc t) (first (second t))) ; tower-rest-discs : Tower -> Discs ; Returns all Discs in t except the top. (define (tower-remove-disc t) (mk-tower (first t) (rest (second t)))) ; tower-add-disc : Disc Tower -> Tower ; Adds disc d to the top of t. (define (tower-add-disc d t) (mk-tower (first t) (cons d (second t)))) ; run — — — — — — — — — — — — — — — — — — — — — — – ; run : Natural -> World ; n = number of discs in the puzzle (define (run n) (big-bang (make-world (mk-init-towers INIT-PEGS n) (solve-hanoi INIT-PEGS n) empty) (on-key key-handler) (on-draw render))) ; render — — — — — — — — — — — — — — — — — — — — — – (define DISC-HEIGHT 10) ; pixels (define DISC-WIDTH-RATIO 10) ; max-disc : Towers -> Disc ; Returns the highest numbered Disc in ts. (define (max-disc ts) (apply max (map (λ (t) (apply max 0 t)) (get-discs ts)))) ; render : World -> Image (define (render w) (local ((define towers (world-towers w)) (define max-d (max-disc towers)) (define width (* (add1 (length towers)) (add1 max-d) DISC-WIDTH-RATIO)) (define height width)) (render-moves-left (world-moves-left w) (render-towers towers (empty-scene width height))))) ; render-moves-left : ListOf<Move> Image -> Image ; Renders the number of moves left onto the given image. (define (render-moves-left mvs img) (overlay/align "left" "top" (text (string-append "MOVES REMAINING: " (number->string (length mvs))) 18 'black) img)) ; render-towers : Towers Image -> Image ; Renders the given towers onto the given image. (define (render-towers ts img) (local ((define max-d (max-disc ts))) (overlay (beside (tower->img (get-tower 'left ts) max-d) (tower->img (get-tower 'middle ts) max-d) (tower->img (get-tower 'right ts) max-d)) img))) ; tower->img : Tower Disc -> Image ; Converts t into an image with dimensions determined by max-disc. (define (tower->img t max-disc) (local ((define width (* DISC-WIDTH-RATIO (add1 max-disc))) (define height (* DISC-HEIGHT (add1 max-disc)))) (overlay/align "center" "bottom" (apply above empty-image empty-image (map render-disc (tower-discs t))) (empty-scene width height)))) ; disc->img : Disc -> Image ; Converts d into a rectangle image. (define (render-disc d) (rectangle (* d DISC-WIDTH-RATIO) DISC-HEIGHT 'solid (disc-color d))) ; shuffle : ListOf<X> -> ListOf<X> ; Returns a random permutation of lst. (define (shuffle lst) (sort lst (λ (x y) (zero? (random 2))))) (define DISC-COLORS (shuffle '("red" "blue" "yellow" "green" "orange" "purple"))) ; disc-color : Disc -> Color ; Returns a color for d. (define (disc-color d) (list-ref DISC-COLORS (modulo (sub1 d) (length DISC-COLORS)))) ; key-handler — — — — — — — — — — — — — — — — — — — — ; key-handler : World KeyEvent -> World ; "right" applies a Move in the forward direction. ; "left" applies a Move in the reverse direction. (define (key-handler w kev) (cond [(key=? kev "right") (world-forward w)] [(key=? kev "left") (world-backward w)] [else w])) ; world-forward : World -> World ; Applies one move from the moves remaining in w. (define (world-forward w) (if (empty? (world-moves-left w)) w (make-world (apply-move (world-towers w) (first (world-moves-left w))) (rest (world-moves-left w)) (cons (first (world-moves-left w)) (world-moves-done w))))) ; world-backward : World -> World ; Reverses the most recently applied move in w. (define (world-backward w) (if (empty? (world-moves-done w)) w (make-world (apply-move (world-towers w) (rev-move (first (world-moves-done w)))) (cons (first (world-moves-done w)) (world-moves-left w)) (rest (world-moves-done w))))) ; apply-move : Towers Move -> Towers ; Applies move mv to Tower ts and returns the resulting Towers (define (apply-move ts mv) (local ((define from-tower (get-tower (move-from mv) ts)) (define to-tower (get-tower (move-to mv) ts)) (define next-from-tower (tower-remove-disc from-tower)) (define next-to-tower (tower-add-disc (tower-top-disc from-tower) to-tower))) (replace-tower (replace-tower ts next-from-tower) next-to-tower))) ; rev-move : Move -> Move ; Reverses Move m. (define (rev-move m) (make-move (move-to m) (move-from m)))