(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.
let
let
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 let
will be able to
access the variables x
and y
, which will have the values
3
and 4
, respectively.
let
can 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.
letrec
letrec
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...
lambda
lambda
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
define
d 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 define
s. 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 let
and 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.