Functional programming -- 2008-2009 -- info.uvt.ro/Laboratory 3
References
editFrom the book Practical Common Lisp:
- (m) Chapter 12., They Called It LISP for a Reason: List Processing (the sections "There Is No List", Functional Programming and Lists, and List-Manipulation Functions; optionally the entire chapter, except maybe the Mapping section);
Examples
edit- Observations
The examples were not tested an they might contain small syntax errors, or (thought not likely) semantic errors.
These examples are implemented in a non tail recursive manner, and thus these are not adequate in real world applications (please see further laboratories for a proper (more efficient) implementation).
- Arithmetic
n!
(factorial):
(defun n! (n) (if (zerop n) 1 (* n (n! (1- n))) )) (print (n! 3)) ; => 6
- Recursion over lists
sum-lst
(shallow): adds all the numbers in a given list.
(defun sum-lst (lst) (if (null lst) 0 (+ (first lst) (sum-lst (rest lst))) )) (print (sum-lst '(1 2 3 4))) ; => 1 + 2 + 3 + 4
sum-lst
(shallow): adds all the numbers in a given list, ignoring any other members (non-number).
(defun sum-lst (lst) (cond ((null lst) 0) ((numberp (first lst)) (+ (first lst) (sum-lst (rest lst)))) (t (sum-lst (rest lst))) )) (print (sum-lst '(1 a 2 b 3 c (5) d 4))) ; => 1 + 2 + 3 + 4
filter-numbers
(shallow): creates a new list that contains only the numbers of the original list.
(defun filter-numbers (lst) (cond ((null lst) nil) ((numberp (first lst)) (cons (first lst) (filter-numbers (rest lst)))) (t (filter-numbers (rest lst))) )) (print (filter-numbers '(1 2 a b (3) 4 c 5 d))) ; => (1 2 4 5)
list-random
: creates a list of a given length, with random (integer) numbers from 0 up to a given limit.
(defun list-random (length limit) (if (zerop length) nil (cons (random limit) (list-random (1- length) limit)))) (print (list-random 10 5))
list-selection-sort
: given a list (of numbers) it sorts it ascending (it needs some auxiliary functions given below) (for details, please consult selection sort).
(defun list-selection-sort (lst) (if (null lst) nil (let ((minimum (list-minimum lst))) (cons minimum (list-selection-sort (list-remove lst minimum)))))) (print (list-selection-sort (list-random 100 1000)))
list-remove
: deletes (only one) occurrence (if any) of a given element (maybe non-numeric) from a given list.
(defun list-remove (lst el) (cond ((null lst) nil) ((equal (first lst) el) (rest lst)) (t (cons (first lst) (list-remove (rest lst) el))))) (print (list-remove '() 1)) ; => () (print (list-remove '(1 2 3) 1)) ; => (2 3) (print (list-remove '(1 2 3) 2)) ; => (1 3) (print (list-remove '(1 2 3) 3)) ; => (1 2) (print (list-remove '(1 2 2 3) 2) ; => (1 2 3)
list-minimum
: returns the minimum value of a (numeric) list.
(defun list-minimum (lst) (cond ((null lst) nil) ((null (rest lst)) (first lst)) (t (let ((head (first lst)) (minimum-rest (list-minimum (rest lst)))) (if (< head minimum-rest) head minimum-rest))))) (print (list-minimum '())) ; => nil (print (list-minimum '(1 2 3))) ; => 1 (print (list-minimum '(2 1 3))) ; => 1 (print (list-minimum '(3 2 1))) ; => 1
list-insertion-sort
(for details, please consult insertion sort).
(defun list-insertion-sort (lst) (if (null lst) nil (list-insert (list-insertion-sort (rest lst)) (first lst)))) (print (list-insertion-sort (list-random 100 1000)))
list-insert
: given a (numeric) value it should insert it in an ordered (numeric) list, so that the resulting list is kept sorted.
(defun list-insert (lst el) (cond ((null lst) (cons el nil)) ((<= el (first lst)) (cons el lst)) (t (cons (first lst) (list-insert (rest lst) el))))) (print (list-insert '(1 2 3 5) 0)) ; => (0 1 2 3 5) (print (list-insert '(1 2 4 5) 3)) ; => (1 2 3 4 5) (print (list-insert '(1 2 4 5) 6)) ; => (1 2 4 5 6)
Exercises
edit- Arithmetic
compute-gcd
: computes the greatest common divisor of two numbers. (Hint: again a recursive function.)
is-prime
: checks if the single argument given is a prime number or not. (Hint: this should be implemented as a recursive function.)
prime-factors
: computes the list of a number prime factors.
- Recursion over lists
my-count
(shallow): compute the number of elements in a list (it's actually the list length) (taken from L-99: Ninety-Nine Lisp Problems -- P04).
my-append
: implement a function that takes two lists and returns the concatenation of those two lists.
(my-append '(1 2 3) '(a b c)) ; => (1 2 3 a b c)
my-reverse
(shallow): implement a function similar with reverse
(taken from L-99: Ninety-Nine Lisp Problems -- P05).
element-at
(shallow): Find the K'th element of a list (taken from L-99: Ninety-Nine Lisp Problems -- P03).
replicate
(shallow): Replicate the elements of a list a given number of times (taken from L-99: Ninety-Nine Lisp Problems -- P15).
(replicate '(a b c) 3) ; => (a a a b b b c c c)
drop-every-nth
(shallow): Drop every n'th element from a list (taken from L-99: Ninety-Nine Lisp Problems -- P16).
(drop-every-nth '(a b c d e f g h i k) 3) ; => (a b d e g h k)
The current page is a simplified view of the page Laboratory 1 and Laboratory 2 from the previous years, which in turn is based on Laboratory 1 and Laboratory 2 by Cornel Izbasa;