practice-m1.rkt

#lang racket

;; general direct-style recursive template over lists
#;(define (my-function lst)
  (if (empty? lst)
      'base-case
      (let ([result-from-rest-of-list (my-function (rest lst))]
            [first-list (first lst)])
        (f first-list result-from-rest-of-list))))

;; first using if, then using match
#;(define (positives? nums)
  (if (empty? nums)
      #t
      (and (> (first nums) 0)
           (positives? (rest nums)))))

(define (positives? nums)
  (match nums
    ['() #t]
    [`(,hd . ,tl) (and (> hd 0) (positives? tl))]))

(define (n-positives lst n)
  (match lst
    ['() (<= n 0)]
    [`(,hd . ,tl)
     (if (> hd 0)
         (n-positives tl (- n 1))
         (n-positives tl n))]))

;; Problem 2 -- Tail calls and tail recursion


#;(define (f lst acc)
  (if (empty? lst)
      acc
      (* (first lst)
         (f (rest lst) (* acc (first lst))))))

;; not tail recursive, direct-style recursion is used


;; I will underline in this solution because it's hard
;; to circle in ascii...
#;(define (f g) (g (g x)))
              ;;_________
#;(define (foo x)
  (if (= x 3) ;; not a tail call
      ((f sub1) x)
    ;;____________
      ((f add1) x)
    ;;____________
      ))

(define (g-again lst)
  (define (h lst acc)
    (if (empty? lst)
        acc
        (h (rest lst) (+ (* 2 (first lst)) acc))))
  (h lst 3))

(define (g-using-foldl lst)
  (foldl (λ (x acc) (+ (* 2 x) acc)) 3 lst))

;; what foldr is doing...

#;(cons x0 (cons x1 (cons x2 (cons x3 '()))))
;; foldr is like replacing each cons with reducer
;; and replacing '() with the initial value

(foldl (lambda (x acc)
         (if (string? x) (string-append acc x) (string-append acc "bar")))
       ""
       '("foo" 1 "baz"))

;; acc0 = ""
;; acc1 = (string-append "" "foo") = "foo"
;; acc2 = (string-append "foo" "bar") = "foobar"
;; acc3 = (string-append "foobar" "baz") = "foobarbaz"

(define (sum-negatives lst)
  (foldr (λ (x acc) (cond [(and (number? x) (< x 0)) (+ acc x)]
                          [else acc]))
         0
         lst))

;; Question 4 -- λ-calculus

;; Part (a)
;; X (lambda (x) (lambda (y) (z)))
;; • ((lambda (z) (z (lambda (y) (y k)))) (lambda (x) x)) -- NO X 
;; X (lambda (x) (lambda (y) (x y y)))

;; Part (b)
((λ (x) (x x)) (λ (z) (λ (y) y)))
⟶β (x x) [ x ↦ (λ (z) (λ (y) y)) ]
 =  ((λ (z) (λ (y) y)) (λ (z) (λ (y) y)))
⟶β (λ (y) y)


;; Part (c), α-conversion
((λ (y) (y y)) (λ (z) (λ (y) y)))

;; Notes from real exam...
;; problem 1 -- two small functions 5+5 that involve recursion over lists..
;; problem 2 -- circle tail calls, underling direct-style calls. and a tail-recursive
;; function that accumulates a list
;; problem 3 -- result of using foldr / r also asks about the difference between foldl
;; and foldr.
;; Problem 4 -- identify redexes and perform reduction to a β-normal form and identify
;; whether a specific term may be reduced to β-normal form...