CMPU-145, Spring 2013
Lab 3 Instructions
Feb. 18, 2013


In this lab, you will use Scheme's DOLIST special form.  Its use is
illustrated below:

    > (define listy '(1 2 3 4 5))
    > (dolist (x listy)
              (printf "x: ~A~%" x))
    x: 1
    x: 2
    x: 3
    x: 4
    x: 5

    > (dolist (x '(a b c d))
              (printf "x: ~A~%" x))
    x: a
    x: b
    x: c
    x: d

In the last example, the PRINTF expression in the body of the DOLIST
is evaluated 4 times, once for each item in the list.  The first time
the body is evaluated, the value of X is the first element of the list;
the second time the body is evaluated, the value of X is the second element
of the list; and so on.

Note that the body of a DOLIST may contain multiple expressions, as
illustrated below.

    > (dolist (x '(a b c))
              (printf "---[")
              (print x)
              (printf "]---~%"))
    ---[a]---
    ---[b]---    
    ---[c]---


PROBLEM 1.

  Define a function, called PRINT-ALL-PAIRS, that takes a single list, LISTY,
  as its only input.  It should not return any output value.  However,
  it should have the side-effect of printing out all pairs whose elements
  are drawn from LISTY, as illustrated below:

    > (print-all-pairs '(a b c))
    (a,a) (a,b) (a,c) (b,a) (b,b) (b,c) (c,a) (c,b) (c,c) 

  HINT:  Use two DOLIST expressions, one nested inside the other.


PROBLEM 2.

  Define a function, called ACCUM-ALL-PAIRS, that takes a single list, LISTY,
  as its only input.  It should return as its output a list containing all
  pairs whose elements are drawn from LISTY, as illustrated below:

    > (accum-all-pairs '(a b c))
    ((c c) (c b) (c a) (b c) (b b) (b a) (a c) (a b) (a a))
    > (length (accum-all-pairs '(a b c)))
    9

  As the last example shows, the list of pairs is returned as an output value;
  thus, it can be used as an input to the LENGTH function.

  HINT:  Use nested DOLISTS, as in problem 1.
         However, also declare a local variable (using LET) called ACC
           whose value will initially be ().
         In the body of the inner DOLIST, use the SET! function to
         *destructively* modify the value of ACC (to accumulate the
	 next pair).

         Here is an example of how SET! works.

    > (define listy '(a b c))  
    > (set! listy (cons 'x listy))
    > listy
    (x a b c)

         Normally, I don't encourage destructive programming.
	 However, here, it is acceptable because we are only modifying
	 the value of a local variable.

PROBLEM 3.

  Define a function, called FIND-SAT-PAIR, that takes two inputs: LOL,
  a list of pairs; and PRED a function that takes two inputs and
  returns a boolean output (#t or #f).  FIND-SAT-PAIR should returns
  as its output a pair (x y) from LOL such that (pred x y) holds.  If
  no such pair exists, then FIND-SAT-PAIR should return #f.

  Here are some examples:

    > (find-sat-pair '((1 2) (2 3) (4 2) (5 1) (6 3))
                     (lambda (x y) 
                       (= x (* y y))))
    (4 2)

    > (find-sat-pair '((1 2) (3 4) (5 4) (6 2))
                     >)
    (5 4)

    > (find-sat-pair '((1 2) (3 4) (5 14) (6 12))
                     >)
    #f

  Note that there is a difference between, say, (< '(3 4)) and
  (< 3 4).  One will cause an error; one will be fine.

  NOTE:  You need not use DOLIST here; it's easer to program the
         recursion directly.


PROBLEM 4.

  Define a function, called FIND-SAT-PAIR-FROM, that takes two inputs,
  LISTY and PRED, where LISTY is a list and PRED is a function that takes
  two inputs and returns a boolean output.  FIND-SAT-PAIR-FROM should return
  a pair, (x y), where x and y are both elements of LISTY, such that 
  (pred x y) returns #t.  If no such pairs exist, it should return #f.
  Here are some examples:

    > (find-sat-pair-from '(1 2 3 4 5) >)
    (5 4)
    > (find-sat-pair-from '(1 2 3 4 5)
                          (lambda (x y)
                            (= x (* y y))))
    (4 2)

  HINT:  Use ACCUM-ALL-PAIRS to generate all pairs from LISTY, and then
         use FIND-SAT-PAIR to find the desired pair.


-----------------------

  When you are done, ask a coach to come over to check your work.
  And then submit electronically, using submit145, as usual.