This assignment departs from the textbook, so there’s nothing to read. I think this content is really cool, but it might be too hard to include in the actual class. And it may especially be too hard for you all since I can’t do a lecture! If so, feel free to skip or just let me know.

From now on, you may use the following *syntactic sugar* for lists that you already saw in the textbook:

```
[list: 1, 2, 3] = link(1, link(2, link(3, empty)))
```

(Pyret converts the former into the latter before running it, so it’s just for ease of writing examples and tests.)

```
[list: ] = empty
```

as well.

## Higher-order functions#

Create a file called `higher-order-functions.arr`

.

### Map#

Recall the function (from the textbook) to double every number in a list:

```
fun my-doubles(l):
cases (List) l:
| empty => empty
| link(f, r) => link(2 * f, my-doubles(l))
end
end
```

This bears a striking resemblence to the function you wrote to add an exclamation mark to every string in a list:

```
fun exclaim(l):
cases (List) l:
| empty => empty
| link(f, r) => link(f + "!", exclaim(l))
end
end
```

In both cases, we recur through a list and apply some function to each element in the list.

Fortunately, we can write what’s called a *higher-order* function: a function that takes another function as one of its arguments! This works just the same as passing any other argument to the function.

- Write the higher-order function
`my-map`

that takes as input a list`l`

and a function`func`

, and produces a list made from applying`func`

to every element in`l`

. (This is called*mapping*the function`func`

across the list`l`

.) Start with:

```
fun my-map(func, l):
...
end
```

Within the body of the function, you’ll be able to call `func`

like any other function.

Rewrite

`my-doubles`

and`exclaim`

using`my-map`

. You will need to write helper functions to use as`func`

in each case. (That is, you’ll need to write a function`double-one`

and`exclaim-one`

that double a single number, and add an exclamation point to a single string, respectively.)You do not need to directly test

`my-map`

: the examples you write for`my-doubles`

and`my-map`

suffice to test it.

### Anonymous functions#

Writing helper functions to use as inputs for `my-doubles`

makes using high-order functions a lot more verbose. Fortunately, we can create functions *anonymously* to use as arguments to our higher-order functions.

An anonymous function looks like this:

```
lam(x): x + 1 end
```

or

```
lam(x, y): x + y end
```

The `lam`

is short for “lambda”, as in lambda calculus. (If you look closely at the Pyret mascot you’ll be able to spot a lambda symbol: λ.)

**Optional:** refactor `my-doubles`

and `exclaim`

from (2.) using anonymous functions.

For example, to add 1 to every element in a list:

```
my-map(lam(x): x + 1 end, [list: 1, 2, 3])
=> [list: 2, 3, 4]
```

### Fold#

Now consider the function `my-sum`

, which adds up all the numbers in a list:

```
fun my-sum(l):
cases (List) l:
| empty => 0
| link(f, r) => f + my-sum(r)
end
end
```

We could write a similar function, `my-multiply`

, to multiply together all the numbers in a list:

```
fun my-multiply(l):
cases (List) l:
| empty => 1
| link(f, r) => f * my-multiply(r)
end
end
```

Let’s think about what’s going on in these functions.

Each function returns some specific value if it sees an empty list. Otherwise, it has a way to combine an element from the list with the result of the recursive call on the rest of the list.

In short, the body of each function looks like this:

```
cases (List) l:
| empty => [base case]
| link(f, r) => [do something with f and the recursive call on r]
end
```

This recursive combination is called a *fold*.

Write the higher-order function

`my-fold`

that takes as input a two-argument “combining” function`func`

, a value`base-value`

and a list`l`

. If`l`

is empty,`my-fold`

evaluates to`base-value`

, otherwise`my-fold`

produces a new value by repeatedly applying`func`

.Use

`my-fold`

to rewrite`my-length`

(finds the length of a list),`my-sum`

and`my-multiply`

. You may use anonymous functions or helper functions.

`map`

and `fold`

are built in to Pyret, and after you implement them yourself you are free to use the built-in versions for future problems and assignments.

## Harder list functions#

Create a file called `lists2.arr`

Write a function

`my-reverse`

that consumes a list`l`

and produces a new list with the same elements in reverse order.Write a function

`my-concat`

that consumes two lists`l-1`

and`l-2`

, and produces a list with all the elements from`l-1`

followed by all the elements from`l-2`

.

*After you implement my-reverse you are welcome to use the built in reverse. After you implement my-concat, you can concatenate lists in Pyret by using the + operator, for example,*

```
[list: 1, 2, 3] + [list: 4, 5]
=> [list: 1, 2, 3, 4, 5]
```

- Write a function
`subsets`

that consumes a list`l`

, and produces a*list of lists*where each list contains the elements of a single subset of`l`

. For example,`subsets`

should produce the following (subject to reordering):

```
subsets([list: ])
=> [list: [list: ]]
subsets([list: 1])
=> [list: [list: 1], [list: ]]
subsets([list: 1, 2])
=> [list: [list: 1, 2], [list: 1], [list: 2], [list: ]]
```

This problem is notoriously tough so please let me know if you’d like a hint.

## Turn in#

Download `higher-order-functions.arr`

and `lists2.arr`

and submit them to gradescope.