change function (Exercise 1.3) to work
for any set of coins (or notes) for any decimal currency. The coin
values should be passed to change as a variable number of
arguments which are the coin values in units (e.g., a quarter would be
represented as 25) in any order. The first arg is still the number to
make change for.
# change :: num X num ... -> [num]
proc change {n args} {...}
change 75 25 10 5 1
=> 3 0 0 0
change 75 10 25 1 5
=> 3 0 0 0
change 75 50 25 10 5 1
=> 1 1 0 0 0
iota function (Exercise 1.4) to take an
optional second argument which is an increment to separate the integer
values. The default increment is 1. iota always returns
a list whose length is equal to its first argument.
# iota :: num X num ... -> [num]
proc iota {n {inc 1}} {...}
iota 10
=> 0 1 2 3 4 5 6 7 8 9
iota 10 3
=> 0 3 6 9 12 15 18 21 24 27
megatcl>iota 3 2
0 2 4
megatcl>iota 3 4
0 4 8
megatcl>
map, a function that abstracts
incrlist (Exercise 1.5) and strlenlist
(Exercise 1.6). map takes two arguments: f, a restricted
class of Tcl script; and L, a list. map applies
f to each element of L, returning a list of the results.
The result list will always be the same length as L.
The types of L and the result need not match. This means
that map is conceptually polymorphic. Of
course, since all Tcl values are strings, you could also say that the
two lists are always lists of strings, but this is often less useful
than thinking about the semantics of the strings.
f needs to be a Tcl script of one argument.
# map :: (alpha -> beta) X [alpha] -> [beta]
proc map {f L} {...}
map I [iota 10]
=> 0 1 2 3 4 5 6 7 8 9
map {K 1} [iota 10]
=> 1 1 1 1 1 1 1 1 1 1
map {expr 10 +} [iota 10]
=> 10 11 12 13 14 15 16 17 18 19
incrlist and strlenlist in terms
of map.
foldl, a function that abstracts
sumlist (Exercise 1.7), multlist (Exercise
1.8) and catlist (Exercise 1.9). foldl
takes three arguments:
foldl applies f pairwise to all the elements of
L, left associatively. It's as if f were inserted
between each element of L, parenthesized left-associatively:
proc + {a b} {expr $a + $b}
foldl + 0 [list 1 2 3 4]
== (((1+2)+3)+4)
=> 10
Why is the identity element necessary? Consider the case of a list of
length one:
foldl + 0 [list 1] == (..+1)The problem is, we don't have two values for our binary
+
operator. The identity element gives us a value to use at the left
end of the expression; it needs to be the identity for f so
that it doesn't otherwise change the result:
foldl + 0 [list 1 2 3 4]
== ((((0+1)+2)+3)+4)
=> 10
proc * {a b} {expr $a * $b}
foldl * 1 [list 1 2 3 4]
== ((((1*1)*2)*3)*4)
=> 24
If L is a list of integers, then f should be a function of two integers; it can return any type of value. If L is a list of strings, then f should be a function of two strings; it can return any type of value. If L is a list of variable names, then f should be a function of two variable names; it can return any type of value.
Another way of describing f is to say that if L is a
list of elements of type alpha, then f must be a
function of type (alpha X alpha ->
beta). We don't care about the type of f's return value
except to say that it may (but is not required to be) different
from alpha.
# foldl :: (alpha X alpha -> beta) X beta X [alpha] -> beta
proc foldl {f id L} {...}
Do you understand why foldl needs a parameter for the
identity element?
sumlist, multlist and
catlist in terms of foldl.
zip, which takes three arguments:
zip applies f pairwise to corresponding elements
of a and b, returning a list of the results.
If a is a list of integers, and b is a list of strings, then f should be a function that takes an integer as its first argument and a string as its second argument. It can return any type of value.
# zip :: (alpha X beta -> gamma) X [alpha] X [beta] -> [gamma]
proc zip {f a b} {...}
proc + {a b} {expr $a + $b}
zip + [iota 10] [iota 10]
=> 0 2 4 6 8 10 12 14 16 18
zip list [list A B C D] [list 1 2 3 4]
=> {A 1} {B 2} {C 3} {D 4}
vardefault, which takes two arguments,
the name of a variable, and a default value. If the variable is
defined in the calling scope, vardefault returns
the variable's value. If it is not defined,
vardefault returns the default value.
proc vardefault {var default} {...}
set x 45
vardefault x 0
=> 45
proc foo {} {
vardefault x 0
}
foo
=> 0
To write this function, you'll need to use upvar to
achieve call by name, and you'll need a way to test whether or not a
variable is defined (use info exists).