;; a (graph-of X) is: 
;;  - (make-graph (listof X) (X -> (listof X)) (X X -> boolean))
(define-struct graph (nodes neighbors node-equal?))

(define G 
  (list 1 2 3 4)
  (lambda (n)
    (cond
      [(= n 1) (list 2 3)]
      [(= n 2) empty]
      [(= n 3) (list 4)]
      [(= n 4) empty]))
  =)

(define G2
  (list 'a 'b)
  (lambda (n)
    (cond
      [(symbol=? n 'a) (list 'a)]
      [(symbol=? n 'b) (list 'b 'a)]))
  symbol=?)

;; graph-equal? : (graph-of X) (graph-of X) -> boolean
;; determines whether G1 and G2 have the same nodes and 
;; the same edges
(define (graph-equal? G1 G2) ...)

;; examples as tests: 
(graph-equal? G2 G2) 'shouldbe true
(graph-equal? G1 G2) 'shouldbe false

(Some more test cases added to illustrate some possibly-subtle points ... added 4:20PM, 11/17)

(graph-equal? (make-graph '() (lambda (x) '()) symbol=?)
              (make-graph '() (lambda (x) '()) symbol=?))
'shouldbe
true

(graph-equal? (make-graph '(a) (lambda (x) '()) symbol=?)
              (make-graph '() (lambda (x) '()) symbol=?))
'shouldbe
false

(graph-equal? (make-graph '(a) (lambda (x) '()) symbol=?)
              (make-graph '(a) (lambda (x) '()) symbol=?))
'shouldbe
true

(graph-equal? (make-graph '(b) (lambda (x) '()) symbol=?)
              (make-graph '(a) (lambda (x) '()) symbol=?))
'shouldbe
false

(graph-equal? (make-graph '(a b) (lambda (x) '()) symbol=?)
              (make-graph '(b a) (lambda (x) '()) symbol=?))
'shouldbe
true

