(list-of 'a) 
(cons 'a (list-of 'a)) 
nil
(list-of problems)These problems were either made up or cribbed shamelessly from all over the internet.
When working through these problems, think about the data and your contracts if you get stuck.
A list is a special type of structure. It has two differences to the structures we've looked at before:
The functions to create and access members have goofy names
A list can contain a list; it has a recursive structure
The latter is more important than the former. A list is either the
empty list, or a list of one element and a list. This recursive
structure means that a list can have an arbitrary length. It also
establishes the natural pattern of recursion over a list: a cond
with two clauses, one to handle the empty list case, one to handle the
non-empty case.
The data definition for a list of symbols is
;;DATA DEFINITION ;; A list-of-symbol is a ;; empty, OR ;; (cons symbol list-of-symbol)
To construct lists you need to know:
'() is our way of writing the empty list
(null? list) is true if the list is the empty list
(cons element list) constructs a list given an element and
a list
(car list) gets the element part of a non-empty list
(cdr list) gets the rest (list) part of a non-empty list
The following procedures all construct lists from lists
Define a procedure called square-list that consumes a (list-of numbers)and
returns a list where each element has been squared.
Define a procedure called add-one-to-list that consumes
a (list-of numbers)and returns a (list-of numbers)where each element has had one added to it.
Define a procedure called replace-name that consumes a
(list-of symbols)and returns a (list-of symbols)where each occurrence of 'noel has been
replaced by 'matt.
Define a procedure called double that takes a symbol and a
(list-of symbols), and doubles every occurrence of the symbol in the list.
;;EXAMPLES ;; All examples should evaluate to true. (equal? (double 'a '(a b c)) '(a a b c)) (equal? (double 'foo '(bar geeble woe)) '(bar geeble woe))
The following functions all process a list to single result.
Define a procedure called sum-list that consumes a
(list-of numbers) and
returns the sum of the elements of that list. The contract for this first
procedure has been provided for you:
;;CONTRACT ;; sum-list : lon -> number
Define a procedure called mult-list that consumes a (list-of numbers)and
returns the result of multiplying all the numbers in the list together.
Define a procedure called average that consumes a (list-of positive-numbers)and
returns the result of averaging all the numbers in the list together.
Define a procedure called all-numbers? that consumes a (list-of numbers)and returns true if all the elements of the list are numbers.
Define a procedure called all-symbols? that consumes a (list-of symbols)and returns true if all the elements of the list are symbols.
Define a procedure called all-positive-numbers? that consumes
a (list-of numbers)and returns true if all the elements of the list are
positive numbers. Note: We will revisit how to abstract over these
two procedures later.
Define a procedure called average-wrapper that consumes a
(list-of numbers)and averages all the numbers in the list if and only if they are all
positive numbers, and returns false otherwise. (Note this
procedure breaks our normal rule of attempting to only return one type of
data.)
;;CONTRACT ;; average-wrapper : (list-of numbers) -> number | boolean ... ;;EXAMPLES ;; All examples should be true. (= (average-wrapper '(1 2 3)) 2) (= (average-wrapper '(2 3 4 5 0)) 3)
Define a procedure called count-symbols that consumes a (list-of symbols)and returns the number of symbols in the list.
Define a procedure called my-length that takes a (list-of thingies)and
returns the length of the list. Is this different than
the previous question?
Given the data definition
;;DATA DEFINITION ;; A Schemer is a ;; -- first-name isa symbol ;; -- mental-age isa positive-number ;; -- walks-on-coals? isa boolean (define-struct schemer (first-name mental-age walks-on-coals?))
write a procedure called extract-mental-ages that consumes a (list-of schemers) and returns a
list of mental-ages. You may need to create a few Schemers first.
Define a procedure called average-mental-age that, given a
(list-of schemers), computes the average mental age of the
Schemers. Hint: You've already written everything you need to do
this problem.
Define a procedure called remove that takes a symbol
and a (list-of symbols), and returns a list with all occurances of the symbol removed
from the list.
Define a procedure called uniqify that takes a (list-of symbols)and
removes all duplicates from the list. Hints: Your solution will not
be optimal given the tools you have so far. One solution might involve
the use of member.
;;CONTRACT ;; member : thingie list -> boolean | list
Member is typically used in any context where a boolean result is expected,
although you should not that it returns either #f or the list
beginning with the first occurence of the found thingie. member might
only work in a full Scheme, as opposed to one of the HtDP learning levels.
Define a procedure called adjacent-sums that takes a (list-of numbers)and
returns a (list-of numbers), where adjacent pairs have been added together. Assume the
input list is at least two elements in length and even in length.
;;EXAMPLES ;; All examples should evaluate to true. (equal? (adjacent-sums '(1 2 3 4 5 6)) '(3 7 11)) (equal? (adjacent-sums (adjacent-sums '(1 1 1 1))) '(4))
Define a procedure called adjacent-sums-wrapper that takes a
(list-of numbers)and returns a (list-of numbers)if and only if the length of the list is even and
greater than two. Otherwise, return false. Hint: Don't forget
procedures you have written previously. (Note this procedure breaks our
normal rule of attempting to only return one type of data.)
The whole point of covering structures was to provide you with tools
that might help you avoid ugly mixed-data situations. We know that
this isn't always possible; the next section lets you play with some
of the type predicates in Scheme (number?, integer?, symbol?,
pair?, list?, boolean?, void?, null?) as you make your way down the
list. (Are null? and
void? really type predicates?)
One kind of mixed data is the most common Schemely representation of trees. So far, we've been recurring on lists based on the following data definition:
;;DATA DEFINITION ;; A LIST is either ;; - empty, or ;; - (cons thing LIST)
where car is used to grab the head, or first item, of the list, and
cdr is used to grab the tail, or rest, of the list.
;; '(a b c d e f g) ;; ^ ----------- ;; | cdr ;; car ;; ;; These should evaluate to true. ;; (symbol? (car '(a b c d e f g))) ;; (list? (cdr '(a b c d e f g)))
This means that when recurring on lists, we have to remember to ask two questions (or, one question and an else):
Is the list empty? (null?)
Is it a list? (pair?, list?)
In moving on to working with trees, we start with the data definition:
;;DATA DEFINITION ;; A tree is either ;; - empty, or ;; - (cons thing tree tree)
The critical difference here is that there are two points where we recur. You can already see why we don't like working with Scheme lists for structured trees like a binary tree; it would be much nicer to do something like
;;DATA DEFINITION ;; A binary-tree is either ;; - an empty-binary-tree ;; - (make-binary-tree item binary-tree binary-tree) ;; (define-struct empty-binary-tree ()) (define-struct binary-tree (item left right))
In writing code for the latter definition, our code would look like (assuming we were summing the nodes of the tree):
(define (bin-tree-sum bt) (cond [(empty-binary-tree? bt) 0] [else (+ (binary-tree-item bt) (bin-tree-sum (binary-tree-left bt)) (bin-tree-sum (binary-tree-right bt)))]))
It is very clear what we're working with. Our code comes out being
structured a little differently when working with Scheme lists of arbitrary
data, because a sublist can appear at any point in the list. So, we are
constantly asking of the car is a list?, and branching our
recursion in two different cond clauses based on the result of this test.
Hope that all helped; if not, good luck.
Define a procedure called deep-count-only-symbols that
extends count-only-symbols by recurring into any lists
encountered along the way.
;;EXAMPLES (= (deep-count-only-symbols '(a b (c 4 #f (d e)) (g 3))) 6)
Define a procedure called deep-sum-list that extends
sum-list and sums all the numbers encountered in a (deep-list-of numbers).
Define a procedure called add-only-numbers that takes a (list-of thingies)and returns the result of summing the numbers in the list. For your
first solution, only traverse the top level of the list.
;;EXAMPLES ;; All examples should evaluate to true. (= (add-only-numbers '(1 a 2 b 3 c (4 d) 5 e)) 11)
Define a procedure called deep-add-only-numbers that extends
add-only-numbers by doing a deep addition,
traversing down any sublists encountered along the way.
;;EXAMPLES ;; All examples should evaluate to true. (= (add-only-numbers '(1 a 2 b 3 c (4 d) 5 e)) 15)
Define a procedure called gather-symbols that takes a (list-of thingies)and returns a (list-of symbols)built from all the symbols encountered in the list.
;;EXAMPLES ;; All examples should evaluate to true. (= (gather-symbols '(1 #t a foo (3 4 goes) #f shopping)) '(a foo goes shopping))
Hint: You may find append useful in this
solution. Maybe. I don't know if it is necessary, actually...
Up until now, you haven't worked with any binding forms in Scheme other
than define. There are three common binding forms that you should
come to know and love: let, letrec, and lambda.
This section will introduce two of the three.
letlet binds Scheme values to variables in a lexical scope. This means
that variables bound in a let are only visible inside the
let. For example
(let ([x 3] [y 4]) ... inside the let ...)
In the snippet above, any code written inside the letwill be able to
access the variables x and y, which will have the values
3 and 4, respectively.
letcan bind any Scheme value to a variable. For example, we might want to
bind the result of some calculation to use it several times in a nested cond:
(cond [(null? ls) 0] [else (let ([sqr (square (car ls))] [len (length (cdr ls))]) (cond [(= sqr len) ... do something ...] [(> sqr len) ... do something else ...] [(<= sqr len) ... keep doing things ...]))])
let can appear anywhere a Scheme expression can appear. The value of a
let expression is the value of the last expression in the let.
Note that a let will fail at compile time if you attempt something like
the following:
(let ([x 4] [y (* x 2)]) ... inside the let ...)
The left-hand sides of the let cannot see the right-hand sides, or
bindings, of the let. You could always nest your let expressions if you
must have them be visible to each-other:
(let ([x 4]) (let ([y (* x 2)]) ...inside both lets...))
This isn't poor form, but if you find yourself nesting too many let
expressions, you might want something else.
letrecletrec looks just like let, mostly. It's behavior is different, and you
will truly be wise when you fully understand letrec.
(letrec ([x 4] [y (* x 2)]) y)
will evaluate to 4. In a letrec, the bindings (right-hand sides) are
visible to each-other. The example given is a bit trivial; letrec is more
often used to bind a recursive procedure that is only needed within the
scope of the letrec.
Which leads me to...
lambdalambda is the anonymous procedure. When you have been writing
(define (foo x y z) ...)
that has been equivalent to
(define foo (lambda (x y z) ...))
The reason lambda is a binding form is because, inside it's body (the
... above), the identifiers (x, y, z, above) are bound to the values passed
in. So lambda is both the anonymous procedure and also a perfectly
capable binding form. In fact, it is an insanely powerful binding form,
which we will make use of later when we move into the Really Cool Stuff.
The second example makes explicit the fact that define is binding a procedure
of one argument to the name foo. For the moment, this is the extent
to which we are going to dazzle you with lambda; consider it as nothing
more than a way to create a procedure. If you wonder why letrec is
something you can aspire to understanding, you can wonder even more why
lambda is the Ultimate. Caution grasshopper, and all that.
With what we have so far, we can write procedures like:
;;CONTRACT ;; funky-func : ls -> ls ;;PURPOSE ;; Takes a list, and returns a list of all even, negative numbers and ;; all sublists composed entirely of symbols with a length equal to 3. (define funky-func (lambda (ls) (let ([even-negative? (lambda (n) (and (number? n) (even? n) (> 0 n)))] [all-sym-len-3? (lambda (ls) (and (list? ls) (all-symbols? ls) (= (my-length ls) 3)))]) (cond [(null? ls) '()] [else (let ([first (car ls)] [rest (cdr ls)]) (if (or (even-negative? first) (all-sym-len-3? first)) (cons first (funky-func rest)) (funky-func rest)))]))))
Whoa. The outermost let binds two weird predicates that we wouldn't want
defined at the top level, because they're only going to be used in
this procedure, and they're kinda dumb. Note, though, that because I know
I'm working on mixed, ugly data, that I included predicates like
number? and list? in my helpers; I'm taking advantage of the
fact that the and will short-circuit, and evaluate to #f if it
fails the first type-check. Ahh.
The second use of let is a bit more gratuitous, but since we don't want
to keep re-evaluating (car ls), I bound it to a variable called
first. The binding of rest was just because I was binding parts
of the list; sometimes it helps to help yourself with a little bit of
renaming.
Now a (not very impressive) reason why you might want a
letrec. Furthermore, I'm going to show you how you can program
tail-recursively. Note that this is not a Good Thing necessarily; any
Scheme compiler worth its salt will optimize all recursions equally
well, so writing in the accumulator-passing style will (generally) not make your code N-times faster.
And we're not here to write fast code, we're here to program Schemely. This way, we can write cool compilers in Scheme that make our code screaming fast. Chez is a pretty good example of this; at 125K lines of code, it has always bootstrapped itself on reasonably current hardware in under 6 seconds. Dybvig would only add features to Chez as he developed it over the years if it improved or maintained the bootstrap time of the compiler. Kinda neat, I think.
Right. I digress.
Take sum-list as an example. In it's naturally recursive form, we
might write:
(define sum-list (lambda (ls) (cond [(null? ls) 0] [else (+ (car ls) (sum-list (cdr ls)))])))
if fed the list '(1 2 3), this will build up a recursive series of
calls that look like:
(sum-list '(1 2 3)) (+ 1 (sum-list '(2 3))) (+ 1 (+ 2 (sum-list '(3)))) (+ 1 (+ 2 (+ 3 (sum-list '())))) (+ 1 (+ 2 (+ 3 0))) (+ 1 (+ 2 3)) (+ 1 5) 6
We could, however, add a variable to ``collect'' or ``accumulate'' the result of the additions, instead of building the recursive expression to be evaluated.
So, we add an accumulator
;;CONTRACT ;; sum-list-acc : lon number -> number ;;PURPOSE ;; Sum a list of numbers. (define sum-list-acc (lambda (ls acc) (cond [(null? ls) acc] [else (sum-list-acc (cdr ls) (+ (car ls) acc))])))
Now, as we recur through the list, we're not building context. Instead,
we're simply increasing the value of acc as we zip down the list.
(sum-list-acc '(1 2 3) 0) (sum-list-acc '(2 3) 1) (sum-list-acc '(3) 3) (sum-list-acc '() 6) 6
Unfortunately, we have a leaky abstraction now. You shouldn't have to
remember to initialize the accumulator; the procedure should just take a
list, and be done with it. So, we write a wrapper (call it
sum-list*), and use letrec to help us out.
;;CONTRACT ;; sum-list* : lon -> number ;;PURPOSE ;; Sum a list of numbers. (define sum-list* (lambda (ls) (letrec ([sum-list-acc (lambda (ls acc) (cond [(null? ls) acc] [else (sum-list-acc (cdr ls) (+ (car ls) acc))]))]) (sum-list-acc ls 0))))
In a letrec, the right-hand side can see the left-hand side, and visa
versa. So, we locally bind a procedure of two arguments to
sum-list-acc, and use it in the body of the letrec. Because letrec
evaluates to the value of the last expression in its body, we're left with
the same result as if we called sum-list, with the same number of
arguments and same contract, but we've changed the implementation
transparently.
(I'm not confident what the local LShift style is, but there is another way
to do this with internal defines. Most compilers, I imagine, just
expand internal definitions into a letrec anyway, so these two methods
are equivalent.
(define sum-list* (let () (define sum-list-acc* (lambda (ls acc) (if (null? ls) acc (sum-list-acc* (cdr ls) (+ (car ls) acc))))) (lambda (ls) (sum-list-acc ls 0))))
But I'd encourage you not to work on developing styles like this until you
are comfortable with what we've been doing. We used this style often in
Scorth when writing compiler passes, because each pass would be a procedure
with a large, locally defined match expression that we wanted to stay
local to the pass we were working on. This saved us nesting a lot of letand letrec expressions.)
Define a procedure called my-reverse that reverses the contents
of a list.
Redefine a whole mess of the previous stuff in the accumulator-passing style.
By now you've probably noticed a characteristic pattern when recurring
on a list. You have a cond expression with two branches:
(cond [(null? ls) (do-stop-action)] [else (do-something-with-car) (recur)])
It would be nice to abstract this pattern in some way so we don't have to keep typing it out. Consider three examples:
Define a procedure called square-list that consumes a (list-of numbers)and
returns a list where each element has been squared.
Define a procedure called add-one-to-list that consumes
a (list-of numbers)and returns a (list-of numbers)where each element has had one added to it.
Define a procedure called replace-name that consumes a
(list-of symbols)and returns a (list-of symbols)where each occurrence of 'noel has been
replaced by 'matt.
Write down the contracts of each function. What's similar? What's different?
If we use 'a to stand for any type, we can write the contract of
these functions as (list-of 'a) -> (list-of 'a). These
functions only differ by what they do to the list they receive.
Assume the function fn is defined to perform the correct
operation of each example above. Write a function that assumes
fn has been defined correctly and can express each of the three
examples above by changing the value of fn. Call this function
my-map.
Scheme lets us pass a function as a value. Change your definition of
my-map to accept fn as a parameter. It should have a
contract my-map : ('a -> 'a) (list-of 'a) -> (list-of 'a)
Now define procedures square, add1 and
replace that you can pass to my-map to complete the
three examples. Congratulations, you just used a higher-order
function!
Often times we won't to write a separate procedure like we did with
square, add1 and replace. In these cases we
can use a lambda to create the higher order function without
giving it a name.
Write square-list using my-map and lambda
Write add-one-to-list using my-map and lambda
Write replace-name using my-map and lambda
Define a function called filter that takes a predicate and a
list. It returns a list containing each member of the input list for
which the predicate didn't return #f.
Write remove using filter.
Using filter write a function that removes all even numbers
from a (list-of numbers).
Let's look at capturing other patterns with higher order functions. A lot of the examples we did above returned a single value such #t or #f, or the sum of all the numbers of the list.
Define a function reduce that takes three values: a function
of two arguments, a value (the seed), and a list. The result of applying
reduce to the empty list is the seed. The result of applying
reduce to a non-empty list is the value of the function
applied to the first element of the list and the result of applying
reduce to the rest of the list.
Write all-numbers? using reduce
Write all-symbols? using reduce
Write count-symbols using reduce
Write my-length using reduce
Write sum using reduce. sum takes a (list-of numbers)and
returns the sum of all the numbers in the list.
Write using sum and my-length. Can you write
average using reduce and lambda?
Let's now look at the structure of a list again. There is a simple recursive defintion for a list:
(list-of 'a) (cons 'a (list-of 'a)) nil
This matches the natural recursive form we used to write out first
functions on lists. At this point you might be interested to know if
there is a function like my-map that we can write that will
capture all the possible functions on a list. There is, and it's
called fold. It's not hard to write. We already have, except
we called in reduce! By choosing appropriate values for the
seed we can do any processing we want on a list. Note how the
definition of fold mirrors the recursive definition of a list.
Each distinct part of list (cons or nill; we call these constructors)
has a transformation specified for it (the function and the seed
respectively).
Write fold
Write my-reverse using fold
Write uniqify using fold
Write my-map using fold
Write filter using fold
The version of fold we have written in usually known as
fold-right. If we had written an accumulator-passing version
it would be what is normally known as fold or sometimes
fold-left.
For any regular (or algebraic) type we can write a fold function that can express all uses of data of the that type. Better yet we can derive the definition of fold automatically from the type definition. The rigourous theoretical foundations of functional programming allow us to prove these kind of statements.