LISP Tutorial
COMP712 Programming Languages
AUT
1
Exercise #1
Write a LISP function, switch, which given two lists as arguments will return the first list except its first element is replaced by the last element of the second list. For example:
> (switch ‘(a b c d) ‘(e f g)) (g b c d)
An example of a simple Q in the exam
(defun switch (L1 L2)
(append (last L2) (cdr L1)))
2
12
Exercise #2
Write a LISP function, switch2, which given any number of lists as arguments will return the first list except its first element is replaced by the last element of the second list, its second element is replaced by the last element of the third list, and so on. For example:
> (switch2 ‘(a b c d) ‘(e f g) ‘(k l)) (g l c d)
> (switch2 ‘(a b c d) ‘(e f g) ‘(k l) ‘(m n o) ‘(1 2 3) ‘(4 5 6)) (g l o 3)
3
;; recall &rest cannot be used as part of a recursive fn
(defun switch2 (L1 &rest L2) (switch2-aux L1 L2))
(defun switch2-aux (L1 L2) (cond ((null L1) nil) ((null L2) L1)
(t (append (last (car L2))
(switch2-aux (cdr L1) (cdr L2))))))
An example of a slightly more complicated Q in the exam.
4
34
Exercise #3
Write sum which given a list of numbers will return the sum of all the numbers in it?
Ø (sum ‘(1 2 3 4 5)) à 15 Ø (sum ‘(1 2 3)) à 6
Ø (sum nil) à 0
5
Writing a simple recursive solution that performs the task directly.
(defun sum (L) (cond ((null L) 0)
(t (+ (car L) (sum (cdr L))))))
A typical recursive solution – if you can’t write this, you are in troubleL
6
56
1
But, you should learn how to use the powerful features provided by your language:
Write sum which given a list will return the sum of all the numbers in it?
The task is sum all the numbers i.e. in functional terms apply sum to the data and return its value
(defun sum (L) (apply #’+ L))
7
Exercise #4
Write a function my-sum-odd which given a number and a list of numbers will return the sum of all the odd numbers in the list plus the number itself:
> (my-sum-odd 100 ‘(1 2 3 4)) 104
> (my-sum-odd 100 ‘()) 100
8
78
Writing a recursive solution by considering all the cases needed:
(defun my-sum-odd (n L) (cond ((null L) n)
((evenp (car L)) (my-sum-odd n (cdr L))) (t (+ (car L) (my-sum-odd n (cdr L))))))
Again, the above is a typical recursive solution that is afforded in most programming languages
9
Learn how to use the powerful features provided by your language:
Write a function my- sum-odd which given a number and a list of numbers will return the sum of all the odd numbers in the list plus the number itself:
Breakdown the tasks:
N + sum of all odd nos Remove even nos
Add remaining odd nos
10
9 10
Breakdown the tasks and think of using functions:
N + sum of all odd nos
Remove even nos Add all nos
(+ N (apply #’+ (remove-if #’even L))
(apply #’+
(remove-if #’even L))
(apply #’+ L)
11
Exercise #5
Write sum2 which given a list will return the sum of all the numbers in it?
Ø (sum2 ‘(1 2 3 4 5)) à 12 Ø (sum2 ‘(1 2 a b 3)) à 6 Ø(sum2) à0
12
11 12
2
Again, a simple recursive solution:
(defun sum (L) (cond ((null L) 0)
((numberp (car L)) (+ (car L)
(sum (cdr L))))
(t (sum (cdr L)))))
How about writing a solution in a functional language?
13
Identifying the functional needs of the problem
Write sum which given a list will return the sum of all the numbers in it?
Breaking down the tasks: sum of all numbers
(apply #’+ L)
Remove non numbers
14
(remove-if-not #’numberp L) (apply #’+ (remove-if-not #’numberp L)
(defun sum (L)
13 14
Exercise #6
Write a LISP function, add-up, which given a list of lists of numbers will return a list of lists of the sum of those numbers:
> (add-up ‘((1 2 3) (4 5) (6 7 8 1))) ((6) (9) (22))
> (add-up ‘((1 2 3) () (4 5) (6 7 8 1))) ((6) (0) (9) (22))
Try to generate a functional solution
15
Identifying the functions needed:
Given a list of lists, add up the numbers in each list and return as a list
Add up numbers in a list and return result as a list
(list (apply #’+ L))
Apply the above task to every list in it
16
(mapcar the above fn to L) (mapcar #’(lambda (x) (list (apply #’+ x))) L))
(defun add-up (L)
15 16
Otherwise, your typical recursive solution, in any language, would be like:
(defun add-up (L) (if (null L) nil
(cons (add-list (car L)) (add-up (cdr L)))))
(defun add-list (L)
(if (null L) 0 (+ (car L) (add-list (cdr L)))))
You need two functions; isn’t it ugly?
17
Exercise #7
Write a function to compute the dot product of two sequences of numbers represented as lists. The dot product is computed by multiplying corresponding elements and then adding up the resulting products. For example:
Ø (dot-product ‘(10 20) ‘(3 4)) ; = 10*3 + 20*4 110
Ø (dot-product ‘(10 20 1) ‘(3 4 1)) ; = 10*3 + 20*4 + 1*1 111
18
17 18
3
Exercise #7
; = 10*3 + 20*4 (dot-product ‘(10 20) ‘(3 4))
*
+ +..
(defun dp (L1 L2)
(apply #’+ (mapcar #’* L1 L2)))
19
*
Applying the fn * to each element
Add them all together
Exercise #8
Write a function, lotto, that generates six numbers for you. You may use the function, random, that will give you a random number as shown below:
Ø (random 40) ;return a number <= 40 39
But, beware the function, random, returns 0 – 40 and hence you have to remove zero if generated. Also, you don’t want to include a number that has already been generated.
> (lotto)
(3 7 20 40 32 11)
20
19 20
The idea: get six numbers and form them into a list but what are the problems?
1st – random gives 0-40. So, need to return 1-40
2nd – no repeated numbers
That means, you have to write your own random and then a function to give you 6 lotto numbers
21
Writing my-random function:
You could call (random 40) and it gives you a number. So, what do you need to add?
Check if number is 0, then
get another one. Straightforward,
right?
Check if number is repeated, then get another one Tricky?
22
21 22
Writing my-random function:
Check if number is repeated, then get another one
You need to pass the numbers generated for every subsequent call for random. Assume you pass that as a list.
(defun my-random (num-so-far) (let ((x (random 40)))
(if (and (> x 0) (not (member x num-so-far)) x (my-random num-so-far))))
23
Let’s try to use my-random function:
(defun lotto ()
what do you need to do here?
You need to call my-random 6 times, right?
But, each time, you also need to capture its result and pass it to the next call for my- random to get 6 unique numbers.
So, you need a local variable to hold on to the numbers generated so far.
24
23 24
4
I do it this way:
Instead of passing a list, I created my-random that I could pass any number of arguments and use &rest to gather them as a list.
(b (my-random a))
(c (my-random a b))
(d (my-random a b c))
(e (my-random a b c d)) (f (my-random a b c d e)))
(list a b c d e f)))
(defun lotto ()
(let* ((a (my-random))
(defun my-random (&rest existing-num) (do ((x (random 40) (random 40)))
((and (> x 0) (not (member x existing-num))) x)))
25
25
5