solutions.rkt

#lang racket

;; PRACTICE Midterm 1 solutions

;; Part (a) 

(define (mul-list l k)
  (if (empty? l)
      '()
      (cons (* (first l) k) (mul-list (rest l) k))))

;; Part (b)

(define (all-equal? lst)
  (define (all-equal-to-k? lst k)
    (cond [(empty? lst) #t] ;; vacuously true
          [(equal? (first (lst)) k) (all-equal-to-k? (rest lst) k)]
          ;; it wasn't empty, and also the first element isn't
          ;; equal? to k
          [else #f]))
  (if (empty? lst)
      #t
      (all-equal-to-k? (rest lst) (first lst))))

#;(define (all-equal? lst)
  (or (empty? lst)
      (andmap (λ (e) (equal? e (first lst))) lst)))

;; Problem 2:
;; - The left hand sides of a cond cannot be tail calls
;; because they have to wait for a result and decide
;; whether to take the true branch or the false branch
;; (which continues to check the rest of the conditions)
;; Thus, the following should circled (tail calls):
;; - (foo 3 5)
;; - (foo 5 3)
;; And the following should underlined (direct-style calls):
;; - (number? bar)
;; - (bar baz)
;; - (baz bar)
;;
;; The function is tail recursive, because each of the two
;; recursive calls is a tail call.

(define (every-other-tail lst)
  (define (h l acc)
    ;(pretty-print (first l))
    ;(pretty-print acc)
    (match l
      [`(,fst ,snd ,rest ...) (h rest (cons fst acc))]
      [_ (reverse acc)]))
  (h lst '()))

;; Problem 3:
;; doing both foldl and foldr
;;
;; foldr walks over the list from right to left
;; ...
;; '(4 4 5 3 6 6)
;;
;; foldl walks over the list left-to-right
;; the reducer function is
;; (λ (x acc) (if (even? x) (cons x (cons x acc)) (cons x acc)))
;; so initial accumulator is '()
;; first element is 4
;; acc updated to '(4 4)
;; next element is 5
;; acc updated to '(5 4 4)
;; next element is 3
;; acc updated to '(3 5 4 4)
;; next element is 6
;; acc updated to '(6 6 3 5 4 4)
;; which is returned

;; Part (b) is tantamount to asking: could you write a
;; reducer that could tell whether a list was travrsed
;; left to right, or right to left?
;; Answer: yes. Good examples are operators that don't
;; commute, and something like cons
(foldl cons '() '(1 2 3))
(foldr cons '() '(1 2 3))

;; Problem 4

;; TWO redexes
((λ (x) (x x)) (λ (z) ((λ (y) y) (λ (k) k))))
;; - ((λ (x) (x x)) (λ (z) ((λ (y) y) (λ (k) k))))
;; - ((λ (y) y) (λ (k) k))

;; (inner) Let's take the inner β redex
;;((λ (x) (x x)) (λ (z) (λ (k) k)))
;; (x x) [ x ↦ (λ (z) (λ (k) k)) ]
;; = ((λ (z) (λ (k) k)) (λ (z) (λ (k) k)))
;; let's continue to β reduce
;; ((λ (z) (λ (k) k)) (λ (z) (λ (k) k)))
;; = (λ (k) k) [ z ↦ (λ (z) (λ (k) k)) ]
;; = (λ (k) k)


;; (outer)
;;((λ (z) ((λ (y) y) (λ (k) k)))
;; (λ (z) ((λ (y) y) (λ (k) k))))
;; ⟶β
;; ((λ (y) y) (λ (k) k))
;; ⟶β
;; (λ (k) k)

;; The last one lets us do either an outer reduction
;; or an inner reduction. In either case, we reduce
;; Ω to itself as often as we want, without end.
;; It is impossible to reduce this down to a normal form