assignment1

Define a function zero? that expects a single number as an argument, and returns 'true if that number is 0, else returns 'false. Your solution should have a form something like this:
```
let
  zero? match lambda x. FILL_IN_THIS_PART
in zero?
```
You can use the if...then...else construction if you like, but it will make it easier to generalize to later problems if you use the case EXPRESSION of PATTERN1 then RESULT1; PATTERN2 then RESULT2; ... end construction instead.
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. Here your solution should have a form something like this:
```
let
  empty? match lambda xs. case xs of
                             FILL_IN_THIS_PART
                          end
in empty?
```
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.)

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 []

Your solution should have a form something like this:

letrec
  drop match lambda (n, xs). FILL_IN_THIS_PART
in drop

What is the relation between tail and drop?

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]

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], [])

Here's a way to answer this problem making use of your answers to previous questions:

letrec
  drop match ... ; # as in problem 4
  take match ... ; # as in problem 5
  split match lambda (n, xs). let
                                ys = take (n, xs);
                                zs = drop (n, xs)
                              in (ys, zs)
in split

However, we want you to instead write this function from scratch. The method displayed above would traverse the sequence (at least, its first n members) twice. Can you do it in a way that only traverses (that part of the) sequence once?

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. For example, helping ourself to a function odd? that works as you'd expect:
```
filter (odd?, [11, 12, 13, 14])  # evaluates to [11, 13]
filter (odd?, [11])              # evaluates to [11]
filter (odd?, [12, 14])          # evaluates to []
```

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])

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. For example:
```
double [10, 20, 30]  # evaluates to [20, 40, 60]
double []            # evaluates to []
```
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). FILL_IN_THIS_PART;
  double match lambda xs. map ((lambda x. 2*x), xs)
in ...
```
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]
```

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 &.
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]).
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.
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.
Write a function reverse that returns the reverse of a sequence. Thus, reverse [1, 2, 3, 4] should evaluate to [4, 3, 2, 1].