(graph-equal? (make-graph '(a b) 
                         (lambda (x)
                           (cond 
                             [(symbol=? x 'a) '(b)] 
                             [(symbol=? x 'b) '()]))
                         symbol=?)
              (make-graph '(a b) 
                         (lambda (x)
                           (cond 
                             [(symbol=? x 'b) '(a)] 
                             [(symbol=? x 'a) '()]))
                         symbol=?))
'shouldbe
false


(graph-equal? (make-graph '(a b) 
                         (lambda (x)
                           (cond 
                             [(symbol=? x 'a) '(a b)] 
                             [(symbol=? x 'b) '()]))
                         symbol=?)
              (make-graph '(a b) 
                         (lambda (x)
                            (cond 
                             [(symbol=? x 'a) '(b a)] 
                             [(symbol=? x 'b) '()]))
                         symbol=?))
'shouldbe
true

;; reverse-graph : (graph-of X) -> (graph-of X)
;; returns a graph that has the same nodes as G, and all
;; edges reversed; e.g. if G has an edge from 'a to 'b, then
;; the resulting graph has an edge from 'b to 'a
(define (reverse-graph G) ...)

;; undirected? : (graph-of X) -> boolean
;; determines if G is undirected; that is, if for every edge from
;; a node X to a node Y in G, there is also an edge from Y to X
(define (undirected? G) ...)

;; vector-sum : (listof posn) -> posn
;; adds together all the posns in lop, treating each posn as a vector
;; [i.e., the sum of two posns (x_1,y_1) and (x_2,y_2) is (x_1+x_2,y_1+y_2)]
(define (vector-sum lop) ...)

;; digits->number : (listof num[0-9]) -> num
;; converts the list of digits lod to the number it represents
(define (digits->number lod) ...)

;; examples as tests:
(digits->number (list 1 2 3 0 5)) 'shouldbe 12305
(digits->number empty) 'shouldbe 0

;; a naming-ftree is
;;   - 'unknown
;;   - (make-child (symbol naming-ftree naming-ftree))
(define-struct child (name ma pa))

;; any-jrs? : naming-ftree -> boolean
;; determines if there are any "juniors" in the given tree. A "junior"
;; is a child with the same name as any of his or her ancestors.
(define (any-jrs? ftree) ...)

; a (graph-of X) is:
; (make-graph (listof X) (X -> (listof X) (X X -> boolean))
(define-struct graph (nodes neighbors node-equal?))

; find-paths : (graph-of X) X X -> (listof (listof X))
; to find all of the paths in the graph from f to t
(define (find-paths G f t) ...)

Define the following functions:

;; forge-list : nat (nat -> X) -> (listof X)
;; to forge a list of length N where the
;; last element is (f 0), the second to last is (f 1), etc
(define (forge-list n f) ...)

;; examples as tests
(forge-list 4 (lambda (x) x))
(list 3 2 1 0)

;; triangular-list : nat -> (listof (listof 'x))
;; to build a triangular list of lists of the symbol 'x
(define (triangular-list i) ...)

;; examples as tests
(triangular-list 4)
(list (list 'x) (list 'x 'x) (list 'x 'x 'x) (list 'x 'x 'x 'x))

Generalize qsort from class so that it takes a comparison function and can sort lists of arbitrary kinds of elements rather than just lists of numbers:

;; qsort2 : (X X -> bool) (listof X) -> (listof X)
;; sort the elements of lox according to the compare function
(define (qsort2 compare lox) ...)


;; examples as tests
(qsort2 < (list 3 4 2 1)) 'shouldbe (list 1 2 3 4)
(qsort2 > (list 3 4 2 1)) 'shouldbe (list 4 3 2 1)

Do HtDP exercise 25.2.3.

Use map from class to write the bodies of each of the following functions:

;; distances : (listof posn) -> (listof num)
;; returns the list consisting of distance from 
;; the origin to each posn in lop
(define (distances lop) ...)

;; build-straight-line : num (listof num) -> (listof posn)
;; returns a list of posns where the X coordinate is n and 
;; the Y coordinate is a number
;; in lon
;; e.g., (build-straight-line 2 (list 1 2 3)) 
;;       'shouldbe
;;       (list (make-posn 2 1) (make-posn 2 2) (make-posn 2 3))
(define (build-straight-line n lon) ...)

Use filter from class to write the bodies of each of the following functions:

;; evens : (listof num) -> (listof num)
;; returns even numbers in lon
(define (evens lon) ...)

;; first-quadrant-pts : (listof posn) -> (listof posn)
;; returns the posns from lop that are in the first
;;  quadrant (i.e., both X and Y parts are positive)
(define (first-quadrant-pts lop) ...)

Use fold from class to write the following function:

;; total-width : (listof image) -> num
;; returns the sum of the widths of all images in loi
(define (total-width loi) ...)

Use one of map, filter, and fold (along with nonrecursive helper functions, possibly) to write the bodies of each of the following functions:

;; points-on-curve : (num -> num) (listof posn) -> (listof posn)
;; given a function f describing a curve (i.e., a function that takes an
;; X-coordinate and returns a Y coordinate), returns those positions
;; in lop that are on that curve
;; e.g.
;; (define (diagonal x) x)       ;; Y = X
;; (define (parabola x) (sqr x)) ;; Y = X^2
;; (define points (list (make-posn 1 0) (make-posn 1 1) (make-posn 2 2)))
;; (points-on-curve diagonal points) 'shouldbe (list (make-posn 1 1) (make-posn 2 2))
;; (points-on-curve parabola points) 'shouldbe (list (make-posn 1 1))
(define (points-on-curve f pts) ...)

;; positions: (num -> num) (listof num) -> (listof posn)
;; given a function f representing a curve and a list lo-xs of x-coordinates,
;; returns the points on the curve f with those x-coordinates
;; e.g., (positions parabola (list 1 2 3)) 
;;       'shouldbe
;;       (list (make-posn 1 1) (make-posn 2 4) (make-posn 3 9))
(define (positions lon f) ...)

;; posns->list : (listof posn) -> (listof num)
;; constructs the list consisting of all the X and Y coordinates of each
;; of the posns in lop, where both coordinates of the first posn come 
;; before any of the coordinates in the rest of the posns
;; e.g., (posns->list points) 'shouldbe (list 1 0 1 1 2 2)
(define (posns->list lop) ...)

;; possible-y-coords : (listof (num -> num)) num -> (listof num)
;; given a list of curves lof and an x-coordinate x, returns the list
;; of what y-coordinate is associated with that x-coordinate in each curve.
;; e.g. (possible-y-coords (list diagonal parabola) 7)
;;      'shouldbe
;;      (list 7 49)
(define (possible-y-coords lof x) ...)

HtDP: 15.1.2, 15.1.3, and 15.1.4

Write the functions
sort-ascending : list-of-numbers -> list-of-numbers
which sorts a list of numbers in ascending order, and
sort-descending : list-of-numbers -> list-of-numbers
which sorts a list of numbers in descending order, or copy them from your notes and prior homework. Circle the differences between them, and write a new function sort-any that is capable of sorting either ascending or descending given the right arguments. Then redefine sort-ascending and sort-descending as functions that do no recursion themselves and just call sort-any with the appropriate arguments.

What is sort-any's contract?

Why does sort-any have to sort lists of numbers specifically?

; sum-pairs : list-of-numbers list-of-numbers -> list-of-numbers
; produces a list of the pairwise sums of the numbers in alon1 and alon2
(define (sum-pairs a-lon1 alon2) ...)

; examples as tests
(sum-pairs empty empty) = empty
(sum-pairs (list 1 3 5) (list 9 25 2000)) = (list 10 28 2005)

; all-in : list-of-numbers list-of-numbers -> boolean
; determines if all of the numbers in alon1 are in alon2
(define (all-in alon1 alon2) ...)

; examples as tests
(all-in empty empty) = true
(all-in (list 1) empty) = false
(all-in empty (list 1)) = true
(all-in (list 1) (list 3 1 4)) = true
(all-in (list 3 1 4) (list 3)) = false

; list-equal? : list-of-numbers list-of-numbers -> boolean
; determines if alon1 and alon2 are identical
(define (list-equal? alon1 alon2) ...)

; examples as tests
(list-equal? (list 1 2 3) (list 1 2 3)) = true
(list-equal? (list 1 2 3) (list 1 2 3 4)) = false
(list-equal? empty empty) = true
(list-equal? empty (list 1)) = false

; 40-year-old-ancestor? : ftree -> boolean
; to determine if a 40-year-old ancestor is in a-ftree
(define (40-year-old-ancestor? a-ftree) ...)

; avg-age : ftree -> number
; to determine the average age in a-ftree
(define (avg-age a-ftree) ...)
Hint: use helper functions

Write the function sort-descending : list-of-numbers -> list-of-numbers that sorts a list of numbers in descending order. How different is this function from the function we wrote in class?

Write the function reverse : list-of-numbers -> list-of-numbers that returns its input with all elements reversed; for example (reverse (list 1 2 3)) should be (list 3 2 1). (Hint: use a wishlist!)

Recall from class:

An ftree is:
  - 'unknown
  - (make-child ftree ftree symbol symbol)
(define-struct child (ma pa eyes name))

DrScheme's built-in functions are exactly the same as the functions we used in class, just with shorter names.

With that in mind, develop the following functions. Don't forget about re-use and helper functions (the functions we wrote in class are fair game for re-use as helper functions).

; a list-of-symbols is either
; - empty, or
; - (cons symbol list-of-symbols)

; contains-doll? : list-of-symbols -> boolean
; to determine if 'doll appears in alos
(define (contains-doll? alos) ...)

; a list-of-numbers is either
; - empty, or
; - (cons number list-of-numbers)

; len : list-of-numbers -> number
; to determine the number of elements in alon
(define (len alon) ...)

; avg : list-of-numbers -> number
; to determine the average of the elements in alon
(define (avg alon) ...)

; add3-to-all : list-of-numbers -> list-of-numbers
; to produce a new list where each number is 3 greater than the 
; corresponding number in alon
; e.g., (add3-to-all (cons 1 (cons 2 empty))) should be (cons 4 (cons 5 empty))
(define (add3-to-all alon) ...)