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.

Yet More Recursion in Lisp

Our last Lisp tutorial looked at using recursion to access data from nested lists. Today's Lisp tutorial looks at more Lisp recursion techniques. Firstly let's look at the Lisp Programming Challenge from our last Lisp recursion post:

(defun get-orbit (planet-list)
  (if (null planet-list) nil
    (cons (second (first planet-list))
          (get-orbit (rest planet-list)))))

(defun get-diameter (planet-list)
  (if (null planet-list) nil
    (cons (third (first planet-list))
          (get-diameter (rest planet-list)))))

(defun get-mass (planet-list)
  (if (null planet-list) nil
    (cons (fourth (first planet-list))
          (get-mass (rest planet-list)))))

More Recursion in Lisp
There are certain functions that we usually apply to numbers and cannot apply to lists for example:
(/ 8 2)
4

Whereas the following will create an error:
(/9 '(2 3 4))

If, as in the above example, we wanted to divide a list of numbers by another number we could write a recursive function to do this:

(defun divide-list-by-x (the-list x) 
    (if (null the-list) nil      
      (cons (/ (first the-list) x)     
      (divide-list-by-x (rest the-list) x))))

(divide-list-by-x '(2 3 4) 2)
(1 3/2 2)

Similarly we could write a recursive Lisp function to perform the modulus function on a list of numbers:

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

 When writing recursive Lisp functions we need to be able to define the following 3 things:

    * When to stop recursing
    * How do we take the next step
    * How to call the recursive function

The two recursive Lisp examples above use a single test to identify when to stop recursing, however we can also use two (or more) tests to identify when the recursive function should stop. In this example, we check to see if a given number is less than every number in a list by writing a recursive function. The function stops recursing if it reaches the end of the list, or if the function encounters a number that is equal to or greater than our test number:

(defun less-than-list (x the-list) 
   (cond ((null the-list) t)       
             ((>= x (first the-list)) nil)       
             (t (less-than-list x (rest the-list)))))

Today's Programming Lisp Challenge
Lisp has many different data types. Write a function to extract the numbers from this list:

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

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

should return:

(1 2 3 4 5)

Subscribe to the RSS feed and check back soon for the answer and more Programming Lisp tutorials.

Lisp Tutorial | More Recursion in Lisp

Our last Lisp Tutorial introduced the idea of recursion in Lisp. Today we're looking at more recursive Lisp functions but first let's look at the answer to yesterday's Lisp challenge. 

Lisp Tutorial Answer
Write a function called INCREASING-P this function returns T if all the numbers in the list are in ascending order and NIL if they are not.

As a reminder, when writing recursive Lisp functions we need to be able to define the following 3 things:

• When to stop recursing
• How do we take the next step
• How to call the recursive function
  

In the example of our INCREASING-P function we:

• Stop recursing when we get to the last two elements of the list
• Compare the first 2 elements of the list to see if the second is greater
• Call the recursive function with the REST of the list

(defun increasing-p (the-list)
  (cond ((null (rest the-list)) t)
        ((< (first the-list) (second the-list))
         (increasing-p (rest the-list)))
        (t nil)))

Defining Variables
Before we look further at recursion we're going to define a GLOBAL VARIABLE. Global variables can be evaluated by all functions, this contrasts with LET and LET* which defined variables that were only valid inside that function.

To define a global variable we can use DEFVAR function for example:
(defvar *simpsons* '(homer marge lisa bart maggie))

Note, it's not necessary to though it is common practice and recommended to identify global variables with * around them like *this*

Now when we evaluate this variable we can see its contents:
*simpsons*
(HOMER MARGE LISA BART MAGGIE)

More Recursion in Lisp

Let's define a global variable called *planets*, In this variable we'll store a nested list of attributes of the planet

• planet-name 
• orbit(AU) 
• diameter(km) 
• mass(kg)

;planet-name orbit(AU) diameter(km) mass(kg)
(defvar *planets* '((mercury 0.38 4880 3.30e23)
                      (venus .72 12103.6 4.869e24)
                      (earth 1 12756.3 5.972e24)
                      (mars 1.52 6794 6.4219e23kg)
                      (jupiter 5.2 142984 1.900e27)
                      (saturn 9.54 120536 5.68e26)
                      (uranus 19.218 51118 8.63e25)
                      (neptune 30.06 49532 1.0247e26)
                      (pluto 39.5 2274 1.27e22)))

Copy, paste and evaluate the above in your Lisp environment.

If we want to create a list of the planet names we need to take the first element of each list. As our *planets* variable is a nested list, the FIRST of *planets* evaluates to this:

(first *planets*)
(MERCURY 0.38 4880 3.3E23)

To get the planets name we need to take the FIRST of this list, so the FIRST of the FIRST of *planets*:
(first (first *planets*))
MERCURY

To create a full list of our planets names we can use recursion, firstly we need to answer our three important questions:

• When to stop recursing?
• When we reach the end of the list
• How do we take the next step
• CONS the FIRST of the FIRST of *planets* 
• How to call the recursive function
• With the REST of *planets*

(defun get-names (planet-list)
  (if (null planet-list) nil
    (cons (first (first planet-list))
          (get-names (rest planet-list)))))

(get-names *planets*)
(MERCURY VENUS EARTH MARS JUPITER SATURN URANUS NEPTUNE PLUTO)

Today's Programming Lisp Challenge
Write GET-ORBIT, GET-DIAMETER, GET-MASS functions that creates a list of orbits, diameter and masses.

Subscribe to the RSS feed and check back soon for the answer and more Programming Lisp tutorials.

Lisp Recursion Tutorial | Recursion in Lisp

Today's Programming Lisp tutorial looks at recursion. Recursion is a very powerful programming tool in Lisp, but before we being let's have a look at the answer to the last programming lisp challenge.

Write a function called BETWEEN that takes 3 input arguments N, MIN and MAX. This function tests to see if N is between MIN and MAX.

(defun between (n min max)
  (if (and (>= n min)
           (<= n max)) t nil))

And with some example input:

(between 6 3 9)
T

(between 2 3 9)
NIL

Recursion in Lisp
Recursion is when a function calls itself. The best way to introduce it is to look at some examples. we've looked at predicates before: the ODDP predicate tests to see if a number is odd however this predicate only works with numbers and not lists. We can use a recursive function (a function that calls itself) to see if there are any odd numbers in the list.

(defun any-odd (the-list)
                  (cond ((null the-list) nil)
                        ((oddp (first the-list)) t)
                         (t (any-odd (rest the-list)))))


The above function illustrates some important features of programming recursive features, here's a line by line break down:

this line defines the function's name as any-odd and its input as the-list:

(defun any-odd (the-list)

This line uses COND to setup a conditional test, (null the-list) checks to see if we're reached the end of the list, if we have it returns nil, if not we go on to the next line of our conditional statement:

(cond ((null the-list) nil)

This line takes the first item of the-list and uses this as the input to ODDP, if ODDP is true we return T:

((oddp (first the-list)) t)

The final line is only evaluated if the previous lines evaluated to nil. This is were the function becomes recursive - it calls itself. Our ANY-ODD function is called with the REST of the list. 

(t (any-odd (rest the-list)))))

Here's another example, this time we'll take a number and a list as input, and check to see if the number appears in the list:

(defun n-in-list (n the-list)
                      (cond ((null the-list) nil)
                        ((equalp n (first the-list)) t)
                         (t (n-in-list n (rest the-list)))))

When programming recursive functions in Lisp we have to know:

• When to stop recursing - in both of the above examples we return nil when we reach the end of the list (null the-list)
• How do we take the next step? This is usually the body of the recursive function. In our ANY-ODD function our step was to test the first item of the list to see if it was ODD, in our N-IN-LIST function, our step was to use the EQUALP predicate and see if N was equal to the FIRST element of the-list
• How to call the recursive function? In the ANY-ODD function above, the function calls itself with the REST of the list. With the N-IN-LIST function, the function calls itself with N and the REST of the-list.

Today's Programming Lisp Challenge
Write a function called INCREASING-P this function returns T if all the numbers in the list are in ascending order and NIL if they are not.

Subscribe to the RSS feed and check back soon for the answer and more Programming Lisp tutorials.