Functional programming -- 2008-2009 -- info.uvt.ro/Laboratory 2
References
editFrom 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
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
andcdr
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
froms1
tos5
;2
froms1
tos5
;3
froms1
,s4
ands5
;4
froms1
tos5
;
; 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 to0
;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 thenull
andlistp
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
andnull
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
, orheight
; - 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;