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:

• (m) Chapter 12., They Called It LISP for a Reason: List Processing (the sections "There Is No List", Functional Programming and Lists, and List-Manipulation Functions; optionally the entire chapter, except maybe the Mapping section);

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
                    ((head (first lst))
                     (minimum-rest (list-minimum (rest lst))))
                (if (< head minimum-rest)
                    head
                    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;