7.2.1.3 Lists as sequences

Function: position obj lst

position returns the 0-based position of obj in lst, or #f if obj does not occur in lst.

Example:

(position 'foo '(foo bar baz bang))
   ⇒ 0
(position 'baz '(foo bar baz bang))
   ⇒ 2
(position 'oops '(foo bar baz bang))
   ⇒ #f

Function: reduce p lst

reduce combines all the elements of a sequence using a binary operation (the combination is left-associative). For example, using +, one can add up all the elements. reduce allows you to apply a function which accepts only two arguments to more than 2 objects. Functional programmers usually refer to this as foldl. collect:reduce (see Collections) provides a version of collect generalized to collections.

Example:

(reduce + '(1 2 3 4))
   ⇒ 10
(define (bad-sum . l) (reduce + l))
(bad-sum 1 2 3 4)
   ≡ (reduce + (1 2 3 4))
   ≡ (+ (+ (+ 1 2) 3) 4)
⇒ 10
(bad-sum)
   ≡ (reduce + ())
   ⇒ ()
(reduce string-append '("hello" "cruel" "world"))
   ≡ (string-append (string-append "hello" "cruel") "world")
   ⇒ "hellocruelworld"
(reduce anything '())
   ⇒ ()
(reduce anything '(x))
   ⇒ x

What follows is a rather non-standard implementation of reverse in terms of reduce and a combinator elsewhere called C.

;;; Contributed by Jussi Piitulainen (jpiitula @ ling.helsinki.fi)

(define commute
  (lambda (f)
    (lambda (x y)
      (f y x))))

(define reverse
  (lambda (args)
    (reduce-init (commute cons) '() args)))

Function: reduce-init p init lst

reduce-init is the same as reduce, except that it implicitly inserts init at the start of the list. reduce-init is preferred if you want to handle the null list, the one-element, and lists with two or more elements consistently. It is common to use the operator’s idempotent as the initializer. Functional programmers usually call this foldl.

Example:

(define (sum . l) (reduce-init + 0 l))
(sum 1 2 3 4)
   ≡ (reduce-init + 0 (1 2 3 4))
   ≡ (+ (+ (+ (+ 0 1) 2) 3) 4)
   ⇒ 10
(sum)
   ≡ (reduce-init + 0 '())
   ⇒ 0

(reduce-init string-append "@" '("hello" "cruel" "world"))
≡
(string-append (string-append (string-append "@" "hello")
                               "cruel")
               "world")
⇒ "@hellocruelworld"

Given a differentiation of 2 arguments, diff, the following will differentiate by any number of variables.

(define (diff* exp . vars)
  (reduce-init diff exp vars))

Example:

;;; Real-world example:  Insertion sort using reduce-init.

(define (insert l item)
  (if (null? l)
      (list item)
      (if (< (car l) item)
          (cons (car l) (insert (cdr l) item))
          (cons item l))))
(define (insertion-sort l) (reduce-init insert '() l))

(insertion-sort '(3 1 4 1 5)
   ≡ (reduce-init insert () (3 1 4 1 5))
   ≡ (insert (insert (insert (insert (insert () 3) 1) 4) 1) 5)
   ≡ (insert (insert (insert (insert (3)) 1) 4) 1) 5)
   ≡ (insert (insert (insert (1 3) 4) 1) 5)
   ≡ (insert (insert (1 3 4) 1) 5)
   ≡ (insert (1 1 3 4) 5)
   ⇒ (1 1 3 4 5)
   

Function: last lst n

last returns the last n elements of lst. n must be a non-negative integer.

Example:

(last '(foo bar baz bang) 2)
   ⇒ (baz bang)
(last '(1 2 3) 0)
   ⇒ ()

Function: butlast lst n

butlast returns all but the last n elements of lst.

Example:

(butlast '(a b c d) 3)
   ⇒ (a)
(butlast '(a b c d) 4)
   ⇒ ()

last and butlast split a list into two parts when given identical arguments.

(last '(a b c d e) 2)
   ⇒ (d e)
(butlast '(a b c d e) 2)
   ⇒ (a b c)

Function: nthcdr n lst

nthcdr takes n cdrs of lst and returns the result. Thus (nthcdr 3 lst) ≡ (cdddr lst)

Example:

(nthcdr 2 '(a b c d))
   ⇒ (c d)
(nthcdr 0 '(a b c d))
   ⇒ (a b c d)

Function: butnthcdr n lst

butnthcdr returns all but the nthcdr n elements of lst.

Example:

(butnthcdr 3 '(a b c d))
   ⇒ (a b c)
(butnthcdr 4 '(a b c d))
   ⇒ (a b c d)

nthcdr and butnthcdr split a list into two parts when given identical arguments.

(nthcdr 2 '(a b c d e))
   ⇒ (c d e)
(butnthcdr 2 '(a b c d e))
   ⇒ (a b)

Function: butnth n lst

butnth returns a list of all but the nth element of lst.

Example:

(butnth 2 '(a b c d))
   ⇒ (a b d)
(butnth 4 '(a b c d))
   ⇒ (a b c d)