In this post the association lists I am describing are of the latter type viz., a list of two element lists.
A two element list is of the form (x1 y1) and thus the association list is of the form ((x1 y1) (x2 y2) ... (xn yn)).
The pair. function
The pair. function takes in two lists, x and y as arguments and returns an association list.Ideally, the two lists x and y must be of the same length. Thus, (pair. '(x1 x2 ... xn) '(y1 y2 ... yn)) will return the association list ((x1 y1) (x2 y2) ... (xn yn)).
The code for the pair. function and other functions used in pair. are given below :
(defun pair. (x y)
(cond ((and. (null. x) (null. y)) '())
((and. (not. (atom x)) (not. (atom y)))
(cons (list (car x) (car y))
(pair. (cdr x) (cdr y))))))
(defun and. (x y)
(cond (x (cond (y 't) ('t '())))
('t '())))
(defun null. (x)
(eq x '()))
(defun not. (x)
(cond (x '())
('t 't)))
A skeletal overview
(defun pair. (x y)
(cond ((and. (null. x) (null. y)) '())
(p2 e2)))
As can be seen from the above code, the pair. function consists of two condition checks. It first checks if both x and y are nil. If that is the case, then, it returns nil as it should. Try,
;; The base case when both x and y are nil.
(pair. '() '())
If the first condition check fails, then it proceeds to the next condition check, p2, which is
(and. (not. (atom x)) (not. (atom y)))
The above check ensures that both x and y are not atoms. Note that
nil is an atom. Thus if even one input x or y is an atom then the second
check fails.
In a cond form, every condition is checked one after another. If the last one fails, then the cond form returns nil. Thus, in our pair. function if the second condition check, p2, fails, then the function returns nil, as p2 is the last condition in the cond form.
However, if p2 returns t then the expression e2 as given below is evaluated. As can be guessed, e2 is where the major work is done. Like the functions subst1 and append., the function pair. also contains a recursive call to itself.
(cons (list (car x) (car y))
(pair. (cdr x) (cdr y)))
;; The function "list" takes in arbitrary elements as input
;; and creates a list of those elements
(list) ==> ()
(list '1) ==> (1)
(list '1 '2) ==> (1 2)
(list '1 '2 '3 '4 '5 '6) ==> (1 2 3 4 5 6)
(list '(1 2) '(3 4)) ==> ((1 2) (3 4))
Thus, what the expression e2 really does is it creates a list of the first element of x and the first element of y and then it conses this two element list onto the recursively created association list
pair. (cdr x) (cdr y)) .
Now to summarize the way in which pair. works. First, let's look at the code again
(defun pair. (x y)
(cond ((and. (null. x) (null. y)) '())
((and. (not. (atom x)) (not. (atom y)))
(cons (list (car x) (car y))
(pair. (cdr x) (cdr y))))))
It first checks if both x and y are nil. If that is the case it returns nil.
If the first check fails, then, it checks if both x and y are not atoms in which case
most probably they are lists. If this is true then, we create a list consisting of the first element
of x and the first element of y. This list is then attached to the front of the
recursive call to (pair. (cdr x) (cdr y)) . If the second check too fails, however, then the cond form returns nil. Thus this results in an association list whose length is equal to the number of elements in the shortest list if the lengths of the two lists are unequal.
Now, for a few examples.
;;Boundary examples where the length of one of the lists is smaller
(pair. '(1) '()) ==> ()
(pair. '(1) '(a b)) ==> ((1 a))
Now for a proper example, where the lengths of both lists are equal.
(pair. '(1 2 3) '(a b c))
a) (pair. '(1 2 3) '(a b c))
|
|
_______________cons____________
/ \
/ \
(list (car '(1 2 3)) (car '(a b c))) (pair. (cdr '(1 2 3)) (cdr '(a b c)))
||
||
\/
b) (pair. '(1 2 3) '(a b c))
|
|
_______________cons____________
/ \
/ \
(list '1 'a) (pair. '(2 3) '(b c))
||
||
\/
c) (pair. '(1 2 3) '(a b c))
|
|
_______________cons____________
/ \
/ \
'(1 a) (pair. '(2 3) '(b c))
|
|
_______________cons____________
/ \
/ \
(list '2 'b) (pair. '(3) '(c))
||
||
\/
d) (pair. '(1 2 3) '(a b c))
|
|
_______________cons____________
/ \
/ \
'(1 a) (pair. '(2 3) '(b c))
|
|
_______________cons____________
/ \
/ \
'(2 b) (pair. '(3) '(c))
|
|
____cons____
/ \
/ \
'(3 c) (pair '() '())
|
|
'()
||
||
\/
e) (pair. '(1 2 3) '(a b c))
|
|
_______________cons____________
/ \
/ \
'(1 a) _______________cons____________
/ \
/ \
'(2 b) ____cons____
/ \
/ \
'(3 c) ()
||
||
\/
f) (cons '(1 a) (cons '(2 b) (cons '(3 c) ()))) ==> ((1 a) (2 b) (3 c))
Thus,
(pair. '(1 2 3) '(a b c)) ==> ((1 a) (2 b) (3 c))
Now, let's have a look at what happens when one of the lists is bigger than the other. Take a modification of the previous example,
(pair. '(1 2 3) '(a b c d e))
In the above example the length of the second element is larger than the first. The intermediate
stages that the above example passes through is the same as the previous example from a) to c)
except for a few minor differences. At step d) however, this is what happens,
d) (pair. '(1 2 3) '(a b c d e))
|
|
_______________cons____________
/ \
/ \
'(1 a) (pair. '(2 3) '(b c d e))
|
|
_______________cons____________
/ \
/ \
'(2 b) (pair. '(3) '(c d e))
|
|
____cons____
/ \
/ \
'(3 c) (pair '() '(d e))
|
|
'()
After that the steps are the same as in the previous example (from e) to f)).
Thus once again, we have
(pair. '(1 2 3) '(a b c d e)) ==> ((1 a) (2 b) (3 c))
Similarly,
(pair. '(1 2 3 4 5) '(a b c)) ==> ((1 a) (2 b) (3 c))
0 comments:
Post a Comment