# 程序代写 Simple LISP – cscodehelp代写

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