2-20.rkt

;; Exercise 2
;; CIS 352 -- Spring 2024
#lang racket

(provide (all-defined-out))

;;
;; Maps
;;

;; map the function f over each element of lst
(define (map f lst)
  (if (empty? lst)
      '()
      (cons (f (first lst)) (map f (rest lst)))))

;; Racket
(map - '(1 2 3)) ;; ‘(-1 -2 -3)
;; equivalent to (via “η-extenstionality”)
(map (lambda (x) (- x)) '(1 2 3))

;; (add-n n lst) adds n to each element of the list lst. 
;; write the function using *direct* style recursion
;; (i.e., follow the template).
(define (add-n lst n)
  (if (empty? lst)
      '()
      (cons (+ n (first lst)) (add-n (rest lst) n))))

;; define add-n again, but this time using map. Your function should
;; not use recursion (directly, although it will indirectly be using
;; recursion in that `map` is recursive), but should instead simply
;; use `map`.
(define (add-n-using-map lst n)
  (map (lambda (x) (+ n x)) lst))

(define (foo x)
  (match x
    [(? number?) (* 2 x)]
    [`(,e0 ,e1 ,_) `(,e0 ,e1)]
    [_ "error"]))

;;
;; practice with matches and quasiquotes
;;

;; return only elements of lst that satisfy f
(define (filter f lst)
  (cond [(empty? lst) '()]
        [(f (first lst)) (cons (first lst) (filter f (rest lst)))]
        [else (filter f (rest lst))]))

(define (fac n)
  (if (= n 0)
      (begin (displayln "here") 1)
      (* n (fac (- n 1)))))

;; I want to write this function to use tail recursion
;; what that means is that every recursive call must be
;; "the last thing to happen"
(define (fac-again n)
  ;; n is going to get smaller (by 1)
  ;; acc is going get bigger
  (define (h n acc)
    (displayln n)
    (displayln acc)
    (if (equal? n 0)
        acc
        (h (- n 1) (* acc n))))
  (h n 1))

(define (fib n)
  (match n
    [0 1]
    [1 1]
    [_ (+ (fib (- n 1)) (fib (- n 2)))]))


;; Exam problem candidate
;;
;; Circle all of the callsites that are tail calls
;; and underline all of the callsites that are
;; direct-style calls
#;(define (length-dir l)
  (pretty-print l)
;;________________
  (pretty-print n)
;;________________
  (if (null? l)
    ;;_________
      0
      (+ 1 (length-dir (rest l))))) ;; (+ 1 ....) circled
                    ;; ________
         ;;_____________________

;; claim: we can rewrite length-dir like this
#;(define (length-dir l)
  (pretty-print l)
;;________________
  (pretty-print n)
;;________________
  (if (null? l)
    ;;_________
      0
      (let ([x (rest l)])
        (let ([r (length-dir x)])
          (+ 1 r)))))


(define (length-tail l)
  (define (h l n)
    (pretty-print l)
    (pretty-print n)
    (if (null? l)
        n
        (h (cdr l) (+ n 1)))) ;; the call to h is in tail position, it is a tail call
  (h l 0)) ;; this call to h is a tail call, too


(define (filter f lst)
  (cond [(empty? lst) '()]
        [(f (first lst))
         (cons (first lst)
               (filter f (rest lst)))]
        [else (filter f (rest lst))]))

(define (filter-tl f lst)

  (define (reverse l)
    (define (rev lst0 lst1)
      (match lst0
        ['() lst1]
        [`(,hd . ,tl) (rev tl (cons hd lst))]))
    (rev l '()))
  
  (define (h0 lst acc)
    (match lst
      ['() acc]
      [`(,hd . ,tl)
       (if (f hd)
           (h0 tl (cons hd acc))
           (h0 tl acc))]))

  (define (h1 lst acc)
    (match lst
      ['() acc]
      [`(,hd . ,tl)
       (if (f hd)
           (h1 tl (append acc (list hd)))
           (h1 tl acc))]))

  ;; fix 1
  (reverse (h0 lst '()))

  ;; fix 2
  #;(h1 lst '()))

;; acc = 1
;; for(i in range(n)):
;;     acc = acc * n
        
;; Define using match patterns: (filter f l) selects the elements in
;; the list l which satisfy the predicate f, omitting those elements x
;; for which (f x) is false
(define (filter-again f lst)
  (match lst
    ['() '()]
    [`(,hd . ,tl) #:when (f hd) (cons hd (filter-again f tl))]
    [`(,hd . ,tl) (filter-again f tl)]))

;; select the maximum element from the list lst, assume lst is a list
;; of numbers.
(define (maxof lst)
  (match lst
    ['() (error "can't take the max of an empty list")]
    [`(,only) only]
    [`(,fst ,snd . ,rest)
     (max fst snd (maxof rest))]))


;; andmap test cases
;; > (andmap list? ‘((1 2) () (3)))
;; #t
;; > (andmap list? ‘((1 . 2) ()))
;; #f
;; > (andmap list? ‘(1 2 3))
;; #f
(define (andmap f lst)
  (match lst
    ['() #t]
    [`(,hd . ,tl) (if (f hd) (andmap f tl) #f)]))

;;
;; practice with hashes and sets
;;

;; hashes in racket are key / value dictionaries
;; add / lookup / etc... are amortized O(1)
(define hsh (hash 'x 1 'y 2 'z 4))

;; important functions on hashes
(hash-keys (hash 'x 1 'y 2 'z 3))
;; returns a list of the keys of the hash
;; in *no specific order*

;; pass in a list of elements
(define (my-set lst)
  ;; make a hash of key/value associations from
  ;; each element of lst (which will be keys in our hash)
  ;; to the dummy value "dummy"
  (define (h lst)
    (match lst
      ['() (hash)]
      [`(,hd . ,tl) (hash-set (h tl) hd "dummy")]))
  (h lst))

;; hashes are generalized *sets*
;; a hash-set (degenerate hash) can be constructed using
(define st (set 1 2 3))

;; print out a hash in a canonical order
(define (render-hash h)
  (for ([key (sort (hash-keys h) symbol<?)])
    (displayln (format "~a,~a" key (hash-ref h key)))))

;; produce a map from each element in lst to the number zero
;; (zeroes '(x y)) = (hash-set (hash-set 'y 0) 'x 0)
;; note that hashes are *unordered*
;; aka (hash 'x 0 'y 0)
(define (zeroes lst)
  (match lst
    ['() (hash)]
    ;; hint: use hash-set and recursion
    [`(,hd . ,tl)
     (hash-set (zeroes tl) hd 0)]))

(define (zeroes-tl lst)
  (define (h lst hsh)
    (match lst
      ['() hsh]
      [`(,hd . ,tl)
       (h tl (hash-set hsh hd 0))]))
  (h lst (hash)))

(define (foldr reducer init lst)
  (match lst
    ['() init]
    [`(,hd . ,tl)
     (reducer hd (foldr reducer init tl))]))

(define (sum-list lst)
  (foldr (λ (next-element-in-list current-accumulator)
           (+ next-element-in-list current-accumulator))
         0
         lst))

(define (filter-using-foldr f lst)
  ;; e is next element in the list
  ;; acc is an accumulated list of elements
  ;; principle: return type from the reducer function is
  ;; the return type of the foldr as a whole
  (foldr (λ (e acc)
           (if (f e)
               (cons e acc)
               acc))
         '()
         lst))

(define (filter-using-foldl f lst)
  ;; e is next element in the list
  ;; acc is an accumulated list of elements
  ;; principle: return type from the reducer function is
  ;; the return type of the foldr as a whole
  (reverse
   (foldl (λ (e acc)
            (if (f e)
                (cons e acc)
                acc))
          '()
          lst)))

;; acc = '()
;; for e in lst:
;;    acc = (if (f e) (cons e acc) acc)


#;(define (sum-list l)
  (match l
    ['() 0]
    [`(,hd . ,tl) (+ hd (sum-list tl))]))

(define (sum-set st)
  (sum-list (set->list st)))

;; Set data structure in Racket
;; Use `set` as a constructor
;; - (set) or (set 'x 'y ...) or (set e0 e1 ...)
;;
;; (set-add st element) O(1) -- returns a new set
;; that includes everything in st and also element
;;
;; (set-union st0 st1) O(n) or faster -- return
;; a new set that includes everything in st0 and st1
;;
;; (set-remove st element) O(1) -- return a set
;; containing everything in st minus element


;; add n to each value of the hash, for each of its keys. Hint: write
;; a recursive function (or foldl, if you know / would like to use it)
;; to walk over each of the keys in `hash-keys`.
(define (add-to-each h n)
  (define (f keys)
    (match keys
      ['() (hash)]
      [`(,first-key . ,rest-keys) (hash-set (f rest-keys)
                                            first-key
                                            (+ (hash-ref h first-key) n))]))
  (f (hash-keys h)))

(define (hash-map hsh f)
  (define (h keys)
    (match keys
      ['() (hash)]
      [`(,hd . ,tl) (hash-set (h tl) hd (f (hash-ref hsh hd)))]))
  (h (hash-keys hsh)))

(define (command? c)
  (match c
    ;; swap x and y's value
    [`(swap ,(? symbol? x) ,(? symbol? y)) #t]
    ;; assign x to the value of y
    [`(assign ,(? symbol? x) ,(? number? y)) #t]
    ;; assign x to the value of y+z
    [`(add ,(? symbol? x) ,(? symbol? y) ,(? symbol? z)) #t]
    [_ #f]))

;; "interpret" a single command: return the resulting hash. Swap
;; should swap the values in x and y. Assign should assign to the
;; value x. Add should assign to the value x with the value of y plus
;; the value of z.
(define (interpret-command e h)
  (match e
    [`(swap ,x ,y)
     (hash-set (hash-set h x (hash-ref h y)) y (hash-ref h x))]
    [`(assign ,x ,y)
     (hash-set h x y)]
    [`(add ,x ,y ,z)
     (hash-set h x (+ (hash-ref h y) (hash-ref h z)))]))

;; interpret each command one at a time
(define (interpret-commands es)
  (define (h hsh lst)
    (match lst
      ['() hsh]
      [`(,hd . ,tl) (h (interpret-command hd hsh) tl)]))
  (h (hash) es))

(define (newlines n)
  (cond
    [(equal? n 0) ""]
    [(not (equal? n 0)) (string-append "\n" (newlines (- n 1)))]))

#;(define (newlines n)
  (match n
    [0 ""]
    [n (string-append "\n" (newlines (- n 1)))]))