02-25.rkt

#lang racket

;; CIS352 -- Feb 25, 2025

;; How do you calculate the transitive closure of a graph given using
;; the layout we've discussed?
;;
;;

;; Let's define a function `(step gr)`, which take a graph as
;; input. It will give us back a graph as output, with the promise
;; that it will only add edges--no edges will be deleted from gr
;;
;; The job of this function is to find all of the "one-step transitive"
;; edges.
(define (step gr)
  ;; Our high-level thought:
  ;; for all edges x → y:
  ;;   for all edges y → z:
  ;;     add x → z to the graph
  ;; But the graph is a hash, not a list of edges...
  (define (add-link gr x y) (hash-set gr x (set-add (hash-ref gr x (set)) y)))
  ;; for all x in the list (hash-keys gr):
  ;;   for all y in the set (hash-ref gr x):
  ;;     for all z in the set (hash-ref gr y):
  ;;       add the x → z to the graph
  (foldl
   (λ (x gr)
     (foldl (λ (y gr)
              (foldl (λ (z gr)
                       (add-link gr x z))
                     gr
                     (set->list (hash-ref gr y))))
            'todo
            'todo))
   gr
   (hash-keys)))

;; This step function adds all of the *one-step* transitive edges.
;; So what you need to do is write a small helper function that
;; recursively calls step and waits until the output equals the input.
;; At that point we've hit a fixed-point and we can return.
;; A fixed-point of some function f is a point x s.t. f(x) = x

;; For all x ∈ (hash-keys gr):
;;   For all y ∈ (hash-ref gr x):
;;     add x → y to the set of edges
(define (enumerate-edges gr)
  (foldl
   (λ (x st-edges)
     (foldl
      (λ (y st-edges)
        (set-add st-edges `(,x → ,y)))
      st-edges
      (set->list (hash-ref gr x))))
   (set)
   (hash-keys gr)))

(define (length-is-len-1? l)
  (and (cons? l)
       (empty? (cdr l))))


;(if #f (/ 1 0) 42)

; (and e0 e1)
#;(if e0
      e1
      #f)

#;(let ([v0 e0])
  (if v0
      e1
      v0))

(define (shortest-string lst)
  (match lst
    ;[(cons s '()) s] equiv to next line...
    [`(,s) s]
    [`(,hd . ,tl)
     (if (< (string-length hd) (string-length (shortest-string tl)))
         hd
         (shortest-string tl))]))

(define (same-length? l0 l1)
  ;; two ways...
  #;(match (cons l0 l1)
    [`(() . ()) #t]
    [`(_ . ()) #t]
    [`(() . _) #t]
    [_ (same-length l0 l1)])
  (cond [(and (empty? l0) (empty? l1)) #t]
        [(empty? l0) #f]
        [(empty? l1) #f]
        [else (same-length? (rest l0) (rest l1))]))
      

(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]))

;; "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) (let ([v (hash-ref h x)]) (hash-set (hash-set h x (hash-ref h y)) y v))]
    [`(assign ,x ,y) (hash-set h x y)]
    [`(add ,x ,y ,z) (hash-set h x (+ (hash-ref h y) (hash-ref h z)))]
    [_ #f]))



(define (interpret-commands cmds)
  (foldl
   (λ (c h) (interpret-command c h))
   (hash)
   cmds))

(define (max-list-tail l)
  ;; acc tracks the max 
  (define (h l acc)
    (match l
      ['() acc]
      [`(,hd . ,tl) (if (> hd acc) (h tl hd) (h tl acc))]))
  (h l -inf.0))

;; come back, write another example

;;
(define (commas strings)
  (match strings
    ['() ""]
    [`(,hd . ,tl) (string-append hd "," (commas tl))]))

(define (commas-again strings)
  (foldr
   (λ (next-string acc-str)
     (string-append next-string "," acc-str))
   ""
   strings))


(define (f x y z)
  (+ x y z))

;(define f (λ (x y z) (+ x y z)))

;; any time you call a function, you *could* have called a lambda
(define g (λ (x y z) ((λ (x y z) (+ x y z)) x y z)))


(define (map f l)
  (match l
    ['() '()]
    [`(,hd . ,tl) (cons (f hd) (map f tl))]))


(define (h y)
  (define (f x) (+ (* x 2) y))
  (map f '(1 2 3)))

;; if you just have, (a) variables, (b) functions/λ, and (c) single-arg function calls
;; you have a Turing-complete language.
(define (λ? e)
  (match e
    [(? symbol? x) #t]
    [`(,(? λ? e0) ,(? λ? e1)) #t]
    [`(λ (,(? symbol? x)) ,(? λ? e-body)) #t]
    [_ #f]))