Functional Programming in Racket and the map$/$reduce paradigm.

$1.$ Implement the function $($lookup var env$)$ where var is a variable, i$.$e$.$ a symbol, and env is an

environment. An environment is a list of bindings and a binding a list of length two where the

first element is a variable and the second is the value bound to the variable. The function

lookup returns the value bound to a given variable in the specified environment. If the variable

is not found in the environment, then use the Racket function error to throw an error. E$.$G$.$

$($lookup $$y $(($x $2)($y $3)))$ returns $3.$

$2.$ The following function is given a list and returns a new list whose elements are those in the

input but in reverse order. E$.$G$.($rev $(123))=(321)$

$($define $($rev l$)$

$($if $($null$?$ l$)$

null

$($append $($rev $($rest l$))($cons $($first l$)$ null$))))$

The function rev uses the function append which appends the list y after the list x$.$

$($define $($append x y$)$

$($if $($null$?$ x$)$

y

$($cons $($first x$)($append $($rest x$)$ y$))))$

The function rev takes $\backslash$Theta $($n$2$

$)$ time where n is the length of the list $[$why$?].$ Tail recursion can be

used to obtain a linear time algorithm. Implement reverse using tail recursion. See the example

from the lecture on functional programming. Hint: you will need a helper function that takes an

additional argument and is more general than reverse.

$3.$ Implement the function $($map f L$)$ which takes two arguments: $1)$ f a function of a single variable

and $2)$ L a list of elements in the domain of f$.$ If L $=($x$1$ x$2...$ xn$),$ the output of the function is the

list $(($f x$1)($f x$2)...($f xn$)).$ E$.$G$.$ assuming the function sqr$,$ defined by $($define $($sqr x$)(*$ x x$)),$ the

result of $($map sqr $(1234))$ is $(14916).$ First try this example using the Racket function map

and then see that you get the same result using your function. Note that Racket$$s map function

is more general in that it allows functions of more than one variable when additional lists are

provided.

$4.$ Implement the function $($reduce f init L$)$ which takes three arguments: $1)$ f a function of two

variables and $2)$ L a list of elements in the domain of f$,$ and $3)$ init the value to be returned when

L $=().$ Reduce is the same as the Racket function foldr. E$.$G$.($reduce $+0(1234))$ is $(+1$

$($reduce $+0(234))=(+1(+2(+3(+40)))).$ First try the Racket function foldr, i$.$e$.($foldr $+0(1$

$234))$ and then see that your implementation obtains the same result. Try the other examples

from the functional programming in Racket lecture.

$5.$ Use map and reduce to solve the following problem: count the number of negative numbers in

a list. Try to make your code as general as possible. Can you use your code to count the

number of elements of a list that satisfy a given predicate?

$6.$ Given a set of $1\backslash$times $2$ dominoes, write a Racket function to generate all of the different ways to to

tile a $2\backslash$times n rectangle placing a single domino vertically $(2\backslash$times $1)$ or stacking two dominoes

horizontally? For example, for n$=3,$ there are $3$ ways.

Think recursively: What are the base cases and how many do you need? How do you solve the

$2\backslash$times n using solutions to smaller problems?

$$ Represent tilings with $$V$$ for one vertical tile and $$HH$$ for two stacked

horizontal tiles. In the above $2\backslash$times $3$ example, the three tilings are represented by

the strings $$VVV$,$VHH$,$ and $$HHV$.$ Note that all three solutions have length

$3.$

$$ Your function, $($GenDominoes n$)$ should return a list of strings, one for each

possible tiling. In the above example, $($GenDominoes $3)$ should return the list

$($VVV$$VHH$$HHV$)$

$$ Your function should recursively generate all solutions of size n$-1$ and

concatenate a $$V$$ in front of each of them, and recursively generate all

solutions of size n$-2$ and concatenate a $$HH$$ in front of them. Use map to

perform the concatenation and use append to combine the solutions. What is

the base case of your recursion?

$$ You should use Racket$$s built in string concatenation function: string$-$append.

See the Racket documentation for details on string$-$append. Make sure you try

it out before you write a function that uses it$.$