Functional programming -- 2008-2009 -- info.uvt.ro/Laboratory 2

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 4., Syntax and Semantics (the entire chapter, except maybe the Macros section);
• (m) Chapter 5., Functions (all sections from the beginning up to, but excluding, the Function Return Values section, but the sections Optional Parameters, Rest Parameters, Keyword Parameters and Mixing Different Parameter Types are optional);
• Variable Basics, Constants, Assignment (from Chapter 6., Variables);
• (m) WHEN and UNLESS, COND, AND, OR, and NOT (from Chapter 7., Macros: Standard Control Constructs);
• (m) Chapter 10., Numbers, Characters, and Strings (the entire chapter);
• (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);

List anatomy

• cells (pairs);
• in-memory representation;
• creation:
  • prepending;
  • appending;
• cells sharing:
  • advantages of functional programming;
  • implications of side effects in non-functional programming;
  • safety copies in non-functional programming;

List operations

Creation

• list:

(list 'a 'b 'c 'd) ; => (a b c d)
(list '(1 2) '(3 4)) ; => ((1 2) (3 4))
(list (+ 1 1) 3) ; => (2 3)

• cons:

(cons 1 nil) ; => (1)
(cons 1 (cons 2 nil)) ; => (1 2)
(cons nil nil) ; => (())

Inspection

• car:

