2020-05-18-pm-sps.rkt

#lang racket

(define last-str #f)

(struct node (l r))

(require rackunit)

(define (b-after-a? tree)
  (match tree
    [(? string? s)
     (cond [(and (equal? s "b")
                 (equal? last-str "a"))
            #t]
           [else
            (begin
              (set! last-str s)
              #f)])]
    [else
     (or (b-after-a? (node-l tree))
         (b-after-a? (node-r tree)))]))




(check-equal? (b-after-a?
               (node (node "a" "f")
                     (node (node "g" "z")
                           (node "y" "b"))))
              #f)

(check-equal? (b-after-a?
               (node (node "a" "f")
                     (node (node "g" "a")
                           (node "b" "b"))))
              #t)



;; store-passing style

(define (b-after-a?/sps tree last-str)
  (match tree
    [(? string? s)
     (cond [(and (equal? s "b")
                 (equal? last-str "a"))
            (list #t "b")]
           [else
            (list #f s)])]
    [else
     (match (b-after-a?/sps (node-l tree) last-str)
       [(list retval last-str-2)
        (if retval
            (list retval last-str-2)
            (b-after-a?/sps (node-r tree) last-str-2))])]))


(check-equal? (b-after-a?/sps
               (node (node "a" "f")
                     (node (node "g" "z")
                           (node "y" "b")))
               #f)
              (list #f "b"))

(check-equal? (b-after-a?/sps
               (node (node "a" "f")
                     (node (node "g" "a")
                           (node "b" "b")))
               #f)
              (list #t "b"))