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

## References[edit]

From the book Practical Common Lisp:

**(m)**Chapter 13., Beyond Lists: Other Uses for Cons Cells (the entire chapter);

## Examples[edit]

**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[edit]

**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).