10-01.rkt

#lang racket

;; Direct style
(define (filter f l)
  (match l
    ['() '()]
    [`(,hd . ,tl) (if (f hd) (cons hd (filter f tl)) (filter f tl))]))

;; Tail recursive version
(define (filter-tl f l)
  (define (h l acc)
    (match l
      ['() (reverse acc)]
      [`(,hd . ,tl) (if (f hd) (h tl (cons hd acc)) (h tl acc))]))
  (h l '()))

(define g (hash "n0" (set "n0" "n1") "n1" (set "n1" "n2") "n2" (set "n3") "n3" (set)))

;; g is a graph (as defined in the sense of project 2)
;; hash whose keys are strings and whose values are sets of strings
(define (all-values g)
  (define (h lst)
    (match lst
      ['() (set)]
      [`(,hd . ,rst) (set-union (hash-ref g hd) (h rst))]))
  (h (hash-keys g)))

(all-values g)

;; Exercise: do this in class until 2:29PM 
(define (all-values-tl g)
  ;; lst is a list of the remaining keys
  ;; acc is an accumulator which tracks a set of values to be returned
  (define (h lst acc)
    (match lst
      ['() acc] ;; base case, return accumulator
      [`(,hd . ,tl) (h tl (set-union (hash-ref g hd) acc))]))
                                       ;; acc by set-unioning the result of hash-ref
  (h (hash-keys g) (set)))

(define (add-edge g x y)
  (hash-set g x (set-add (hash-ref g x (set)) y)))

;; takes in a graph g and adds an edge from each node to the node n
(define (add-edge-to-each g n)
  (define (h lst)
    (match lst
      ['() g]
      [`(,hd . ,tl) (add-edge (h tl) hd n)]))
  (h (hash-keys g)))

;; Exercise: fill in the call to (h ...) to make this tail recursive 
(define (add-edge-to-each-tl g n)
  (define (h lst acc)
    (match lst
      ['() acc]
      [`(,hd . ,tl) (h tl (add-edge acc hd n))]))
  (h (hash-keys g)))

;; If we think of the list as
;; (cons x0 (cons x1 (... (cons xn '()) ...)))
;; (f    x0 (f    x1 (... (f    xn i) ...)))
(define (foldr f i l)
  (match l
    ['() i] ;; return the initial value
    [`(,hd . ,tl) (f hd (foldr f i tl))]))

(define (filter-list f l)
  (foldr (λ (next-element acc) (if (f next-element) (cons next-element acc) acc))
         '()
         l))


(define (foldl reducer acc lst)
  (match lst
    ['() acc]
    [`(,hd . ,tl)
     (foldl reducer (reducer hd acc) tl)]))

;; takes a hash h and adds n to each value
(define (add-to-each h n)
  (foldr (λ (k hsh) (hash-set hsh k (+ (hash-ref h k) n)))
         h
         (hash-keys h)))

;; Finding one-step transitive edges
;; a transitive edge is x -> z where there are edges x -> y and y -> z

;; Hint for P2: finding one-step transitive edges

;; Accumulate a graph g
;; For each node x:
;;   For each node y ∈ (hash-ref g x):
;;     For each node z ∈ (hash-ref g y):
;;       Add an edge from x -> z
#;(foldl
 (λ (x g)
   (foldl (λ (y g)
            (foldl (λ (z g) ...)
                   ...))
          g
          (set->list (hash-ref g x))))
 initial-graph
 (hash-keys initial-graph))