gistfile1.txt

#lang racket

;; CIS352 -- Feb 24, 2026

;; □ -- Sets in Racket

;; QuickAnswer

(set) ;; empty set 
(set 1 2 3) ;; {1, 2, 3} = {3, 2, 1} = {3, 3, 2, 2, 1, 1, 1}
(equal? (set 1 2 3)
        (set 3 2 1))
(equal? (set 1 2 3)
        (set 3 3 2 2 1 1 1))

;; I can use set-member? to check whether something is in the set
(set-member? (set 1 2 3) 4)

;; I can use set-union to merge two sets
(set-union (set 1 1 1 3 3 2) (set 10 1 3 10))

;; I can use set-add to add an element
(set-add (set 1 2 3) 5)

(define x (set 10 15 20))

;; Let's say I want to write a function (add-all s lst)
;; add every element of lst to the set s
#;(define (add-all s lst)
  (define (h lst)
    (if (empty? lst)
        (set)
        (set-add (h (rest lst)) (first lst))))
  (set-union s (h lst)))

#;(define (add-all-bad s lst)
  (for ([item lst])
    (set-add s item))
  s)

;; Rewrite add-all in a different manner (not using the helper function h)
#;(define (add-all s lst)
  (match lst
    ['() 'todo]
    [`(,fst ,rst ...) 'todo]))

;; Rewrite add-all in a different manner (not using the helper function h)

(define (add-all s lst)
  (match lst
    ['() s]
    [`(,fst ,rst ...) (set-add (add-all s rst) fst)]))

;; the function list->set turns a list into a set
;;
;; (list->set lst) => (set ....)
(define (list->set lst)
  (match lst
    ['() (set)]
    [`(,fst ,rst ...) (set-add (list->set rst) fst)]))

;; (set->list s) => '(x0 x1 ...)

;; QuickAnswer: how do you fill in todo to sum the
;; elements of the set s?

;; Sum-set using foldr
(define (sum-set s)
  (foldr (lambda (next-element cur-acc) 'todo)
         0
         (set->list s)))

#;(define (sum-set s)
  (foldr (lambda (next acc) (+ acc next)) 0 (set->list s)))


;; □ -- Hashes in Racket

;; Hashes are dictionaries

;; We have the empty hash. The empty hash associates no keys with no values
(hash)

;; If I pass hash arguments, I give keys/values in pairs
(hash 'x 5 'y 20) ;; maps 'x ↦ 5, maps 'y ↦ 20

;; To lookup a value associated with a key, I use hash-ref
(hash-ref (hash 'x 5 'y 20) 'x) ;; 5
(hash-ref (hash 'x 5 'y 20) 'y) ;; 20

;; Like (set-add ...), which adds items to sets
;; (hash-set h k v) takes three things:
;;  - a hash h
;;  - a key k
;;  - a value v
;;
;; Returns a new hash that is the same as h, except
;; also k ↦ v. The hash h is unchanged.
(define h (hash 'x 5 'y 20))
(hash-set h 'x 15)

;; I can get the keys of a hash by using (hash-keys h)
;; I can get the values of a hash by using (hash-values h)
;; 
;; But I *can't* assume that hash-keys / hash-values return
;; the keys / values in the same order.

(define (print-hash hsh)
  (define (h lst-keys)
    (match lst-keys
      ['() (void)] ;; don't print anything
      [`(,fst ,rst ...)
       ;; gets the value associated with the key fst
       (displayln "Key is:")
       (displayln fst)
       (displayln "Value is:")
       (displayln (hash-ref hsh fst))
       (h rst)]))
  (h (hash-keys hsh)))

;; □ -- How to represent graphs in P2

;; Every edge X -- Y in the graph is represented by the following:
;; - The graph (in project 2) is a hash
;; - The keys of the hash are nodes in the graph (strings)
;; - The values of the hash are *sets* of nodes (strings)
;; - If there is an edge X -- Y, then Y ∈ the set associated with X

