Functional programming: Scheme, lambda, map and recursion

Functional programming sees a program as a combination of mathematical functions. No variables, no assignment, no loops; a function always gives the same result with the same argument. The functional language of this course is Scheme (a small, clean dialect of LISP). Two question types come up on exams: finding the value of a Scheme expression (car, cdr, cons chains) and tracing what a short recursive function returns.

Golden rules:

1. Evaluate from the inside out. Rewrite the list at each step.
2. car = first element, cdr = the rest of the list, cdr always returns a list (for suitable input).
3. cons adds to the front of the second argument. If the second argument is not a list, it is a dotted pair.
4. Recursion pattern: the empty list is the base case, process with car, continue with cdr.
5. The quote (') stops evaluation.

Mathematical functions

A mathematical function maps each element of its domain to an element of its range. The order of evaluation is determined only by the arguments, not by side effects:

$\text{cube}(x) \equiv x \cdot x \cdot x \qquad \text{cube}(2) = 8$

Lambda notation writes an anonymous function: $\lambda(x)\, x \cdot x \cdot x$. Application: $(\lambda(x)\, x \cdot x \cdot x)(2) = 8$. Scheme’s lambda comes directly from here.

A functional form (higher-order function): a function that takes functions as parameters or returns a function. Three classics:

• Composition: $h \equiv f \circ g$, $h(x) = f(g(x))$.
• Apply-to-all: apply a function to every element of a list (map).
• Construction: apply a list of functions to one argument, list the results.

The difference from imperative languages: in an imperative program, variables are memory cells and the state changes. In a pure functional program there is no state; that is why referential transparency holds and concurrency becomes easier. The cost: efficiency on a von Neumann machine.

LISP data structure

In LISP (1958, John McCarthy) there are two kinds of data objects: atoms (a, 17, hello) and lists ((a b c), (a (b c) d)). Lists are held internally as a chain of cons cells: each cell has two fields, car (the element) and cdr (the next cell). The cdr of the last cell is the empty list ().

(a (b c) d)

[a|•]──►[•|•]──►[d|/]
          │
          ▼
        [b|•]──►[c|/]

The program is written in the same form too: (+ 2 3) is a list and evaluates to 5. That code and data have the same form is the most distinctive feature of LISP.

Scheme basics

The interpreter is a read-evaluate-print loop. Evaluation rule: when you see a list, take the first element as the function, evaluate the other elements, and apply the function. Numbers evaluate to themselves.

car, cdr, cons

(car (cdr '(a b c)))          ; b
(cdr '((a b) c d))            ; (c d)
(car '((a b) c d))            ; (a b)
(cdr '(x))                    ; ()
(cons '(a) '(b))              ; ((a) b)
(cons 'a 'b)                  ; (a . b)
(car (car (cdr '(1 (2 3) 4))))  ; 2

b
(c d)
(a b)
()
((a) b)
(a . b)
2

Trace of the last expression:

(cdr '(1 (2 3) 4))   →  ((2 3) 4)
(car ((2 3) 4))      →  (2 3)
(car (2 3))          →  2

PITFALL · the difference between cons and list. (cons '(a) '(b)) gives the two-element ((a) b); (list '(a) '(b)) gives ((a) (b)). cons takes the second argument as a list and adds to its front; list makes every argument a separate element. (car '()) is an error: the empty list has no first element.

Defining functions and control

(define pi 3.14159)                         ; binding a name
(define (square x) (* x x))                 ; a function
(define square2 (lambda (x) (* x x)))       ; the same, with lambda

(if (> x 0) x (- x))                        ; two-way selection
(cond ((< x 0) 'neg)
      ((= x 0) 'zero)
      (else 'pos))                          ; multiple-way selection

(let ((a 2) (b 3)) (+ a (* a b)))           ; 8, local names

Predicate functions return a boolean (#t, #f): null?, eq?, equal?, pair?, number?, zero?. eq? asks the equality of two symbols or the same object, equal? asks the structural equality of two lists: (equal? '(1 (2)) '(1 (2))) → #t.

Recursive list functions

No loops; everything is recursion. The pattern is always the same:

(define (f lst)
  (cond ((null? lst) <base value>)
        (else (<combine> (car lst) (f (cdr lst))))))

(define (sum lst)
  (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))
(sum '(3 5 7))                               ; 15

(define (member atm lis)
  (cond ((null? lis) #f)
        ((eq? atm (car lis)) #t)
        (else (member atm (cdr lis)))))
(member 'c '(a b c d))                       ; #t

(define (rev l)
  (if (null? l) '() (append (rev (cdr l)) (list (car l)))))
(rev '(1 2 3 4))                             ; (4 3 2 1)

15
#t
(4 3 2 1)

Trace of (sum '(3 5 7)):

(sum '(3 5 7)) = 3 + (sum '(5 7))
               = 3 + 5 + (sum '(7))
               = 3 + 5 + 7 + (sum '())
               = 3 + 5 + 7 + 0 = 15

In nested lists the car can also be a list; then you recurse in two directions:

(define (count-atoms l)
  (cond ((null? l) 0)
        ((pair? (car l)) (+ (count-atoms (car l)) (count-atoms (cdr l))))
        (else (+ 1 (count-atoms (cdr l))))))
(count-atoms '(a (b c) ((d)) e))             ; 5

Higher-order functions

(map (lambda (x) (* x x)) '(1 2 3))          ; (1 4 9)

(define (filter p lst)
  (cond ((null? lst) '())
        ((p (car lst)) (cons (car lst) (filter p (cdr lst))))
        (else (filter p (cdr lst)))))
(filter (lambda (x) (> x 2)) '(5 1 4 2 3))   ; (5 4 3)

(define (compose f g) (lambda (x) (f (g x))))
((compose car cdr) '(1 2 3))                 ; 2

(define (adder n) (lambda (x) (+ x n)))
(map (adder 3) '(1 2 3))                     ; (4 5 6)

(define (twice f) (lambda (x) (f (f x))))
((twice (lambda (x) (* x 3))) 2)             ; 18

(1 4 9)
(5 4 3)
2
(4 5 6)
18

The same ideas exist today in imperative languages too:

console.log([1, 2, 3].map((x) => x * x), [5, 1, 4, 2, 3].filter((x) => x > 2), [1, 2, 3, 4].reduce((a, b) => a * b, 1));

[ 1, 4, 9 ] [ 5, 4, 3 ] 24

Java 8 streams (list.stream().map(...).filter(...)), Python’s map, filter and lambdas, and C#‘s LINQ were taken from functional programming.

Tail recursion

(define (fact1 n) (if (= n 0) 1 (* n (fact1 (- n 1)))))
(define (fact2 n acc) (if (= n 0) acc (fact2 (- n 1) (* n acc))))
(fact2 5 1)                                  ; 120

In fact1, a multiplication is waiting after the recursive call: the ARI of every call must stay on the stack, and if n is large the stack overflows. In fact2 the call is the last job: its result is returned directly. Scheme turns this into a loop (the new call reuses the old ARI). The way to make a function tail recursive is usually to add an accumulator parameter.

Other functional languages

Common mistakes

(car (cdr '(a b c)))

(cdr '((a b) c d))
(car '((a b) c d))
(cdr '(x))

(cons 'a '(b c))
(cons '(a) '(b))
(cons 'a 'b)

(car (car (cdr '(1 (2 3) 4))))

(define (f n)
  (if (= n 0)
      1
      (* 2 (f (- n 1)))))

(map (lambda (x) (* x x)) '(1 2 3))

(let ((a 2) (b 3)) (+ a (* a b)))

(define (filter p lst)
  (cond ((null? lst) '())
        ((p (car lst)) (cons (car lst) (filter p (cdr lst))))
        (else (filter p (cdr lst)))))

(define (compose f g) (lambda (x) (f (g x))))
((compose car cdr) '(1 2 3))

(define (count-atoms l)
  (cond ((null? l) 0)
        ((pair? (car l)) (+ (count-atoms (car l)) (count-atoms (cdr l))))
        (else (+ 1 (count-atoms (cdr l))))))

(define (fact1 n) (if (= n 0) 1 (* n (fact1 (- n 1)))))
(define (fact2 n acc) (if (= n 0) acc (fact2 (- n 1) (* n acc))))

(define (adder n) (lambda (x) (+ x n)))
(map (adder 3) '(1 2 3))