List Abstractions

These are the list abstractions that you will cover in this class, and this page is meant to help you remember them.

map

Constructs a list by applying fn to each item on lx.

;; map: (X Y) [X -> Y] [List-of X] -> [List-of Y]
(define (map fn lx) ...)
(map fn (list x1 ... xn)) == (list (fn x1) ... (fn xn))

filter

Produces a list from those items on lx for which predicate holds.

;; filter: (X) [X -> Boolean] [List-of X] -> [List-of X]
(define (filter predicate lx) ...)

foldr/foldl

foldr: Applies fn from right to left to each item in lx and base.

foldl: Applies fn from left to right to each item in lx and base.

;; foldr: (X Y) [X Y -> Y] Y [List-of X] -> Y
(define (foldr fn base lx) ...)
(foldr fn base (list x1 ... xn)) == (fn x1 ... (fn xn base))

;; foldl: (X Y) [X Y -> Y] Y [List-of X] -> Y
(define (foldl fn base lx) ...)
(foldl fn base (list x1 ... xn)) == (fn xn ... (fn x1 base))

build-list

Constructs a list by applying f to 0, 1, …, (sub1 n).

;; build-list: (X) Nat [Nat -> X] -> [List-of X]
(define (build-list n f) ...)
(build-list n f) == (list (f 0) ... (f (- n 1)))

sort

Produces a version of lx that is sorted according to cmp.

;; sort: (X) [List-of X] [X X -> Boolean] -> [List-of X]
(define (sort lx cmp) ...)

andmap/ormap

andmap: Determines whether predicate holds for every item on lx.

ormap: Determines whether predicate holds for at least one item on lx.

;; andmap: (X) [X -> Boolean] [List-of X] -> Boolean
(define (andmap predicate lx) ...)
(andmap predicate (list x1 ... xn)) == (and (predicate x1) ... (predicate xn))
 
;; ormap: (X) [X -> Boolean] [List-of X] -> Boolean
(define (ormap predicate lx) ...)
(ormap predicate (list x1 ... xn)) == (or (predicate x1) ... (predicate xn))