Module 7 Extra Materials

Abstract List Functions

• sort - sort a list given a function defining order
  • The function consumes an x and an y and returns true if x comes before y in a sorted list.
• filter - select/retain certain element from a list lst given a predicate p
  • The list produced contains only the elements that produces true when applied to p.
• map - given a list lst and a unary (i.e. one parameter) function f, produce a list contains results of f applied to every element of lst.
• build-list - given a natural number n and a function f, produces

(list (f 0) (f 1) ... (f (- n 1)))

• foldr - given a function f, a base case b, and a list (list x1 x2 ... xn), produces

(f x1 (f x2 ( ... (f xn b) ... )))

This is a generalization of structural recursion on lists. Imagine you are working with the list template, and you decide to write a function for the recursive case (that is, the consumed list is not empty):

(f (first lst) (list-template (rest lst)))

This is how the function f in foldr will be used.

• andmap, ormap - like map, except the function f must be a predicate, and the results of the function applied to the elements of the list are combined using and or or, respectively.

For a complete list, see this figure from the book: Scheme's built-in abstract functions for list-processing

An extra example: afind

The afind function finds the first Association (As) that under a predicate produces true in an Association List (AL). If no such Association exists, produce false.

We start with the purpose and contract (you do not have to know how to write this):

;; (afind p? alop) produces the first Association in alop that produces true 
;; when the key of the association applied to p?.
;; afind: (X -> Bool) (listof (list X Y)) -> (Anyof (list X Y) false)

We are not using our traditional designation of using As or AL, since we didn't really learn how to express a type being dependent on another type using data definitions. However, this would work on any kind of lists of associations in this structure, so (listof (list X Y)) is acceptable here.

Some examples:

(check-expect (afind positive? (list (list 0 1)
                                       (list -2 3)
                                       (list 4 'sym)))
              (list 4 'sym))
(check-expect (afind (lambda (elem) (equal? elem "apple"))
                       (list (list "orange" 5)))
              false)

The implementation like a simple recursion on a list. Let's try writing it using foldr. in the code snippet below, fn refers the function to be passed into foldr, and base is the base case, to be filled in.

(define (afind p? alop)
  (foldr fn base alop))

The base case is false. So...

(define (afind p? alop)
  (foldr fn false alop))

What happens in the recursive case? Well, imagine we are writing the recursive case in a normal recursive function. We have those two parts available:

• fst which is (first alop)
• recur-result which is (afind p? (rest alop))

The logic in the recursive case depends on if the key of fst produces true when applied to p?. I would like you to think about how to write the recursive case for a bit, then compare your answer with ours.

Now we can convert our logic from text to code. Again, make sure you have work on it yourself before checking the answer.

(define (afind p? alop)
  (foldr (lambda (fst recur-result)
           (cond
             [(p? (first fst)) fst]
             [else recur-result]))
         false
         alop))

Exercises

1. Write afind with explicit recursion (that is, without using any abstract list functions).
2. Which version is more efficient? Why?

In fact, at the bottom of Scheme's built-in abstract functions for list-processing, there is one function assf which is exactly the afind function we write.