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


Functional programming (Spring 2010):

References

edit

From the book Practical Common Lisp:

List anatomy

edit
  • 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

edit
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

edit
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

edit
if

Reference:

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:

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:

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:

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:

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

edit
defun

Reference:

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

edit
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;