A data type is called first-class when you can pass instances of the data type as function arguments or return them as function values. You may not be familiar to the notion that functions could be treated as first-class objects. It means that functions can be passed as function arguments and returned as function values. It makes LISP easy to build very powerful abstractions.

Let's compute 2⁴ using double function:

(defun double (x)
  (* 2 x))

(double (double (double 2)))
16

We may do it in best way:

(defun repeat-n-times (function n arg)
  (if (zerop n)
      arg
    (repeat-n-times function (1- n) (funcall function arg))))

(repeat-n-times (function double) 3 2)
16

Trace the execution:

(trace repeat-n-times )
;; Tracing function REPEAT-N-TIMES.
(REPEAT-N-TIMES)
(repeat-n-times (function double) 7 2)
1. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '7 '2)
 2. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '6 '4)
  3. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '5 '8)
   4. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '4 '16)
    5. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '3 '32)
     6. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '2 '64)
      7. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '1 '128)
       8. Trace: (REPEAT-N-TIMES '#<FUNCTION DOUBLE (X) (DECLARE (SYSTEM::IN-DEFUN DOUBLE)) (BLOCK DOUBLE (* 2 X))> '0 '256)
       8. Trace: REPEAT-N-TIMES ==> 256
      7. Trace: REPEAT-N-TIMES ==> 256
     6. Trace: REPEAT-N-TIMES ==> 256
    5. Trace: REPEAT-N-TIMES ==> 256
   4. Trace: REPEAT-N-TIMES ==> 256
  3. Trace: REPEAT-N-TIMES ==> 256
 2. Trace: REPEAT-N-TIMES ==> 256
1. Trace: REPEAT-N-TIMES ==> 256
256

Instead of typing (function double) we may use #', for example:

(repeat-n-times #'double 3 2)

Lisp provides a mechanism to defining functions “in place”. It is useful because we don't need to define function as a global function before passing it into repeat-n-times. It is based on the Lambda calculus:Wikipedia:en

(repeat-n-times #'(lambda (x) (* x x)) 3 2)
1. Trace: (REPEAT-N-TIMES '#<FUNCTION :LAMBDA (X) (* X X)> '3 '2)
 2. Trace: (REPEAT-N-TIMES '#<FUNCTION :LAMBDA (X) (* X X)> '2 '4)
  3. Trace: (REPEAT-N-TIMES '#<FUNCTION :LAMBDA (X) (* X X)> '1 '16)
   4. Trace: (REPEAT-N-TIMES '#<FUNCTION :LAMBDA (X) (* X X)> '0 '256)
   4. Trace: REPEAT-N-TIMES ==> 256
  3. Trace: REPEAT-N-TIMES ==> 256
 2. Trace: REPEAT-N-TIMES ==> 256
1. Trace: REPEAT-N-TIMES ==> 256
256

Other example of using lambda expression:

(repeat-n-times #'(lambda (x) (cons '(some text) x)) 4 nil)
((SOME TEXT) (SOME TEXT) (SOME TEXT) (SOME TEXT))

Previous examples shows that it is possible to iterate through a list using linear recursion. If we look closer at the definitions of recursive functions we see that we may write a function invoking other function with arguments from a list.

Function applying function f to every element of list l and returning a list containing the result:

(defun do-on-list (f l)
  (if (null l)
      nil
    (cons (funcall f (first l)) (do-on-list f (rest l)))))

Example using:

(do-on-list #'reverse '((1 2 4) (a b c ) (1 a 2 b 3 c)))
((4 2 1) (C B A) (C 3 B 2 A 1))
(do-on-list #'(lambda (x) (* x x)) '(1 2 3 4))
(1 4 9 16)

This function is defined in Common Lisp and it is called mapcar. Mapcar is an example of generic iterators, which capture the generic logic of iterating through a list. We iterate through a list for 3 main reasons:

• transforming a list by systematically applying a function to the element of the list
• searching for a list member that satisfy a given condition
• screening out all members that does not satisfy a given condition

Mapcar implements generic algoritm for performing transformation iteration.

Common Lisp defines a built-in function for searching through a list - find-if:

(find-if #'evenp '(1 3 5 8 11 12))
8
(find-if #'(lambda (X) (not (null X))) '(nil nil (1 2 3) (4 5)))
(1 2 3)

For removing elements from lists we can use built-in function remove-if

(remove-if #'(lambda (X) (< (list-length X) 3)) '((1 2 3) (1 2) nil (1 2 3 4)))
((1 2 3) (1 2 3 4))
(remove-if #'(lambda (X) (zerop (rem x 2))) '(3 6 8 9 10 13 15 18))
(3 9 13 15)

1. Write a function returning first sublist(leftmost) from a list of lists with length at least 3

Sample solution: (defun find-long-list (L) “Given a list L of lists, return the leftmost member with length at least 3.” (find-if #'(lambda (X) (>= (list-length X) 3)) L))