Saturday, 22 May 2010

Lisp Tutorial | MAPCAR and LAMBDA in Lisp

Applicative Programming in Lisp
Usually, the input to a Lisp function is some sort of data.

Functions are data too, so applicative programming takes this idea and uses Lisp functions in the same way other data: as inputs to other functions and functions returned as values. Today's Programming Lisp Tutorial introduces Applicative Programming in Lisp, MAPCAR and LAMBDA.

And of course we have the answer to the Lisp Programming Challenge from our last post.

Lisp Programming Challenge Answer:

Here's the answer to our last Lisp Programming Challenge: write a recursive function that extracts the numbers from a list:

(defun extract-numbers (the-list)
    (cond ((null the-list) nil)      
          ((numberp (first the-list))      
             (cons (first the-list) 
                   (extract-numbers (rest the-list))))
          (t (extract-numbers (rest the-list))))) 

(extract-numbers '(1 Partridge 2 Turtle Doves 3 French Hens 4 Calling Birds 5 Gold Rings))
(1 2 3 4 5) 

This function first checks that we have not reached the end of the list, then uses the NUMBERP predicate to check if the FIRST item in the list is a number. If it is we CONS this number and recursively call the extract-numbers function with the REST of the-list. 
If the list item is not a number we ignore it and call extract-numbers with the REST of the list. 

MAPCAR in Lisp

There are certain functions that we usually apply to numbers and cannot apply to lists for example:
(* 3 3)

Whereas the following will create an error:
(* 3 '(1 2 3 4))

We can write our own Lisp functions to perform operations on numbers:

(defun square (x) (* x x))
(square 10)

If we wanted to square every number in a list we could write a recursive function to do this:

(defun square-list (the-list)
     (if (null the-list) nil
           (cons (square (first the-list))
              (square-list (rest the-list)))))

(square-list '(1 2 3 4 5))
(1 4 9 16 25)

An alternative method would be to use Lisp's MAPCAR function. MAPCAR applies a function to each element of a list.

(mapcar #'square '(1 2 3 4 5))
(1 4 9 16 25)

We can apply predicates to lists in a similar way:
(mapcar #'oddp '(1 2 3 4 5))

Lisp and Lambda
MAPCAR accepts the function and a list as its input. We often have to input two numbers to a function:
(< 3 6)

But if we wanted to test if every number in a list was smaller than a given number, MAPCAR would generate an error as it's expecting a list as its only input:
(mapcar #'< 3  '(1 2 3 4 5))
Error: Cannot take CAR of 3.

The answer to this problem is to write a lambda expression. Lambda expressions are known as anonymous functions: they look like defining a Lisp function with DEFUN form without giving the function a name. Here we use the < predicate to see if each number in the list is smaller than 3:

(mapcar #'(lambda (n) (< n 3 ))  '(1 2 3 4 5))

Similarly we could multiply each of the numbers in a list by a given number:
(mapcar #'(lambda (n) (* n 5 ))  '(1 2 3 4 5))
(5 10 15 20 25)

We can use MAPCAR and LAMBDA inside other Lisp functions we define, for example if we wanted to add a number (n) to each element of a list:
(defun add-to-list (n the-list)
       (mapcar #'(lambda (x) (* x n)) the-list))

(add-to-list 3 '(1 2 3 4 5))
(3 6 9 12 15)

Today's Lisp Challenge
#1 Use DEFUN, MAPCAR and LAMBDA to define a function called half-list-numbers that divides every number in a list by two
#2 Use DEFUN, MAPCAR and LAMBDA to define a function called greater-than-n that uses the > predicate and returns a list every number in a list by two