Overview: Roughly, the assignment will build in steps parts of a pattern matcher for (possibly nested) lists of integers .

(a) To begin with, we define some  atomic patterns, which match single values in Scheme. These include
        _  ; underscore matches any value
       <> ; this symbol matches the null list
       <&> ; this symbol matches any non-null list
        an integer n;   matches itself

Write a simple function
            (matchAtomic atomicp val)
that returns #t iff the atomic pattern atomicp matches value val. Thus
     (matchAtomic 1 1)  yields #t
     (matchAtomic 1 '(1))  yields #f
     (matchAtomic '_  '(1 2))  yields #t
     (matchAtomic '<&>  '3)  yields #f.
     (matchAtomic '<>  '(4))  yields #f.

Testing suggestion: try all possible combinations of
 atomicp= '_ '<> '<&> '2   with val= '3 '2 '() '(1 (2) 3)

(b) Next, let's extend pattern matching to lists: a list of atomic patterns matches a list of values iff the atomic patterns match the values left to right. (This means that the pattern must have the same length as the object list.)

Write a function
      (matchList patList valList)
that performs this matching.
      (matchList '(1 _) '(1 2))   yields #t
      (matchList '(<> 2 <&>) '(() 2 (3 4))) yields #t
      (matchList '(1 _) '(1))  yields #f
      (matchList '(1 _) '(2 1)) yields #f.

For full credit  you must use in an **essential/non-trivial** way some of the higher order functions map1, map2, reduceUs, accumUs  defined at the end.

 (c) (Motivation: Note that the set of atomic patterns presented above is very short.  We could introduce a pattern for odd numbers, say, but this is totally arbitrary. Moreover, patterns like '<> or "odd number" have corresponding Scheme functions, null? and odd?, which may be built in or defined by us. ) Generalize atomic patterns to include arbitrary functions f, with the semantics that pattern f matches value v iff f returns #t for argument v. (f can be a built-in or user-defined function!) For example, even? will match 2 but not 1, nor '(2). Write a new version of matchAtomic, called matchAtomic2, which also accepts functions as atomic patterns.  So, in addition, to (a),

 (matchAtomic2 null? '())  yields #t
 (matchAtomic2 null? '2)  yields #f

 Note: the creation of patterns using the list function, rather than quote is essential: using pattern '(1 null?) would result in trying to compute the value of 'null? function (instead of the null? function) at some argument, giving a runtime error.
 

(d) Rather than just having '_ matching any value, lets enhance it with "variables", which will be symbols starting with $ in our case. Such patterns match anything, but they get "bound" (into a list of pairs) to the value matched (The idea, though not the syntax, is inspired by Prolog). So not only does $x match 3, but the result is a list with the pair ($x 3) in it.

Modify your definitions in (a) and (b)  to obtain matchAtomic3 and matchList3 such that

 (matchList3  '(1 $x $y)  '(1 2 3))  yields  ( ($x 2) ($y 3))    ;; successful match with variables
 (matchList3  '(1 _)  '(1 2))    yields    ()    ;; successful match without variables just produces ()
 (matchList3  '($x $y 4)  '(1 2 3)) yields #f    ;; unsuccessful match returns #f

 The use of higher order functions will continue to be rewarded, though it becomes harder here.

HELPER FUNCTION: to test if the name of a value is a symbol beginning with $ sign, use

(define (isVar? val)
    (and (symbol? val) (equal? #\$ (string-ref (symbol->string val) 0))))

You can assume that every variable occurs at most once in a pattern, so there is no problem with multiple bindings of the same identifier.
 

(e) Extend your definitions in (a) and (b) to handle *nested* patterns  such as '(1  ((_  <&>))), so that
   (matchList4 '(_  (<&> 2) )  '(3  ((1 4) 2) ))  yields #t

(This is easy, if you think about it the right way.)

As usual, in order to have automatic running of your programs please make sure that your function names are correctly written. One way to assure this is to run some of our tests from the file provided.

   (define (map1 f L) 
     (if (null? L) () 
	 (cons (f (car L))  (map1 f (cdr L)))
	 ))

   (define (map2 f LA LB)
     (if (null? LA) ()
	 (cons (f (car LA) (car LB)) (map2 f (cdr LA) (cdr LB)))
	 ))

   (define (reduceUs f ls init)
     (cond
      ((null? ls)  init)
      (else        (f (car ls) (reduceUs f (cdr ls) init)))
      ))

   (define (accumUs f ls init)
     (cond
      ((null? ls)  init)
      (else        (f  (accumUs f (cdr ls) init) (car ls)))
      ))