Scheme Assignment 1+

I've decided to give certain deserving people an extension to the
Scheme assignment and at the same time give everybody something to do
during the week-long break before our next class (no class on 10/6 -
graduate or undergraduate).  The assignment is now due on 10/8, with
the following additions:

1. Using the code I wrote for generating spanning trees (but only
   include what you need), write a program to determine if a directed
   graph is connected.  A graph is connected if there are paths
   between every pair of nodes - i.e., it's possible to go from one
   node to every other node.  If you generate a spanning tree and that
   tree includes all the nodes of the original graph, then the graph
   is connected.

  ; Hint: Use the "vertices" function I defined for you, and the 
  ; following:

  ; Determines if A and B have the same elements, not necessarily
  ; in the same order:
  (define (eqlist A B) (and (sublist A B) (sublist B A)))

  Note that there are actually two notions of connectedness: weak and
  strong.  Weakly connected means that there is SOME node from which the
  spanning tree will reach all nodes.  Strongly connected means it doesn't
  matter where you start the spanning tree from, you will reach all nodes.
  In other words, if the graph is connected in one direction, it's weakly
  connected.  You can implement either strong or weak connectedness, but
  you need to indicate which.


2. Modify the spanning tree program into one that determines if there
   are any cycles in the graph - i.e., if there's a path from some
   vertex back to itself.  Note that you must run your cycle detection
   program on *every* node in order to be sure if there are or are not
   any cycles.  You know that a cycle exists if when you expand the
   search frontier you get a new node that's seen before, i.e., that's
   inside the old frontier, or set of interior nodes (you can't just
   use cons1 and union - since they won't tell you if there are
   duplicates).

; Hint: Modify the span function to return #f if there's a cycle
; (note that span is tail recursive - so it'll stop the graph search)

; Determines if there's an element that appears in both lists:
(define (intersect A B)
  (cond ((null? A) #f)
        ((null? (cdr A)) (member (car A) B))
	(#t (or (member (car A) B) (intersect (cdr A) B)))))



----

You might (not required) also want to take advantage of higher-order
programming, namely the map, fold, forall and exists that I talked
about earlier, and which you implemented.  The definitions of a lot
of predicates can be made clearer - in the sense of mathematical
clarity - if you use these higher-order constructs:

(define (intersect A B)
  (exists (lambda (x) (member x B)) A))

(define (sublist A B)
  (forall (lambda (x) (member x B)) A))

Here's another higher order function that filters out only those elements
that satisfy some boolean property:

(define (suchthat p l)
  (if (null? l) l
     (if (p (car l)) (cons (car l) (suchthat p (cdr l)))
         (suchthat p (cdr l)))))

For example, (suchthat (lambda (x) (> x 3)) '(1 4 2 7)) will return
'(4 7) - all elements that are greater than 3.


; now you can do "logic programming" in scheme: that is, program by
; writing down logical definitions:

; finds the intersection of two lists that really represents sets:
; (the function intersect above only returns #t or #f):

(define (intersection A B)
  (suchthat (lambda (x) (member x B)) A))

; returns set A minus set B:
(define (diff A B)
  (suchthat (lambda (x) (not (member x B))) A))