Built-in Abstract Functions

Using built-ins

To realize that we can use a built-in function on a list, the first thing to do is to realize that the operation we are trying to achieve is fairly generic.

The specific method is to compare the signature we want to design to the signature of a built-in function minus their function argument. For example, assume we have the following function being coded:

;; (listof Image) -> (listof Image)
;; produce list of only those images that are wide?
(check-expect (wide-only) (list I1 I2 I3 I4 I5) (list I2 I4))
 
(define (wide-only loi) empty) ;stub

What we can do is compare the signature to those of bullt ins. In this case, appropriate functions would be filter and map, given:

(@signature (X -> boolean) (listof X) -> (listof X))
;; produce a list from all those items on lox for which p holds
(define (filter p lox) ...)
 
(@signature (X -> Y) (listof X) -> (listof Y))
;; produce a list by applying f to each item on lox
;; that is, (map f (list x-1 ... x-n)) = (list (f x-1) ... (f x-n))
(define (map f lox) ...)

In this scenario, obviously we want filter. Specifically, we choose filter because the output list is smaller than the input list, whereas in map both input and output lists are of the same lenght.

Templating with built-ins

To create a template, all we have to do is the following:

(define (wide-only loi)
	(filter ... loi))

Note that we are saying is that, while we don’t yet now how we are going to use filter, we know that the filter will be applied to loi somehow. Additionally, we do not use the header from the function we are using.

To code the rest of the function body, we need to fill in the .... This is accomplished by looking at the signature of the relevant function, in this case:

(X -> Boolean) (listof X) -> (listof X)

What this tells us is that the template needs to be filled with some sort of predicate, given that filter produces a Boolean. Assuming it was defined before, we can then finish our definition as a “one-liner”:

(define (wide-only loi)	(filter wide? loi))

Note: While we still have to produce unit tests for our functions, if we are using a built-in the requirement for a base test can be disposed of, since those built-ins provide the required testing functionality in themselves.

Examples

Using foldr

Given the following, use a built-in to pass the check-expect:

;; (listof Number) -> Number
;; sum the elements of a list
(check-expect (sum (list 1 2 3 4)) 10)
 
;(define (sum lon) 0) ;stub

The signature for foldr looks as follows:

(@signature (X Y -> Y) Y (listof X) -> Y)
;; (foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base))
(define (foldr f base lox) ...)

What we see is that fold takes in a function, which itself has two arguments and produces one, an argument of the same type as the output of the first argument, and a list of type of the first argument to the initiaul function.

Using sum as an example, we can start by laying down the foundation of the function definition:

(define (sum lon)
	(foldr ... ... lon))

The question then becomes what to place in each of those .... A good hint is to look towards the end of the foldr signature, where we see (f x-n base). This can be translated to (+ (- (first lon) 1) 0).

Another useful tip is to write out what the type of each argument for the built in function is going to be, given the function that we are trying to code. For example, looking at the signature of sum we know that the product is going to be a Number. Thus:

(define (sum lon)
			(Number Number -> Number) Number
	(foldr            ...               ...      lon))

Thus, the solution to sum is:

(define (sum lon)
	(foldr + 0 lon))

Note that foldl is the tail recursive version of foldr.

Built-in composition

Suppose we have the following signature and purpose:

;; Natural -> Natural
;; produce the sum of the first n nautural numbers
(check-expect (sum-to 3) (+ 0 1 2))
 
; (define (sum-to n) 0) ;stub

When comparing this to the signatures of the built-in functions we can see that there is no built in that consumes and produces Natural. However, we can simply “pipe” the functions to produce what we want using build-list.

(define (sum-to n)
	(foldr + 0 (build-list n identity)))

Identity and build-list

The identity function will always return its input. In other words:

(identity x) -> x
 
(identity 42) -> 42
(identity "meow") -> "meow"

build-list consumes a Natural and a function and returns a list of (fn (- n 1)). It’s signature is as follows:

(@signature Natural (Natural -> X) -> (listof X))
;; produces (list (f 0) ... (f (- n 1)))
(define (build-list n f) ...)

This can be used in combination with identity to generate a list of natural numbers by using:

(build-list 5 identity) -> (list 0 1 2 3 4)

Most languages have similar functionality. In Python, this is exactly the same thing that range does.

x = [i for i in range(5)]
x 
>>> [0, 1, 2, 3, 4]