(car '(1 2)) ; => 1
(car '((a b c) 1 2)) ; => (a b c)
(car ()) ; => nil

• cdr:

(cdr '(1 2 3)) ; => (2 3)
(cdr '((a b c) 1 2)) ; => (1 2)
(cdr ()) ; => nil

• car and cdr combinations:

(car (cdr '(1 2 3))) ; => 2
(cadr '(1 2 3)) ; => 2
(cddr '(1 2 3)) ; => (3)
(caddr '(1 2 3)) ; => 3

• first, second, ..., tenth, last:

(sixth '(1 2 3 4 5 6 7)) ; => 6
(last '(1 2 3 4 5)) ; => (5)
(last ()) ; => ()

• nth, nthcdr:

(nth 3 '(1 2 3 4 5 6)) ; => 4
(nthcdr 3 '(1 2 3 4 5 6)) ; => (4 5 6)

• length:

(length ()) ; => 0
(length nil) ; => 0
(length '(1 2 3)) ; => 3
(length '(1 (2 3 4 5) 6)) ; => 3

• member:

(member 5 '(1 2 3)) ; => nil
(member 2 '(1 2 3)) ; => (2 3)
(member 2 '(1 (2 3) 4)) ; => nil

Transformation

• append:

(append '(1 2) '(3 4)) ; => (1 2 3 4)
(append 1 2 3) ; => error!

• reverse:

(reverse '(1 2 3 4)) ; => (4 3 2 1)
(reverse '(1 (2 3) 4)) ; => (4 (2 3) 1)

• subst:

(subst 'a 1 '(1 2 1 3)) ; => (a 2 a 3)
(subst 'a 1 '(1 (2 1) 3)) ; => (a (2 a) 3)

Exercises

cons

By using only cons, nil and atoms (numbers, symbols, etc.), write (and test) the expression that creates the following lists:

()
(1)
(1 2)
(1 2 3)
(1 (2) 3)
(1 ((2)) 3)
(1 () 3)
((1 2) 3)
((1 2) (3))
((1 (2 (3 ()))))

; example:
(cons 1 nil) ; => (1)

car, cdr

Considering that the variable s1, s2, etc. contain the following lists:

(setq s1 '(1 2 3 4))
(setq s2 '(1 (2) 3 4))
(setq s3 '((1 2 3 ((4)))))
(setq s4 '(((1 2) (3 4))))
(setq s5 '(1 (2 (3 (4)))))

By using only car or cdr write the expression that returns the following:

• 1 from s1 to s5;
• 2 from s1 to s5;
• 3 from s1, s4 and s5;
• 4 from s1 to s5;

; example
(car s1) ; => 1

cadr, ...

Now by using also cadr, cdar, and the other combinations, solve the same problem as above.

; example
(cadr s1) ; => 2

Control structures

if

Reference:

• Section 7.6., Conditionals;
• Special operator IF;

Syntax:

(if <condition> <then-statement> [else-statement])

Syntax example:

(if t 1 2) ; => 1
(if nil 1 2) ; => 2
(if t 1) ; => 1
(if nil 1) ; => nil

Basic example:

(setq a 5)
(setq b 7)

; computing the maximum value between a and b
(if (> a b)
    a
    b)

; now assigning to a variable the maximum between a and b
(setq m (if (> a b) a b))

when

Reference:

• Section 7.6., Conditionals;
• Macro WHEN, UNLESS;

Syntax:

(when <condition> <statement-1> ... <statement-n>)

Syntax example:

(when t
    (print 1)
    (print 2)) ; => 2 and 1, 2 is printed on the console
(when t 1 2 3) ; => 3
(when nil 1 2 3) ; => nil

Basic example:

(setq n (read))

; write an error if n is negative
(when (minusp n)
    (print "n is negative"))

unless

Reference:

• Section 7.6., Conditionals;
• Macro WHEN, UNLESS;

Syntax:

(unless <condition> <statement-1> ... <statement-n>)

Syntax example:

(unless nil
    (print 1)
    (print 2)) ; => 2 and 1, 2 is printed on the console
(unless t 1 2 3) ; => nil
(unless nil 1 2 3) ; => 3

cond

Reference:

• Section 7.6., Conditionals;
• Macro COND;

Syntax:

(cond
    (<condition-1> <statement-1-1> ... <statement-1-n1>)
    (<condition-2> <statement-2-1> ... <statement-2-n2>)
    ...
    (<condition-m> <statement-m-1> ... <statement-m-nm>)
    (t <statement-t-1> ... <statement-t-nt>))

Basic example:

(setq n 5)

; testing the nature of the variable n
(print
    (cond
        ((not (integerp n)) "non-integer")
        ((evenp n) "even")
        ((oddp n) "odd")
        (t "error"))))

let

Reference:

• Section 7.5., Establishing New Variable Bindings;
• Special Operator LET, LET*;

Syntax:

(let
       ((<variable-1> <initial-value-1>)
        ...
        (<variable-n> <initial-value-n>))
   <statement-1>
   ...
   <statement-n>)

Syntax example:

(let
        ((l1 '(1 2 3))
         (l2 '(a b c)))
    (append l1 l2))

Basic example:

(set a 5)
(set b 7)

; returning a list with:
; * the minimum and maximum between a and b
; * the ratio between the minimum and maximum
(let
        ((m (max a b))
         (n (min a b)))
    (list m n (/ n m)))

Defining functions

defun

Reference:

• Section 5.3.1., Defining Named Functions;
• Macro DEFUN;

Syntax:

(defun <function-name> (<argument-1> ...)
    <statement-1>
    ...)

Syntax example:

(defun my-sum (a b)
    (+ a b))

(my-sum 1 2) ; => 3

(defun my-evenp (n)
    (zerop (mod n 2)))

(my-evenp 2) ; => t

(defun my-max2 (a b)
    (if (> a b)
        a
        b))
(my-max2 3 4) ; => 4

(defun my-max3 (a b c)
    (cond
        ((and (> a b) (> a c))
            a)
        ((> b c)
            b)
        (t
            c)))

(my-max3 1 4 3) ; => 4

(defun int-test (n)
    (cond
        ((not (integerp n)) "non-integer")
        ((evenp n) "even")
        ((oddp n) "odd")
        (t "error")))

(int-test 1) ; => "odd"
(int-test 2) ; => "even"
(int-test "a") ; => "non-integer"

Exercises

Simple decisions

less-than-or-equal-to: Implement a function which takes two numeric arguments and determines if the first one is less or equal to the second (taken from Some Simple Programming Exercises):

• hint: use only the forms and, or, not (not necessary all of them) and the comparison functions;

(defun less-than-or-equal-to (x y)
    (or ...))
(less-than-or-equal-to 1 2) ; => t
(less-than-or-equal-to 1 1) ; => t
(less-than-or-equal-to 2 1) ; => nil

my-signum: Implement a function that takes as arguments one number and returns:

• 0 if the number is equal to 0;
• 1 if the number is positive;
• 2 if the number is negative;
• hint: use the form cond and comparison functions;

(defun my-signum (n)
    (cond
        ...
    ))
(my-signum 0) ; => 0
(my-signum 100) ; => 1
(my-signum -100.5) ; => -1

Type predicates

my-signum: Update the previous function so that now it accepts any kind of argument, but if given anything else than a number it returns nil:

• hint: use the predicate numberp;

(my-signum 5) ; => 1
(my-signum nil) ; => nil
(my-signum '(1 2 3)) ; => nil

is-a-list: Implement a function that takes only one argument, and returns (taken from Some Simple Programming Exercises):

• list if the argument is a list;
• empty-list if the argument is an empty list;
• something-else if the argument is not any of the above;
• hint: use the form cond and the null and listp predicates (and keep in mind that an empty list is also a list);

(is-a-list '()) ; => empty-list
(is-a-list '(1 2)) ; => list
(is-a-list 'nope)) ; => something-else

Lists

compare-length: Write a function that takes two lists as arguments and returns:

• 0 if the two lists are equal in length;
• 1 if the first list is longer than the second one;
• 2 if the first list is shorter than the second one;

(compare-length '() '()) ; => 0
(compare-length '(1) '(1 2)) ; => 2
(compare-length '(1 2) '()) ; => 1

compare-length: Update the previous function so that it also accepts any kind of arguments, and in addition to the previous rules:

• if neither argument is a list it returns nil;
• if both lists are empty then it returns nil;
• if only the first argument is a list it returns 1;
• if only the second argument is a list it returns 2;
• hint: use the listp and null predicates (and keep in mind that an empty list is also a list);

(compare-length 1 2) ; => nil
(compare-length 1 '(3)) ; => 2
(compare-length '() '()) ; => nil

only-third: Write a function, using only car and cdr, which returns the third element of a list (taken from Some Simple Programming Exercises):

(only-third '(1 2 3 4)) ; => 3

Data abstraction

lookup-details: Write a function which looks up information in a record. A record takes the following form of a list with three elements (name age height). Your function should take two arguments (taken from Some Simple Programming Exercises):

• the type of information to look for: name, age, or height;
• the record;

(lookup-details 'age '(john 31 163cm)) ; => 31
(lookup-details 'name '(mary 10 unknown)) ; => mary

make-lookup-table: Then write another function which, when given a record of the form given above, returns a lookup table as follows (you are not allowed to look inside the list, but instead you should use the previous defined function lookup-details) (taken from Some Simple Programming Exercises):

(make-lookup-table '(john 31 163cm))
; => ((name john) (age 31) (height 163cm))

Recursion

(**) compute-gcd: Write a function that computes the greatest common divisor of two numbers. (Hint: again a recursive function.)

(**) is-prime: Write a function that checks if the single argument given is a prime number or not. (Hint: this should be implemented as a recursive function.)

(***) prime-factors: Write a function that takes a number and returns a list of its prime factors.

---

The current page is a simplified view of the page Laboratory 1, Laboratory 2 and Laboratory 4 from the previous years, which in turn is based on Laboratory 1, Laboratory 2 and Laboratory 4 by Cornel Izbasa;