Sequence data structures

The pair data structure allows us to create pairs of pairs, laying the foundation for the (linked) list data structure for representing general sequences.

This allows further useful abstractions:

• mapping over lists: general function to apply element-wise functions to a list (SIMD idea)

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))```

• tree structures: for hierarchical structures
  • and now we can even map functions over trees.
• conventional interfaces to define standard generalized operations on compound data structures
  • eg. treat the lists as signals and functions as signal processing modules.
  • allows modularity in software design.

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))