Skip to content

Instantly share code, notes, and snippets.

@jbclements
Created May 18, 2020 22:03
Show Gist options
  • Save jbclements/d97b0be940ec59fd86e42847ddf46a6f to your computer and use it in GitHub Desktop.
Save jbclements/d97b0be940ec59fd86e42847ddf46a6f to your computer and use it in GitHub Desktop.
#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"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment