Functional programming -- 2008-2009 -- info.uvt.ro/Laboratory 4
|
Functional programming (Spring 2010):
|
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).