==== Functional programming in LISP ====

=== First-class objects ===


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<sup>4</sup> using double function:

<code lisp>
(defun double (x)
  (* 2 x))
</code>

<code lisp>
(double (double (double 2)))
16
</code>

We may do it in best way:
<code lisp>
(defun repeat-n-times (function n arg)
  (if (zerop n)
      arg
    (repeat-n-times function (1- n) (funcall function arg))))
</code>

<code lisp>
(repeat-n-times (function double) 3 2)
16
</code>

Trace the execution:
<code lisp>
(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
</code>
Instead of typing (function double) we may use **#'**, for example:
<code lisp>
(repeat-n-times #'double 3 2)
</code>

=== Lambda expressions ===
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 [[http://en.wikipedia.org/wiki/Lambda_calculus|Lambda calculus:Wikipedia:en]]

<code lisp>
(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
</code>
Other example of using lambda expression:
<code lisp>
(repeat-n-times #'(lambda (x) (cons '(some text) x)) 4 nil)
((SOME TEXT) (SOME TEXT) (SOME TEXT) (SOME TEXT))
</code>

=== Iterating through a list ===
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:
<code lisp>
(defun do-on-list (f l)
  (if (null l)
      nil
    (cons (funcall f (first l)) (do-on-list f (rest l)))))
</code>
Example using:
<code lisp>
(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)
</code>

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**:
<code lisp>
(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)
</code>

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

<code lisp>
(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)
</code>
== Exercises ==
  - Write a function returning first sublist(leftmost) from a list of lists with length at least 3

<del>
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))
</del>