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

 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.

Recursion over trees (nested lists)

`sum-tree` (deep): adds all the numbers in a given tree (a list containing other lists), taking into consideration even nested lists, ignoring any other members (non-number or non-list).

```(defun sum-tree (tree)
(cond
((null tree)
0)
((numberp (first tree))
(+ (first tree) (sum-tree (rest tree))))
((listp (first tree))
(+ (sum-tree (first tree)) (sum-tree (rest tree))))
(t
(sum-tree (rest tree)))
))

(print (sum-tree '(1 a 2 b 3 c (5 (6) (())) d 4))) ; => 1 + 2 + 3 + 5 + 6 + 4
```

`sum-tree` (deep) (second solution).

```(defun sum-tree (tree)
(cond
((numberp tree)
tree)
((null tree)
0)
((listp tree)
(+ (sum-tree (first tree)) (sum-tree (rest tree))))
(t
0)
))
```

`filter-numbers` (deep): the same as `filter-numbers`, but it should work on trees.

```(defun filter-numbers (tree)
(cond
((null tree)
nil)
((numberp (first tree))
(cons (first tree) (filter-numbers (rest tree))))
(t
(filter-numbers (rest tree)))
))

(print (filter-numbers '(1 2 a b (3) 4 c 5 d))) ; => (1 2 (3) 4 5)
```

`filter-numbers` (deep): second solution, similar with sum-tree second solution.

• we can observe that it's behavior is not the correct one;
• there is no simple solution to fix this version;
```(defun filter-numbers (tree)
(cond
((numberp tree)
tree)
((null tree)
nil)
((listp tree)
(cons (filter-numbers (first tree)) (filter-numbers (rest tree))))
(t
nil)
))

(print (filter-numbers '(1 2 a b (3) 4 c 5 d))) ; => (1 2 nil nil (3) 4 nil 5 nil)
```

## Exercises

Recursion over trees

`my-count` (deep): compute the number of elements in a tree.

`my-reverse` (deep): similar with the one above but it should work on trees.

`delete-all` (deep): Write a recursive function which takes an atom and a nested list as arguments, and returns a new list which is a copy of the old with all instances of the atom removed, using `cond` (taken from Some Simple Programming Exercises).

```(delete-all 4 '((1 (((4)) 6 7 (4 3 4)))))
; => ((1 ((nil) 6 7 (3))))
```

`my-flatten`: it takes a tree, and should create a list by dissolving the inner lists (taken from L-99: Ninety-Nine Lisp Problems -- P07).

```(my-flatten '(1 2 (3 4 (5 ()) 6) () () 7))
; => (1 2 3 4 5 6 7)
```
More elaborate exercises

`compress`: If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed (taken from L-99: Ninety-Nine Lisp Problems -- P08).

```(compress '(a a a a b c c a a d e e e e))
; => (a b c a d e)
```

`pack`: Pack consecutive duplicates of list elements into sublists (taken from L-99: Ninety-Nine Lisp Problems -- P09).

```(pack '(a a a a b c c a a d e e e e))
; => ((a a a a) (b) (c c) (a a) (d) (e e e e))
```

`pack-rle`: Use the result of the previous problem to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists `(n e)` where `n` is the number of duplicates of the element `e` (taken from L-99: Ninety-Nine Lisp Problems -- P10).

```(pack-rle '(a a a a b c c a a d e e e e))
; => ((4 a) (1 b) (2 c) (2 a) (1 d) (4 e))
```

`pack-rle`: Modify the result of the previous problem in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as `(n e)` lists (taken from L-99: Ninety-Nine Lisp Problems -- P11).

`unpack-rle`: Given a run-length code list generated as specified in the previous problem, construct its uncompressed version. (taken from L-99: Ninety-Nine Lisp Problems -- P12).