# Functional programming -- 2008-2009 -- info.uvt.ro/Laboratory 3

## References

[edit]From 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;