the-seasoned-schemer-notes/chapter-11/02-two-in-a-row.scm

(import
 (except (rnrs base) let-values map)
 (only (guile)
       lambda* λ))

;;; ============
;;; TWO IN A ROW
;;; ============

;; A function shall be defined, which determines, whether there are 2
;; subsequent elements inside a given list, for which ~eq?~ is ~#t~.

;; CODE 1:

;; (define is-first?
;;   (λ (a lat)
;;     (cond
;;      [(null? lat) #f]  ; check for empty list
;;      [else (eq? a (car lat))])))

;; (define two-in-a-row?
;;   (λ (lat)
;;     (cond
;;      [(null? lat) #f]  ; check for empty list
;;      [else
;;       (or (is-first? (car lat) (cdr lat))
;;           (two-in-a-row? (cdr lat)))])))

;; However, this version obscures, that in one case it performs a
;; check twice. When it checks, whether the list is ~null?~ in
;; ~is-first?~ and returns ~#f~, ~two-in-a-row?~ will recur and call
;; itself. Then it will check for a second time, whether the list it
;; receives is ~null?~.

;; To avoid this duplicate check, the book suggests to leave the
;; decision of whether to recur or not to the function, which checks
;; for an empty list first. That is ~is-first?~.

;; Let us try to leave that responsibility to ~is-first?~:

;; CODE 2:

;; (define is-first?
;;   (λ (a lat)
;;     (cond
;;      [(null? lat) #f]
;;      [else
;;       (or (eq? a (car lat))
;;           ;; Not (cdr lat) here! is-first? is already given the cdr of
;;           ;; the list and the argument ~a~ is the actual car of the
;;           ;; list! The predicate ~is-first?~ does not reduce the
;;           ;; input. That is a responsibility of ~two-in-a-row?~.
;;           (two-in-a-row? lat))])))

;; (define two-in-a-row?
;;   (λ (lat)
;;     (cond
;;      [(null? lat) #f]
;;      [else
;;       (is-first? (car lat) (cdr lat))])))

;; Now we have two functions which are mutually recursive.

;; NOTE: There is also a problem of (two-in-a-row? lat) in ~is-first?~
;; not being in the tail position and thus growing the stack each
;; call. (two-in-a-row? lat) is inside the (or ...)  expression, which
;; still needs to be kept on the stack, so that is-first? can return
;; the result of (or ...).

;; NOTE: There is still a duplicate check of (null? lat), because when
;; ~two-in-a-row?~ is called from ~is-first?~, it checks again,
;; whether the list is empty.

;; NOTE: is-first? decides, whether to recur or not.

;; OBSERVATION: When we look at what ~two-in-a-row?~ actually does,
;; when called from ~is-first?~, we can see, that it does not actually
;; do much. The ~null?~ check for the empty list will always be ~#f~,
;; because the same thing was already checked in ~is-first?~.

;; OBSERVATION: ~lat~ is given to ~two-in-a-row?~. So ~two-in-a-row?~
;; will always enter the ~else~ branch, when called from ~is-first?~
;; and the ~null?~ check is only useful, when ~two-in-a-row?~ is
;; initially called from outside of ~is-first?~.

;; CONCLUSION: This observation leads to the conclusion, that one
;; could write a single function, by modifying ~is-first?~ a little
;; more, so that the call to ~two-in-a-row?~ is no longer needed.

;; The modified version of ~is-first?~ will be renamed to
;; ~two-in-a-row?~ to express what it does.

;; CODE 3:

;; (define two-in-a-row?
;;   (λ (preceding lat)
;;     (cond
;;      [(null? lat) #f]
;;      [else
;;       (or (eq? preceding (car lat))
;;           (two-in-a-row? (car lat) (cdr lat)))])))

;; NOTE: There is still a problem here: ~two-in-a-row?~ receives
;; always 2 arguments. This is inconvenient to work with and
;; unexpected at the caller side. One can use ~two-in-a-row?-helper~
;; to avoid this.

;; NOTE: The problem of non-tail position of the call to
;; ~(two-in-a-row? (car lat) (cdr lat))~ still persists.

;; CODE 4:

;; (define two-in-a-row?-helper
;;   (λ (preceding lat)
;;     (cond
;;      [(null? lat) #f]
;;      [else
;;       (or (eq? preceding (car lat))
;;           (two-in-a-row?-helper (car lat) (cdr lat)))])))

;; (define two-in-a-row?
;;   (λ (lat)
;;     (cond
;;      [(null? lat) #f]
;;      [else
;;       (two-in-a-row?-helper (car lat) (cdr lat))])))

;; This clears up the interface for the user.

;; A tail call optimized version, getting rid of the non-tail position
;; of the recursive call, could be written as follows:

;; CODE 5:

(define two-in-a-row?-helper-tail-recursive
  (λ (preceding lat)
    (cond
     [(null? lat) #f]
     ;; It is a bit meh, that we cannot simply return the result of the
     ;; expression here and need to write #t instead. Perhaps there is a better
     ;; way?
     [(eq? preceding (car lat)) #t]
     [else
      ;; Tail-recursive.
      (two-in-a-row?-helper-tail-recursive (car lat) (cdr lat))])))

(define two-in-a-row?
  (λ (lat)
    (cond
     [(null? lat) #f]
     [else
      (two-in-a-row?-helper-tail-recursive (car lat) (cdr lat))])))

;; USAGE:

(display
 (simple-format
  #f "(two-in-a-row? '(1 2 2 3 4)) -> ~a\n"
  (two-in-a-row? '(1 2 2 3 4))))

(display
 (simple-format
  #f "(two-in-a-row? ''(1 2 3 4 5)) -> ~a\n"
  (two-in-a-row? '(1 2 3 4 5))))