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

 Functional programming (Spring 2010): front; laboratory: agenda, references, projects, tools; notes (normal paced): 1, 2, 3, 4, 5, 6, 7, 8 (Spring 2009); notes (fast paced): 1, 2, 3, 4 (Spring 2010) (discontinued); applications: robots; mailing list: send mail, view archive, subscribe; author: Ciprian Dorin Craciun, ccraciun@info.uvt.ro;

## References

From the book Practical Common Lisp:

## Examples

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
(minimum-rest (list-minimum (rest lst))))
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

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;