;; X ---> Y --> Z --> A
;; Let's turn this diagram into a graph as represented in project 2
(hash "X" (set "Y")
      "Y" (set "Z")
      "Z" (set "A")
      "A" (set))

;; If want to add this edge:
;;
;; X ---> Y --> Z --> A
;;        v-----------^
;;
;; what do I type here (modification of the above)
(hash "X" (set "Y")
      "Y" (set "Z" "A")
      "Z" (set "A")
      "A" (set))

;; call (hash-ref graph from) -- that gives me a set
;; now I can use set-member? on that to determine if to
;; ∈ the set of nodes being pointed by from
(define (is-there-an-edge? graph from to)
  (set-member? (hash-ref graph from (set)) to))

;; □ -- How to add an edge to a graph?

;; Add an edge from ↦ to
;; Don't drop any previous edges
(define (add-edge graph from to)
  ;; Use (hash-set h k v)
  ;; The value needs to associate from with a set containg to
  ;; but also everything that was pointed to by k before
  (hash-set graph from (set-add (hash-ref graph from (set)) to)))

;; □ -- Folding over the keys of a hash

;; (add-to-each-key hsh v)
;; walks over the hash hsh and adds v to each value
;; produces a new hash where every value is +v 
(define (add-to-each-key hsh v)
  (foldr (lambda (next-key acc-hash) (hash-set acc-hash
                                               next-key
                                               (+ v (hash-ref hsh next-key))))
         (hash)
         (hash-keys hsh)))

;; (link-to-every graph n): for every node in the graph
;; add a link between that node and the node n
;;
;; Plan: use foldr to accumulate a graph (i.e., hash),
;; walk over the keys of the input hash, each of them is associated
;; with a set of neighbors. Add n to that set.
;;
;; You can use add-edge.
(define (link-to-every graph n)
  (foldr (lambda (next-node acc-graph)
           'todo)
         (hash)
         (hash-keys graph)))

;; For all node n0 in (hash-keys graph):
;;  For all node n1 pointed to by n0 in the graph:
;;    For all nodes n2 pointed to by n1 in the graph:
;;      Add an edge between n0 and n2
;; 
;; Use nested foldr/l to accumulate a graph, looping over:
;;  - (hash-keys graph) at the top level
;;  - (set->list (hash-ref graph n0)) at the second level
;;  - (set->list (hash-ref graph n1)) at the third level
;;  - Thread through the accumulator, passing from outer to inner.

;; We didn't quite get here--we'll cover this next time, as we begin
;; to talk about interpreters and proof trees.

;; □ -- Build an interpreter for the following language
(define (expr? e)
  (match e
    ;; Integers are expressions
    [(? integer? i) #t]
    ;; (+ e0 e1)
    [`(+ ,(? expr? e0) ,(? expr? e1)) #t]
    ;; (- e0 e1)
    [`(- ,(? expr? e0) ,(? expr? e1)) #t]
    ;; Variable references
    [(? symbol? x) #t]
    ;; Let-binding (variable creation)
    [`(let ([,(? symbol? x) ,(? expr? e)])
        ,(? expr? e-body))
     #t]
    ;; Nothing else is an expression
    [_ #f]))

;; Let's write an intrepreter for the fragment of this
;; language that skips variables / let.
(define (interp e)
  (match e
    ;; Integers evaluate to themselves
    [(? integer? i) i]
    ;; plan: call interp on e0 / e1, then take their results
    ;; and use - to subtract the result of the first
    ;; from the second
    [`(+ ,(? expr? e0) ,(? expr? e1))
     'todo]
    ;; plan: call interp on e0 / e1, then take their results
    ;; and use - to subtract the result of the first
    ;; from the second
    [`(- ,(? expr? e0) ,(? expr? e1))
     'todo]
    ;; don't touch this
    [(? symbol? x) #t]
    ;; don't touch this
    [`(let ([,(? symbol? x) ,(? expr? e)])
        ,(? expr? e-body))
     'todo]
    ;; Nothing else is an expression
    [_ #f]))