Define a function
zero?
that expects a single number as an argument, and returns'true
if that number is0
, else returns'false
.let zero? match lambda x. case x of 0 then 'true; y then 'false end in zero?
Define a function
empty?
that expects a sequence of values as an argument (doesn't matter what type of values), and returns'true
if that sequence is the empty sequence[]
, else returns'false
.let empty? match lambda xs. case xs of [] then 'true; _ & _ then 'false end in empty?
The second
case
clause could also just be_ then 'false
.Define a function
tail
that expects a sequence of values as an argument (doesn't matter what type of values), and returns that sequence with the first element (if any) stripped away. (Applyingtail
to the empty sequence[]
can just give us back the empty sequence.)let tail match lambda xs. case xs of [] then []; _ & xs' then xs' end in tail
Define a function
drop
that expects two arguments, in the form (number, sequence), and works like this:drop (0, [10, 20, 30]) # evaluates to [10, 20, 30] drop (1, [10, 20, 30]) # evaluates to [20, 30] drop (2, [10, 20, 30]) # evaluates to [30] drop (3, [10, 20, 30]) # evaluates to [] drop (4, [10, 20, 30]) # evaluates to []
letrec drop match lambda (n, xs). case (n, xs) of (0, _) then xs; (_, []) then []; (_, _ & xs') then drop (n-1, xs') end in drop
What is the relation between
tail
anddrop
?let tail xs = drop (1, xs) in ...
That uses the shorthand explained here, which I will continue to use below.
Define a function
take
that expects two arguments, in the same form asdrop
, but works like this instead:take (0, [10, 20, 30]) # evaluates to [] take (1, [10, 20, 30]) # evaluates to [10] take (2, [10, 20, 30]) # evaluates to [10, 20] take (3, [10, 20, 30]) # evaluates to [10, 20, 30] take (4, [10, 20, 30]) # evaluates to [10, 20, 30]
letrec take (n, xs) = case (n, xs) of (0, _) then []; (_, []) then []; (_, x' & xs') then x' & take (n-1, xs') end in take
Define a function
split
that expects two arguments, in the same form asdrop
andtake
, but this time evaluates to a pair of results. It works like this:split (0, [10, 20, 30]) # evaluates to ([], [10, 20, 30]) split (1, [10, 20, 30]) # evaluates to ([10], [20, 30]) split (2, [10, 20, 30]) # evaluates to ([10, 20], [30]) split (3, [10, 20, 30]) # evaluates to ([10, 20, 30], []) split (4, [10, 20, 30]) # evaluates to ([10, 20, 30], [])
letrec split (n, xs) = case (n, xs) of (0, _) then ([], xs); (_, []) then ([], []); (_, x' & xs') then let (ys, zs) match split (n-1, xs') in (x' & ys, zs) end in split
Write a function
filter
that expects two arguments. The second argument will be a sequencexs
with elements of some type t, for example numbers. The first argument will be a functionp
that itself expects arguments of type t and returns'true
or'false
. Whatfilter
should return is a sequence that contains exactly those members ofxs
for whichp
returned'true
.letrec filter (p, xs) = case xs of [] then []; x' & xs' when p x' then x' & filter (p, xs'); _ & xs' then filter (p, xs') end in filter
The above solution uses pattern guards.
Write a function
partition
that expects two arguments, in the same form asfilter
, but this time evaluates to a pair of results. It works like this:partition (odd?, [11, 12, 13, 14]) # evaluates to ([11, 13], [12, 14]) partition (odd?, [11]) # evaluates to ([11], []) partition (odd?, [12, 14]) # evaluates to ([], [12, 14])
letrec partition (p, xs) = case xs of [] then ([], []); x' & xs' then let (ys, zs) match partition (p, xs') in if p x' then (x' & ys, zs) else (ys, x' & zs) end in partition
Write a function
double
that expects one argument which is a sequence of numbers, and returns a sequence of the same length with the corresponding elements each being twice the value of the original element.letrec double xs = case xs of [] then []; x' & xs' then (2*x') & double xs' end in double
Write a function
map
that generalizesdouble
. This function expects a pair of arguments, the second being a sequencexs
with elements of some type t, for example numbers. The first argument will be a functionf
that itself expects arguments of type t and returns some type t' of result. Whatmap
should return is a sequence of the results, in the same order as the corresponding original elements. The result should be that we could say:letrec map match lambda (f, xs). case xs of [] then []; x' & xs' then (f x') & map (f, xs') end; double match lambda xs. map ((lambda x. 2*x), xs) in ...
Write a function
map2
that generalizesmap
. This function expects a triple of arguments: the first being a functionf
as formap
, and the second and third being two sequences. In this casef
is a function that expects two arguments, one from the first of the sequences and the other from the corresponding position in the other sequence. The result should behave like this:map2 ((lambda (x,y). 10*x + y), [1, 2, 3], [4, 5, 6]) # evaluates to [14, 25, 36]
letrec map2 (f, xs, ys) = case (xs, ys) of ([], _) then []; (_, []) then []; (x' & xs', y' & ys') then (f x' y') & map2 (f, xs', ys') end in map2
Extra credit problems
In class I mentioned a function
&&
which occupied the position between its arguments, rather than coming before them (this is called an "infix" function). The way that it works is that[1, 2, 3] && [4, 5]
evaluates to[1, 2, 3, 4, 5]
. Define this function, making use ofletrec
and the simpler infix operation&
.letrec xs && ys = case xs of [] then ys; x' & xs' then x' & (xs' && ys) end in (&&)
This solution is using a variation of the shorthand explained here. We didn't expect you'd know how to deal with the special syntax of
&&
. You might have just defined this using a regular name, likeappend
.Write a function
unmap2
that is something like the inverse ofmap2
. This function expects two arguments, the second being a sequence of elements of some type t. The first is a functiong
that expects a single argument of type t and returns a pair of results, rather than just one result. We want to collate these results, the first into one sequence, and the second into a different sequence. Thenunmap2
should return those two sequences. Thus if:g z1 # evaluates to (x1, y1) g z2 # evaluates to (x2, y2) g z3 # evaluates to (x3, y3)
Then
unmap2 (g, [z1, z2, z3])
should evaluate to([x1, x2, x3], [y1, y2, y3])
.letrec unmap2 (g, zs) = case zs of [] then ([], []); z' & zs' then let (x, y) match g z'; (xs, ys) match unmap2 (g, zs') in (x & xs, y & ys) end in unmap2
Write a function
takewhile
that expects ap
argument likefilter
, and also a sequence. The result should behave like this:takewhile ((lambda x. x < 10), [1, 2, 20, 4, 40]) # evaluates to [1, 2]
Note that we stop "taking" once we reach
20
, even though there are still later elements in the sequence that are less than10
.letrec takewhile (p, xs) = case xs of [] then []; x' & xs' then if p x' then x' & takewhile (p, xs') else [] end in takewhile
Write a function
dropwhile
that expects ap
argument likefilter
, and also a sequence. The result should behave like this:dropwhile ((lambda x. x < 10), [1, 2, 20, 4, 40]) # evaluates to [20, 4, 40]
Note that we stop "dropping" once we reach
20
, even though there are still later elements in the sequence that are less than10
.letrec dropwhile (p, xs) = case xs of x' & xs' when p x' then dropwhile (p, xs'); _ & _ then xs; [] then [] end in dropwhile
Unlike the previous solution, this one uses pattern guards, merely for variety. (In this solution the last two
case
clauses could also be replaced by the single clause_ then xs
.)Write a function
reverse
that returns the reverse of a sequence. Thus,reverse [1, 2, 3, 4]
should evaluate to[4, 3, 2, 1]
.letrec aux (ys, xs) = case xs of [] then ys; x' & xs' then aux (x' & ys, xs') end; reverse xs = aux ([], xs) in reverse