Index: Check Syntax button, Some abstract functions, lambda
Make sure you are using the Advanced language level.
Many of you have already experimented with DrScheme's "Check Syntax" button. But you might not have discovered some of the neat features it allows.
To do: Write a small recursive function and left-click on the "Check Syntax" button.
DrScheme highlights different parts of the syntax (such as user-defined names, predefined names, constants, and keywords) in different ways. As many of you have noticed, it also highlights unbound names, which are probably typos, and it draws arrows from bound variables to their binding occurrences.
To do: Right-click on a variable name. You'll see a small menu. Try each of the options.
Today we introduce some handy abstract functions, defined by equations:
(map f (list x1 ... xN)) = (list (f x1) ... (f xN))
(foldr f e (list x1 x2 ... xN)) = (f x1 (f x2 ... (f xN e)))
(foldl f e (list x1 x2 ... xN)) = (f xN ... (f x2 (f x1 e))...)
(filter p? (list x1 ... xN)) = (list xI ... xJ)
if (p? xI) = #t and ... and (p? xJ) = #t
You've already seen foldr in class and last lab.
Some examples:
(map add1 (list -1 5 -3 4 2)) = (list 0 6 -2 5 3)
(foldr max 0 (list -1 5 -3 4 2)) = 5
(foldl max 0 (list -1 5 -3 4 2)) = 5
(foldr cons empty (list -1 5 -3 4 2)) = (list -1 5 -3 4 2)
(foldl cons empty (list -1 5 -3 4 2)) = (list 2 4 -3 5 -1)
(filter positive? (list -1 5 -3 4 2)) = (list 5 4 2)
To do: Develop definitions of map and filter that follow the template for lists. (As a challenge, define foldl outside lab.)
To do: Develop definitions of map and filter that use foldr.
To do: Here's a solution for the homework 3 elevator problem. Make a copy and edit it. Where possible, use the above abstract functions, and several functions will become one-liners. Here's a new solution.
To do: Above we say
(map add1 (list -1 5 -3 4 2)) = (list 0 6 -2 5 3)
Write a function
;; map-add7 : list-of-numbers -> list-of-numbers
;; (map-add7 (list -1 5 -3 4 2)) = (list 6 12 4 11 9)
Write a function
;; map-addn : number list-of-numbers -> list-of-numbers
;; (map-addn 1 (list -1 5 -3 4 2)) = (list 0 6 -2 5 3)
;; (map-addn 7 (list -1 5 -3 4 2)) = (list 6 12 4 11 9)
In each of these, you probably defined and named a (local or global) helper function. Here's an alternate solution for the last problem:
(define (map-addn n lon)
(map (lambda (m) (+ m n)) lon))
This should look a lot like your solution except for being shorter and using
except this lambda keyword.
lambda evaluates to an unnamed (or anonymous) helper function.
(lambda (x) ...)
= (local ((define (unique-name x) ...))
unique-name)
It is convenient when you just want to use a helper function once, so
having a name isn't important.
To do: Try the following, plus some of your own examples. Try to understand each example before typing them into DrScheme.
(lambda (x) (+ 3 x))
((lambda (x) (+ 3 x)) 5)
(lambda (x) (+ 3 5))
((lambda (x) (+ 3 5)) 'silly)
(lambda () (+ 3 5))
((lambda () (+ 3 5)))
(lambda (x) x)
((lambda (x) x) 5)
Observe that we now allow the function position to be an arbitrary
expression, not just a name. Typically, it is either a name or a
lambda expression, but it can be anything that evaluates
to a function.
We have introduced an anonymous function as shorthand for a kind of named function. We could have reversed this, eliminating the
(define (foo x) ...)
syntax in favor of
(define foo (lambda (x) ...))
For the curious... It looks like you can't define recursive functions without having a name for them. Well, you can, but it's very tricky. See Comp 311.