1. Define a function zero? that expects a single number as an argument, and returns 'true if that number is 0, else returns 'false.

let
zero? match lambda x. case x of
0 then 'true;
y then 'false
end
in zero?

2. 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.

3. 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. (Applying tail 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

4. 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 and drop?

let
tail xs = drop (1, xs)
in ...


That uses the shorthand explained here, which I will continue to use below.

5. Define a function take that expects two arguments, in the same form as drop, 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

6. Define a function split that expects two arguments, in the same form as drop and take, 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

7. Write a function filter that expects two arguments. The second argument will be a sequence xs with elements of some type t, for example numbers. The first argument will be a function p that itself expects arguments of type t and returns 'true or 'false. What filter should return is a sequence that contains exactly those members of xs for which p 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.

8. Write a function partition that expects two arguments, in the same form as filter, 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

9. 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

10. Write a function map that generalizes double. This function expects a pair of arguments, the second being a sequence xs with elements of some type t, for example numbers. The first argument will be a function f that itself expects arguments of type t and returns some type t' of result. What map 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 ...

11. Write a function map2 that generalizes map. This function expects a triple of arguments: the first being a function f as for map, and the second and third being two sequences. In this case f 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 of letrec 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, like append.

• Write a function unmap2 that is something like the inverse of map2. This function expects two arguments, the second being a sequence of elements of some type t. The first is a function g 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. Then unmap2 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 a p argument like filter, 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 than 10.

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 a p argument like filter, 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 than 10.

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.813586413860321, "perplexity": 4243.434298615609}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-17/segments/1492917122621.35/warc/CC-MAIN-20170423031202-00328-ip-10-145-167-34.ec2.internal.warc.gz"}