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

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