Power-Programmierung/CD1.mdf/lisp/interpre/apteryx/tutor3.lsp

Lisp/Scheme | 1993-12-09 | 8KB | 236 lines

; Copyright 1993 Apteryx Lisp Ltd

; Some list processing (use F4 to evaluate example expressions)

; A list is an ordered sequence of elements. In Lisp it is represented
; by writing an open bracket "(", the elements of the list in order
; separated by white space, and then a closing bracket ")".
; Examples -

    (1 2 3 4) ; A list of 4 numbers

    (jim fred tom harry trevor) ; A list of 5 names

    () ; An empty list (containing 0 members)

    ((a b c d e) (f g h) ()) ; A list with 3 members, all of which are
                             ; themselves lists.

; All Lisp programs are lists, but we can also treat lists as data to
; be processed. Arguments to a Lisp function are normally evaluated
; themselves before being passed to the function. To pass a list directly
; in without it being evaluated as an expression, we need some way to
; prevent this evaluation. We do this by putting a quote character '
; before the list. For example, length is a function that returns the
; number of members of a list -

(length '(jim tom fred))

; If we leave the quote out, we get an error when the Lisp attempts to
; evaluate the expression (jim tom fred)

(length (jim tom fred))

; The quote ' is actually an abbreviation for the special form "quote".
; For example '(jim tom fred) = (quote (jim tom fred))
; Note that the quote character abbreviates both the symbol quote and
; the brackets that enclose quote and its argument. quote is a special
; form which takes one argument which is not evaluated and returns that
; unevaluated argument as it's result. The sole purpose of quote is to
; prevent the evaluation of data that occurs by default (in particular
; for lists and non-keyword symbols - other Lisp objects are
; self-evaluating, and quote is unnecessary when they are passed as
; arguments).

(length (quote (jim tom fred)))

; cons is a function that adds an element on to the beginning of a list.

(cons 4 '(5 6))

; If we pass a non-list as the second argument we get a dotted pair as
; a result.

(cons 4 5)

; A dotted pair is sometimes called a "cons" or "cons cell". It is stored
; in the computer as a simple pair of objects (or to be exact as pointers
; to a pair of objects). A list is in fact constructed using dotted pairs,
; for example (4 . (5 . (6 . ()))) means the same as (4 5 6). So the
; effect of the function cons is to construct a new "cons" made up of
; pointers to the two arguments to cons. A list is a pair of objects, the
; first of which is the first element of the list and the second is
; the list consisting of all elements in the list other than the first
; element. These two elements are sometimes known as "first" and "rest"
; and sometimes as "head" and "tail". One exception is the empty list (),
; which not having a first element, has to be a special object in itself.
; In Lisp, the empty list is identified with the symbol nil.

; In fact functions called first and rest exist which return the first
; and second elements respectively of a "cons".

(first '(3 4))

(rest '(a b c d e))

(rest '(3 . 4))

; Alternative names for first and rest are car and cdr.

(car '(3 4))

(cdr '(a b c d e))

; These are the "traditional" names for these functions (and somewhat
; obscure). If the name "cons" seems a bit obscure, it is an abbreviation
; for "constructor", referring to the construction of lists.

; list is a function that makes any number of elements into a list

(list (+ 2 3) (+ 4 5))

; append "glues" any number of lists together

(append '(a b c) '(d e) '(f g h i) '(j) '(k l m))

; contrast the following -

(cons '(a b) '(c d))
(list '(a b) '(c d))
(append '(a b) '(c d))

; member determines if an object belongs to a list.

(setq my-family '(dad mum jim tom deborah))

(member 'dad my-family)

(member 'harry my-family)

; Note that when member returns a positive result it returns that
; portion of the list argument starting from the member found.
; Since this is always non-empty, it effectively means true.

(if (member 'harry my-family)
  (print "harry is in my family")
  (print "harry is not in my family") )

(if (member 'dad my-family)
  (print "dad is in my family")
  (print "dad is not in my family") )

; find the nth element in a list (note that element 0 is the first element)

(nth 0 '(a b c d e f))
(nth 1 '(a b c d e f))
(nth 2 '(a b c d e f))

; find the last element in a list

(last '(1 2 3 4 5 6))

; return a copy of a list with specified element removed

(remove 'jim '(fred jim tom jim harry jim harry))

; return a copy of a list with elements in reverse order

(reverse '(this is my life))

; note that it reverses just the elements of the list, and doesn't
; reverse any elements which may be lists

(reverse '((this is) (my life)))

; We could write a function that does a "deep" reverse

(defun deep-reverse (x)
  (if (consp x)
    (reverse (mapcar #'deep-reverse x))
    x) )

(deep-reverse '((this is) (my life) (this is (your life))))

; consp is a function that returns t (= true) for a non-empty list or any
; other "dotted" pair, and false for anything else. The function definition
; more or less says - for a non-empty list, first apply deep-reverse
; to each element, and then return the list of results reversed, for
; any other object return it unchanged.

(deep-reverse '((a . b) (c d)))

; The above function won't produce a very satisfactory result for
; objects that contain dotted pairs that aren't true lists, because
; neither mapcar nor reverse like such "improper" lists. To fix this
; we can use true-listp instead of consp, which only returns t for a
; for a "true" list (including the empty list).

(defun deep-reverse (x)
  (if (true-listp x)
    (reverse (mapcar #'deep-reverse x))
    x) )

(deep-reverse '((a . b) (c d)))

; some pre-defined functions do operate "deeply", i.e. they go into
; nested lists.

; For example subst and sublis do substitutions.

(subst 'tom 'jim '(jim fred harry (jim (jim tom) (fred jim (jim)))))

(sublis '( (tom . tomasina) (fred . frederica) (jim . jane) (harry . harrieta))
  '(jim fred harry (jim (jim tom) (fred jim (jim)))) )

; note that for sublis the first argument is a list of dotted pairs. Such
; a list is called an association list or assoc list or alist. Each pair
; is an association of the first element with the second.

(setq male-to-female-alist
  '((tom . tomasina) (fred . frederica) (jim . jane) (harry . harrieta)) )

; assoc the first pair (if any) of an alist whose first element is eql
; to the first argument.

(cdr (assoc 'fred male-to-female-alist))

; You can think of an alist as a simple sort of lookup table.

(setq phone-list
  '((tom . 4906589) (jim . 2139087)) )

(assoc 'tom phone-list)

(assoc 'fred phone-list)    ; This returns nil because no entry is found

; some of the above list functions have "destructive" equivalents, i.e.
; they are functions that build as much as possible of their result from
; the input arguments, even if this means altering the input arguments

(delete 'jim '(tom jim harry))
(remove 'jim '(tom jim harry))

; the above two seem to give the same result, but lets see what each
; does to its input argument

(let ( (fellas '(tom jim harry)) )
  (remove 'jim fellas)
  fellas)  ; remove leaves its input argument untouched

(let ( (fellas '(tom jim harry)) )
  (delete 'jim fellas)
  fellas)  ; delete cuts the element to be deleted out of the input list

(let ( (fellas '(jim tom jim harry)) )
  (delete 'jim fellas)
  fellas)  ; note here that the first jim isn't deleted from fellas,
           ; this is because it can be deleted simply by returning the
           ; cdr of the trimmed list


; nconc is the destructive equivalent of append - it "destroys" all
; input arguments except the last one.

(nconc '(tom harry) '(dick))