Ein großer Vorteil LISP-ähnlicher Sprachen ist die Existenz von Funktionen höherer Ordnung. Das sind Funktionen, die entweder wiederum Funktionen als Parameter akzeptieren, in denen Funktionen Rückgabewert sein können, oder aber für die beides zutrifft. Diese Möglichkeit ist in Beispielen wie den folgenden besonders nützlich.

Funktionen als Parameter

Um zu zeigen, wie nützlich Funktionen als Parameter sind, sollen die Funktionen double-all und add-two als Beispiel dienen. Die erste Funktion verdoppelt alle Elemente einer Liste während die zweite zu jedem Element zwei addiert (Listing 1).

Die Ähnlichkeit der beiden Funktionen ist so frappierend, dass sich die Frage aufdrängt, ob man hier nicht etwas verallgemeinern kann. Mankann zumindest in Scheme. Der Unterschied besteht nur in der jeweiligen Operation auf dem jeweils ersten Element der Restliste. Nach der Bearbeitung wird das Ergebnis in die Rückgabeliste aufgenommen. Mit einer Funktion als Parameter lassen sich die beiden Beispiele vereinfachen. Dazu behalten wir die Implementierung bei und parametrisieren die Unterschiede durch einen Parameter (hier op ).

(define (apply-to-all op a-list)
  (if (null? a-list) 
      '()
      (cons (op (first a-list))
   (apply-to-all op (cdr a-list)))))
Op  sieht  in double-all  so aus: 

 (* 2 x), was man
direkt in Scheme übersetzen kann: 

 (define (double x) (* 2 x))

Wenden wir double-all sowie apply-to-all zusammen mit double einmal an:

(define a-list '(1 2 3))
(double-all a-list) -> '(2 4 6)
(apply-to-all double a-list) -> '(2 4 6)

Der angedeutete Pfeil -> steht für "ergibt" oder "evaluiert zu". Die beiden Funktionen liefern das gleiche Ergebnis, jedoch ist die zweite Version universeller einsetzbar.

Was hier so bemerkenswert einfach geht, ist in manchen Sprachen gar nicht oder nur mit hohem Aufwand nachzubilden. Die sich aus Funktionen höherer Ordnung ergebenden Möglichkeiten, dürften selbst bei diesem Beispiel schon so offensichtlich sein, dass man sich fragt, warum nicht alle Sprachen solche Möglichkeiten bieten. Um nicht jeder noch so kleinen Funktion einen eigenen Namen geben zu müssen, kann man in Scheme auch anonyme Funktionen einsetzen. Somit kann apply-to-all folgendermaßen vereinfacht werden:

(apply-to-all (lambda (n) (* 2 n)) a-list)

Das Ergebnis wäre wieder \'(2 4 6). Dieses lambda ist in Scheme ein wichtiges Basiselement der Programmierung und die Grundlage weiterer Elemente, auch wenn diese Elemente auf den ersten Blick keine Gemeinsamkeiten mit dem unscheinbaren lambda besitzen.

Apply-to-all kann man durch die Scheme Standardfunktion ( map) ersetzen. Mit dieser sähe unsere Lösung so aus:

(map(lambda (n) (* 2 n)) a-list)

Selbstverständlich kann man double-all mit Hilfe von map reimplementieren.

(define (double-all al)
    (map (lambda (n) (* 2 n)) al))

Eine weitere nützliche Funktion ( filter) dient zum Aussortieren von Elementen, die bestimmten Bedingungen genügen. Man kann filter wie in Listing 2 implementieren:

Möchten Sie nun aus einer Liste alle positiven Elemente herausfiltern, können Sie folgende Scheme-Funktion nutzen:

(filter positive? a-list)

Map und filter sind beliebig kombinierbar. Mit

(filter positive? (map double a-list))

verdoppelt man beispielsweise alle Elemente und sortiert dann die Positiven aus. In diesem Fall wäre

(map double (filter positive? a-list))

äquivalent und aus Effizienzgründen vorzuziehen. Wer mag, kann sich mal Gedanken darüber machen, warum das so ist.

(define (double-all a-list)
  (if (null? a-list) 
          '()
          (cons (* 2 (first a-list)) 
                  (double-all (rest a-list)))))

(define (add-two a-list)
  (if (null? a-list)
          '()
          (cons (+ 2 (first a-list)) 
                  (add-two (rest a-list)))))

(define (filter pred? a-list)
  (cond

    ((null? a-list) '())
    ((pred? (first a-list)) (cons (first a-list)
                                  (filter pred? (rest a-list))))
    (else
     (filter pred? (rest a-list)))))

Funktionen als Rückgabewerte

In Scheme sind Funktionen und Daten gleichberechtigt. Funktionen sind an allen Stellen erlaubt, wo auch "normale" Variablen vorkommen können. Innerhalb anderer Methoden, als Parameter und auch als Rückgabewerte. Sie sind in Fachterminologie ausgedrückt Objekte erster Klasse (first-class objects). Hier ein Beispiel:

(define (make-adder n)   (lambda (m)     (+ n m))) (define add-5 (make-adder 5))

Bei add-5 handelt es sich um eine Funktion, die 5 zu ihrem Argument addiert, Steele stellt in [6], S. 145, Kapitel 2.3.2 ein interessantes Beispiel vor.