Simple LISP
1. (car ‘x)
2. (cdr ‘x)
3. (cadar ‘((a b c) (d) ‘(e f)))
error error b
4. (append ‘(a b) ‘c ‘(d e f) ‘g) error
5. (list‘(ab)‘c‘(def)‘g)
((a b) c (d e f) g)
1
LISP & Functional Programming
Write a function, Combine, which given 3 lists will return a list of all the 3 lists without their first element:
Ø(combine ‘(1 2 3) ‘(4 5 6) ‘(7 8 9)) ((2 3) (5 6) (8 9))
Ø (combine ‘(1 2 3) () ‘(7 8 9)) ((2 3) () (8 9))
2
12
34
LISP & Functional Programming
Write a function, Combine, which given 3 lists will return a list of all the 3 lists without their first element:
given 3 lists
return a list of all the 3 lists
without their first element
L1 L2 L3
(list L1 L2 L3)
(list (cdr L1) (cdr L2) (cdr L3))
3
LISP & Functional Programming
given 3 lists
return a list of all the 3 lists
without their first element
L1 L2 L3
(list L1 L2 L3)
(list (cdr L1) (cdr L2) (cdr L3))
Selecting the right functions for solving your problem is an essential step in functional programming.
4
LISP & Functional Programming
Write a function, Combine, which given 3 lists will return a list of all the 3 lists without their first element. Answer:
(Defun combine (L1 L2 L3)
(list (cdr L1) (cdr L2) (cdr L3)))
5
LISP & Functional Programming
Write a function, combine-last, which given 3 lists will return a list of all their last element:
Ø (combine-last ‘(1 2 3) ‘(4 5 6) ‘(7 (8 9))) (3 6 (8 9))
Ø (combine-last ‘(1 2 3) () ‘(7 8 9)) (3 9)
6
56
1
LISP & Functional Programming
Write a function, combine-last, which given 3 lists will return a list of all their last element:
L1 L2 L3
(list L1 L2 L3)
(list (last L1) (last L2) (last L3))
given 3 lists
return a list of all the 3 lists
Get the last element
7
LISP & Functional Programming
Write a function, combine-last, which given 3 lists will return a list of all their last element:
(Defun combine-last (L1 L2 L3) (liXst (last L1) (last L2) (last L3)))
append – why?
8
78
LISP & Functional Programming
In programming, functional or not, it is important to ensure you got the correct representation.
(last ‘(a b c)) (c) (list (last L1) (last L2)
((3) (6) ((8 9))) To remove the extra (append (last L1)
(last L3)) brackets, do:
(last L2) (last L3))
9
LISP & Functional Programming
Write a function, Drop-x, that given a number, x, and a list will return the list with the first x elements removed. X is a number between 0 and 3 :
(Defun drop-x (x L) (cond ((= x 1) (cdr L))
((= x 2) (cddr L)) ((= x 3) (cdddr L)) (t L)))
Would a recursive/iterative function be better?
10
9 10
It is often said a PL needs to have expressive power. But then you still need to learn how to express clearly your intended solution.
(Defun drop-x (x L) (cond ((= x 1) (cdr L))
((= x 2) (cddr L)) ((= x 3) (cdddr L)) (t L)))
(Defun drop-x (x L) (cond ((zerop x) L)
(t (drop-x (1- x) (cdr L)))))
This portrays that you have 3 cases only
This portrays a more general function
11
Recursive functions
Write a function, my-length, that given a list, will return a count of all the top-level elements in it.
Ø (my-length‘(1 2 b (c 3) d)) 5
(defun my-length (L) (cond ((null L) 0)
(t (1+ (my-length (cdr L))))))
12
11 12
2
Recursive functions
Writing a recursive solution is about identifying what you want to do fundamentally (i.e. base case) and how you combine the result at the end.
Ø (my-length‘(1 2 b (c 3) d))
How to identify It is the step that gives you an
the base case? answer directly.
Think of what you need to do given the base case
You take each element and count!
13
Recursive functions
Write a recursive solution is about identifying what you want to do with the base case and how you combine the result with a recursive call.
Ø (my-length‘(1 2 b (c 3) d)) Base case: Empty list – 0
Next: Youknowthereis1element+thesumof the remaining elements in the list.
14
13 14
Recursive functions
Write a recursive solution is about identifying what you want to do with the base case and how you combine the result with a recursive call.
Ø (my-length‘(1 2 b (c 3) d))
Base case 1 + sum of remaining elements
0 1 + (my-length (2 b (c 3) d))
15
Recursive functions
Write a function, my-length, that given a list, will return a count of all the top-level elements in it.
Ø (my-length‘(1 2 b (c 3) d)) 5
Hence, the answer:
(defun my-length (L)
(cond ((null L) 0) ; base case
(t (1+ (my-length (cdr L))))))
16
15 16
Recursive functions
Write a function my-total-length which given a list of lists will return a count of ALL elements in it:
Ø (my-length‘(1 2 b (c 3) d))
Base case 1 + sum of remaining elements
0 What needs to change here?
17
Recursive functions
Write a function my-total-length which given a list of lists will return a count of ALL elements in it:
Ø (my-total-length‘(1 2 b (c 3) d)) Let’stryit: 1 +1+1+?
This is not necessarily a 1. It could be a list and we need to sum it
18
17 18
3
Recursive functions
Write a function my-total-length which given a list of lists will return a count of ALL elelments in it:
(defun my-total-length (L) (cond ((null L) 0)
((atom L) 1)
(t (+ (my-total-length (car L))
(my-total-length (cdr L))))))
Such a function is known as a doubly recursive function
19
Recursive functions
Compare these two recursive functions:
(defun my-length (L) (cond ((null L) 0)
(t (1+ (my-length (cdr L))))))
(defun my-nth (n L) (cond ((= n 1) (car L))
(t (my-nth (- n 1) (cdr L)))))
20
19 20
21 22
Recursive functions
(defun my-length (L) (cond ((null L) 0)
(t (1+ (my-length (cdr L)))))) (my-length ‘(a b c d))
L: ()
L: (c d)
1+
1
1+
0
= Data frame
21
L: (d)
L: (b c d)
L: (a b c d)
Code: 1 +
1+
2
3
Recursive functions
(defun my-nth (n L) (cond ((= n 1) (car L))
(t (my-nth (- n 1) (cdr L)))))
(my-nth 3 ‘(a b c d))
L: (c d) n: 1
c
L: (b c d) n: 2
L: (a b c d) n: 3
22
Tail recursive functions
My-nth is tail recursive.
(defun my-length (L) (cond ((null L) 0)
(t (1+ (my-length (cdr L))))))
(defun my-nth (n L) (cond ((= n 1) (car L))
(t (my-nth (- n 1) (cdr L)))))
Which is more efficiently implemented?
23
Tail recursive functions
Turn my-length into tail recursive
(defun my-length (L) (cond ((null L) 0)
(t (1+ (my-length (cdr L))))))
(defun my-nth (n L) (cond ((= n 1) (car L))
(t (my-nth (- n 1) (cdr L)))))
24
23 24
4
Recursive functions
In other words, you want it to return the result once you got it!
(my-length ‘(a b c d))
L: (a b c d)
L: (c d)
L: () L: (d)
25
L: (b c d)
Tail recursive functions
My-length is now tail recursive
(defun my-length (cnt L) (cond ((null L) cnt)
(t (my-length (1+ cnt) (cdr L))))))
(defun my-nth (n L) (cond ((= n 1) (car L))
(t (my-nth (- n 1) (cdr L)))))
26
25 26
27 28
Recursive functions
(defun my-length (ans L) (cond ((null L) 0)
(t (my-length (1+ ans) (cdr L)))))
L: () ans: 4
4
27
(my-length ‘(a b c d))
L: (d)
ans: 3 L: (c d)
ans: 2
L: (b c d) ans: 1
L: (a b c d) ans: 0
Can you tell me what has changed?
Tail recursive functions
(defun my-length (cnt L) (cond ((null L) cnt)
(t (my-length (1+ cnt) (cdr L)))))) How do you call my-length now?
Ø(my-length 0 ‘(a b c d)) 4
This function is ugly and strange, why?
28
Tail recursive functions
To make it more elegant, we can do:
(defun my-length (L) (my-length-aux 0 L))
(defun my-length-aux (cnt L) (cond ((null L) cnt)
(t (my-length-aux (1+ cnt) (cdr L)))))) Still not elegant, why?
29
Optional arguments
Common LISP allows us to do:
(defun my-length (L &optional cnt) (cond ((null L) cnt)
(t (my-length (cdr L) (1+ cnt)))))
That means you can call: (my-length ‘(a b c d)) Awesome! But there is an error! Where?
30
29 30
5
Optional arguments
Need to initialise cnt!
(defun my-length (L &optional (cnt 0)) (cond ((null L) cnt)
(t (my-length (cdr L ) (1+ cnt))))))
Now the function works and you can start writing some pretty good functions
Actually you don’t have to initialise it and if so, it has the value NIL
31
Write a function, my-reverse, that given a list, will reverse the elements in it.
Ø (my-reverse ‘(a b c d e) (e d c b a)
(defun my-reverse (L) (cond ((null L) nil)
(t (append (my-reverse (cdr L)) (list (car L))))))
32
31 32
So, same idea as before: Ø (my-reverse ‘(a b c d e)
Base case
()
What is the function to apply here?
a + (my-reverse (b c d e)) a + (e d c b)
Need to: (e d c b) + a
(e d c b) + (a) = (e d c b a)
33
Write a function, my-reverse, that given a list, will reverse the elements in it.
Ø (my-reverse ‘(a b c d e) (e d c b a)
(defun my-reverse (L) (cond ((null L) nil)
(t (append (my-reverse (cdr L)) (list (car L))))))
Make sure you understand why I use append and list. How about writing a tail-reverse?
34
33 34
(defun my-reverse (L) (cond ((null L) nil)
(t (append (my-reverse (cdr L)) (list (car L))))))
Remember tail-recursive means you want to pass the partial results in the recursive calls
But you need to work out the partial results and pass it together with the recursive call
You don’t need to combine results coming back from recursive calls
35
(defun tail-reverse (L &optional result) (cond ((null L) result)
(t (tail-reverse (cdr L)
(cons (car L) result)))))
(defun my-reverse (L) (cond ((null L) nil)
(t (append (my-reverse (cdr L)) (list (car L))))))
36
35 36
6
Write a tail-recursive function, power-n, that given 2 numbers, n and m, return mn.
(defun power-n (n m &optional (result 1))
First, you get the arguments right. Then the body:
(if (zerop n) result (power-n n? m? ?))
The Q is what should these args be?
37
Write a tail-recursive function, power-n, that given 2 numbers, n and m, return mn.
(defun power-n (n m &optional (result 1)) (if (zerop n) result
(power-n (1- n) m (* result m))))
38
37 38
Other function parameter
What is peculiar about functions like +:
Ø(+ 1 2) 3
Ø(+ 1 2 3 4 5 6) 21
It takes a variable number of arguments
In LISP, you do something like: (defun + (&rest L) …)
39
Any number of argumets
Write a function, collect-what, which given any number of numbers will return a list of all the odd or even numbers depending and excluding the first number. If first number is odd, returns a list of odds, otherwise evens:
Ø(collect-what 1 2 3 4 5 6 7) (3 5 7)
Ø(collect-what 2 3 4 5 6 7) (4 6)
40
39 40
Any number of arguments
Usually we begin:
(defun collect-what (L) …….)
But, knowing that the number of arguments is infinite, I need to use &rest:
(defun collect-what (&rest L)
What the gives me is a collection of those arguments as a list, L.
41
Any number of arguments
Ø(collect-what 1 2 3 4 5 6 7) (3 5 7)
We can think of L as (1 2 3 4 5 6 7)
(defun collect-what (&rest L)
(if (oddp (car L)) (collect-odd (cdr L)) (collect-even (cdr L))))
42
41 42
7
Any number of arguments
Alternatively, knowing that the number of arguments is infinite, I can take the first one and have the rest:
(defun collect-what (n &rest L)
(if (oddp n) (collect-odd L) (collect-even L)))
As compared with:
(defun collect-what (&rest L)
(if (oddp (car L)) (collect-odd (cdr L))
(collect-even (cdr L))))
43
Any number of arguments
(defun collect-what (n &rest L)
(if (oddp n) (collect-odd L) (collect-even L)))
(defun collect-odd (L) (cond ((null L) nil)
((oddp (car L))
(cons (car L) (collect-odd (cdr L))))
(t (collect-odd (cdr L)))))
Exercise: write the function collect-even.
44
43 44
Any number of arguments
(defun collect-what (n &rest L)
(if (oddp n) (collect-odd L) (collect-even L)))
(defun collect-even (L) (cond ((null L) nil)
((evenp (car L))
(cons (car L) (collect-even (cdr L))))
(t (collect-even (cdr L)))))
45
Keywords
Do you see a problem with this function?
(defun which-one (&optional a b c) (list a b c))
Ø(which-one 10)
?
But, what if 10 is meant for variable b or c?
; a gets 10
46
45 46
Keywords
(defun which-one (&key a b c) (list a b c))
Ø(which-one :b 10) (nil 10 nil)
In other words, &key allows you to select which argument you want.
Use &key:
47
Keywords
(defun fun (&optional (b 2) (c 6)) (+ b c))
Exercise:
Ø (fun) 8
Ø(fun 5) 11
48
47 48
8
Keywords
(defun which-one (a &optional b &key c d) (list a b c d))
Ø(which-one 1 2 :d 4) (1 2 nil 4)
Exercise:
49
My view on functional language
One feature that distinguishes a functional language from an imperative language is that the former is designed to enable you to write better/awesome functions.
One consequence of the above is that we may pay a price in terms of efficiency! Writing a better function is not the same as producing efficient codes. Why?
The former focuses on finding a clean abstract solution whereas the latter focuses on finding a solution for the machine.
50
49 50
One more practice
Write a function, max, which given a list of numbers will return the largest number in it.
Ø (max ‘(1 4 3 67 9 4)) 67
How? – take the first number as the max. Then go down the list and compare it with each number in it. If the next number is larger than it, take it as the result.
51
One more practice
Write a function, max, which given a list of numbers will return the largest number in it.
Ø (max ‘(1 4 3 67 9 4)) 67
(defun max (L &optional (ans (car L))) (Cond ((null (cdr L)) ans)
(t (max (cdr L)
(if (> (cadr L) ans) (cadr L) ans)))))
52
51 52
(defun max (L &optional (ans (car L))) (Cond ((null (cdr L)) ans)
(t (max (cdr L)
(if (> (cadr L) ans) (cadr L) ans)))))
How would you modify max so that you can do:
Ø (max 1 4 3 67 9 4) ;input is not a list 67
53
Using &rest
Ø (max 1 4 3 67 9 4) ;input is not a list 67
Can you do this:
(defun max (ans &rest L) (Cond ((null (cdr L)) ans)
(t (max (if (> (car L) ans) (car L) ans) (cdr L)
Unfortunately, no but why?
54
53 54
9
Using &rest
(defun max (ans &rest L) (Cond ((null (cdr L)) ans)
(t (max (if (> (car L) ans) (car L) ans) (cdr L)
Ø (max 1 4 3 67 9 4)
ans = 1 L = (4 3 67 9 4)
Oops, double lists!
(max 4 (3 67 9 4)
ans = 4 L = ((3 67 9 4))
55
Using &rest
(defun max (ans &rest L) (max-aux ans L))
(defun max-aux (ans L) (Cond ((null (cdr L)) ans)
(t (max-aux (if (> (cadr L) ans) (cadr L) ans) (cddr L)
(defun max (L &optional (ans (car L))) (Cond ((null (cdr L)) ans)
(t (max (cdr L)
(if (> (cadr L) ans) (cadr L) ans)))))
Note: So, &rest cannot be used recursively whereas &optional is ok.
56
55 56
57 58
The idea:
165204678320022
Put all numbers < 16 16 on this side
Quicksort
Put all numbers >= 16 on this side
Quicksort
Combine them into a list
57
The idea:
(165204678320022) (5 4 6 3 2 2) 16 (20 78 200)
(432256) 16 (2078200) (2 2 3 4 5 6 16 20 78 200)
58
Quicksort
(append
(Q-sort (less-than-N (car L) (cdr L)))
(list (car L))
(Q-sort (greater-equal-N (car L) (cdr L))))))
59
(defun Q-sort (L) (unless (null L)
Quicksort
(defun less-than-N (N L) (cond ((null L) nil)
((< (car L) N)
(cons (car L) (less-than-N N (cdr L))))
(t (less-than-N N (cdr L)))))
(defun greater-equal-N (N L) (cond ((null L) nil)
((>= (car L) N)
(cons (car L) (greater-equal-N N (cdr L))))
(t (greater-equal-N N (cdr L)))))
60
59 60
10