LISP Tutorial2
COMP712 Programming Languages
AUT
1
Exercise #1
Write a function, zip, which takes as its argument two lists and returns a list of corresponding elements from the two lists.
> (zip ‘(red green yellow) ‘(apple kiwi banana) ((red apple) (green kiwi) (yellow banana))
(defun zip (L1 L2) (mapcar #’list L1 L2)
2
12
Exercise #2
Using mapcar, write a function that counts all the top-level elements in a list (i.e re-write length using mapcar).
Ø(my-count ‘((a b) (c d) (e f))) 3
(defun my-count (L) (apply #’+
(mapcar #’(lambda (x) 1) L)))
3
(defun my-count (L)
(apply #’+ (mapcar #’(lambda (x) 1) L)))
Ø(my-count ‘((a b) (c d) (e f))) 3
Ø(my-count ‘((a b) (c d) () (e f))) ? 4 i.e. () is counted
(defun my-count (L) (apply #’+
(mapcar #’(lambda (x) (if (null x) 0 1)) L)))
4
34
Exercise #3
Using mapcar, write a function that counts all the top-level elements in a list (i.e re- write total-length using mapcar).
Ø(my-count2 ‘((a b) (c d) (e f))) 6
(defun my-count (L)
(apply #’+ (mapcar #’(lambda (x) 1) L)))
(defun my-count2 (L)
(apply #’+ (mapcar #’(lambda (x)
(if (null x) 0
(if (atom x) 1 (my-count2 x)))) L)))
5
Exercise #4
Write my-cnt-if which takes a predicate function and a list and returns the number of top-level elements in the list that satisfy the predicate.
Ø (my-cnt-if #’(lambda (x) (> x 10)) ‘(12 3 14 5)) 2
Ø (my-cnt-if #’evenp ‘(1 2 3 4 5 6 7)) 3
6
56
1
Write my-cnt-if which takes a predicate function and a list and returns the number of top-level elements in the list that satisfy the predicate.
(defun my-count-if (pred L) (cond ((null L) 0)
(t (if (funcall pred (car L))
(+ 1 (my-count-if pred (cdr L))) (my-count-if pred (cdr L)) ))))
In this example, I want to highlight the use of funcall.
7
Write my-cnt-if which takes a predicate function and a list and returns the number of top-level elements in the list that satisfy the predicate.
Alternatively using mapcar-style:
(defun my-cnt-if (pred L)
(length (remove-if-not pred L)))
8
78
Exercise #5
Write a function sum-tree which given a binary tree will return the sum of all its leaf nodes:
Ø(sum-tree ‘(a (b (c 2 3) (d 2 3))
93
(e (f 43 (h 1 9)) 30)))
(defun sum-tree (L)
(let ((left-tree (second L)) (right-tree (third L)))
(+ (if (numberp left-tree)
left-tree (sum-tree left-tree))
(if (numberp right-tree)
right-tree (sum-tree right-tree)))))
9
(defun sum-tree (L)
(let ((left-tree (second L)) (right-tree (third L)))
(+ (if (numberp left-tree)
left-tree (sum-tree left-tree))
(if (numberp right-tree)
right-tree (sum-tree right-tree)))))
The key to finding a solution here is to realise using LET to introduce 2 local variables, one to hold the left tree and the other toholdtherighttree.
a
be
c
2 3 2 3 43 h
1
df
30
9
10
9 10
Exercise #6
Write a function collect-leaves which given a binary tree will return a list of all its leaf nodes:
Ø (collect-leaves ‘(a (b (c 2 3) (d 2 3)) (e (f 43 (h 1 9)) 30)))
(2 3 2 3 43 1 9 30)
(defun collect-leaves (L)
(let ((left-tree (second L)) (right-tree (third L)))
(append (if (numberp left-tree)
(list left-tree) (collect-leaves left-tree))
(if (numberp right-tree)
(list right-tree) (collect-leaves right-tree)))))
11
Exercise #7
Write a function, uniform, that given a list will check whether it has more lists or atoms in it. Then return a list that change all its elements into the form that is the majority. If equal, return a list with a form of your choice.
Ø(uniform ‘(a b (2 3) 4 (a f))) Ø(a b 2 3 4 a f)
Ø (uniform ‘(a b c (2 3) (w) (f)))
either (a b c 2 3 w f) or ((a) (b) (c) (2 3) (w) (f))
12
11 12
2
Exercise #7
(defun uniform (L)
(let ((L1 (length (remove-if #’listp L)))
(L2 (length (remove-if-not #’listp L))) (all-list (mapcar #’(lambda (x)
(if (listp x) x (list x))) L)))
(if (> L2 L1) all-list (apply #’append all-list))))
If equal number of lists and atoms, what does this algorithm give you? A list of atoms
13
Exercise #8
Write max-female which given a list of names, ages, and sexes return the oldest female in the list.
Ø (max-female
‘((jane 10 f) (joe 12 m) (mary 5 f) (abdul 8 m)))
(jane 10 f)
I am thinking of removing the male from the list and then find the max
14
13 14
Removing the male from L means I need a local variable. I also need a variable to hold the current oldest female:
(defun max-female (L)
(let* ((fL (remove-if #’(lambda (x)
(equal (third x) ‘m)) L))
(result (car fL))) (dolist (x (cdr fL) result)
(setf result
(if (> (second x) (second result)) x result)))))
15
15
3