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

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 Sketchy Lisp: the Tail-Recursive Programs section.

From the book Successful Lisp: Tail recursion.

Or from wikipedia:Tail recursion Tail recursion.

Examples

Arithmetic

n! (factorial):

(defun n!* (n acc)
	(if (zerop n)
		acc
		(n!* (1- n) (* acc n))))

(defun n! (n)
	(n!* n 1))

(print (n! 0))
(print (n! 1))
(print (n! 2))
(print (n! 10))

fibonacci:

(defun fibonacci* (n a1 a2)
	(if (<= n 1)
		a1
		(fibonacci* (1- n) a2 (+ a1 a2))))

(defun fibonacci (n)
	(fibonacci* n 1 1))

(print (fibonacci 1))
(print (fibonacci 2))
(print (fibonacci 3))
(print (fibonacci 10))

Arithmetic over lists

list-sum:

(defun list-sum* (lst sum)
	(cond
		((null lst)
			sum)
		((numberp (first lst))
			(list-sum* (rest lst) (+ sum (first lst))))
		(t
			(list-sum* (rest lst) sum))))

(defun list-sum (lst)
	(list-sum* lst 0))

(print (list-sum nil))
(print (list-sum '(1)))
(print (list-sum '(1 a 2)))

list-min:

(defun list-min* (lst m)
	(cond
		((null lst)
			m)
		((not (numberp (first lst)))
			(list-min* (rest lst) m))
		((< (first lst) m)
			(list-min* (rest lst) (first lst)))
		(t
			(list-min* (rest lst) m))))

(defun list-min (lst)
	(list-min* (rest lst) (first lst)))

(print (list-min nil))
(print (list-min '(1)))
(print (list-min '(1 a)))
(print (list-min '(2 a 1 b 3)))

Recursion over lists

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 acc)
	(if (zerop length)
		acc
		(list-random* (1- length) limit
				(cons (random limit) acc))))

(defun list-random (length limit)
	(list-random* length limit nil))

(print (list-random 0 1000))
(print (list-random 10 1000))

list-reverse:

(defun list-reverse* (lst rev)
	(if (null lst)
		rev
		(list-reverse* (rest lst) (cons (first lst) rev))))

(defun list-reverse (lst)
	(list-reverse* lst nil))

(print (list-reverse nil))
(print (list-reverse '(1)))
(print (list-reverse '(1 a 2)))

list-clone:

(defun list-clone (lst)
	(list-reverse* (list-reverse* lst nil) nil))

(print (list-clone nil))
(print (list-clone '(1)))
(print (list-clone '(1 a 2)))

Recursion over ordered

ordered-insert:

(defun ordered-insert* (lst x acc)
	(cond
		((and (null lst) (null x))
			acc)
		((null lst)
			(ordered-insert* nil nil (cons x acc)))
		((null x)
			(ordered-insert* (rest lst) nil (cons (first lst) acc)))
		((< x (first lst))
			(ordered-insert* lst nil (cons x acc)))
		(t
			(ordered-insert* (rest lst) x (cons (first lst) acc)))))

(defun ordered-insert (lst x)
	(reverse (ordered-insert* lst x nil)))

(print (ordered-insert '() 5))
(print (ordered-insert '(1) 5))
(print (ordered-insert '(10) 5))
(print (ordered-insert '(1 5 10) 5))

Exercises

Redo all the exercises from the previous laboratories, but this time in a tail recursive manner:

• all exercises from the 3rd laboratory;
• the exercises from the 4th laboratory, from the More elaborate exercises section;