Racket provides useful primitive procedures for lists:
list-ref takes as arguments a list and a number
n and returns the
nth item of the list. The first element of the list is indexed as
0, meaning it is the
0th element of the list. Here's how
list-ref is defined:
(define (list-ref lst n) (if (= n 0) (car lst) (list-ref (cdr lst) (- n 1))))
and here is an example of how it works:
-> (define squares (list 1 4 9 16 25)) squares -> (list-ref squares 3) 16
null? takes a list as an argument and returns
#t if the list is empty. Otherwise, it returns
(null? (list 1 3)) #f (null? '()) #t
length takes a list as an argument and returns the number of items in a list. Here's how
length is defined:
(define (length items) (if (null? items) 0 (+ 1 (length (cdr items)))))
and here is an example:
-> (define odds (list 1 3 5 7)) odds -> (length odds) 4
From here on out, we’ll be mostly using lists and pairs rather than sentences. This is great, since it means we'll be able to take a closer look at how data is represented by Racket. But, this also means that a lot of the important higher order functions we previously defined with sentences must now be rewritten to work with pairs.
Recall the HOF
every, which takes in a function and a sentence, and returns a sentence with the function applied to every element of the sentence. The equivalent of this HOF using pairs is called
map, which it takes in a function and a list, and returns a list with the function mapped to every element in the list.
map is a recursively defined function, as you can see here:
(define (map proc items) (if (null? items) null (cons (proc (car items)) (map proc (cdr items)))))
null? for lists is analogous to the procedure
empty? for sentences, and checks whether or not the given argument is the empty list. Here are a few example calls to
-> (map square (list 1 2 3 4 5)) (1 4 9 16 25) -> (map car (list (cons 1 2) (cons 3 4) (cons 5 6))) (1 3 5)
We already had a quick glimpse of
filter in the
filtered-accumulate problem in Homework 2, so you should already have some idea of what the HOF
filter should do.
filter takes in two arguments, a predicate and a list, and returns a list with only elements that satisfy the predicate. Take a look at the formal definition:
(define (filter pred lst) (cond ((null? lst) null) ((pred (car lst)) (cons (car lst) (filter pred (cdr lst)))) (else (filter pred (cdr lst)))))
And here are some examples:
-> (filter odd? '(1 2 3 4 5)) (1 3 5) -> (filter (lambda (x) (> x 2)) '(1 2 3 4 5)) (3 4 5)
Finally, there is the procedure
accumulate for sentences. This procedure takes in a function of two arguments, a base case value, and a sentence of values, and continuously combines the values in the list using this operation and ending/starting with the base case value. There are two equivalents to accumulate for lists:
foldr. Both take in a function of two values, a base case value, and a list.
fold-left starts from the last (right-most) element in the list and continuously applies the function recursively until it reaches the first element of the list. Thus, it folds to the left. For example, here are the steps to evaluate a call to
-> (foldl cons '() '(1 2 3 4)) ... (cons 4 (cons 3 (cons 2 (cons 1 '())))) (4 3 2 1)
Here's another example:
-> (define combiner (lambda (x y) (cons (add1 x) y))) combiner (foldl combiner '() '(1 2 3 4)) ... (combiner 4 (combiner 3 (combiner 2 (combiner 1 '())))) ... (5 . (4 . (3 . (2 . ())))) (5 4 3 2)
On the other hand,
fold-right starts from the first (left-most) element in the list and continuously applies the function recursively until it reaches the last element of the list. Thus, it folds to the right. Take these calls for example:
-> (foldr cons '() '(1 2 3 4)) ... (cons 1 (cons 2 (cons 3 (cons 4 '())))) (1 2 3 4) -> (foldr + 0 '(1 2 3 4)) ... (+ 1 (+ 2 (+ 3 (+ 4 0)))) 10
We now have two versions of
accumulate, where the values of
foldr would only differ when they are called with combiner functions in which order matters.
To make the transition easier, here’s a table illustrating some operations on sentences and their equivalent for lists.