## Description

Overview

The objective of this assignment is for you to have fun learning

about recursion, recursive datatypes, and make some pretty

cool pictures. All the problems require relatively little

code: somewhere between 2 to 10 lines. If any function requires

more than that, you should rethink your solution.

The assignment is in the files:

1. [src/TailRecursion.hs](/src/TailRecursion.hs) and

[src/RandomArt.hs](/src/RandomArt.hs) have skeleton

functions with missing bodies for you to fill in,

2. [tests/Test.hs](/tests/Test.hs) has some sample tests

and a test harness for you to check your

solutions before submitting.

You should only need to modify the parts of the files which say:

“`haskell

error “TBD:…”

“`

with suitable Haskell implementations.

Assignment Testing and Evaluation

All the points, will be awarded automatically, by

**evaluating your functions against a given test suite**.

[Tests.hs](/tests/Test.hs) contains a very small suite

of tests which should give you a flavor of the sorts of tests

your assignment will be graded against.

When you run

“`shell

$ make test

“`

Your last lines should have

“`

All N tests passed (…)

OVERALL SCORE = … / …

“`

**or**

“`

K out of N tests failed

OVERALL SCORE = … / …

“`

**If your output does not have one of the above your code will receive a zero**

If, for some problem, you cannot get the code to compile,

leave it as in the starter code (with `error …`), with your partial

solution enclosed below as a comment.

The other lines will give you a readout for each test.

You are encouraged to try to understand the testing code,

but you will not be graded on this.

Submission Instructions

Submit your code via the HW-2 assignment on Gradescope.

You must submit a single zip file containing a single directory with your repository inside.

A simple way to create this zip file is:

– Run `git push` to push your local changes to your private fork of the assignment repository

– Navigate to your private fork on github and download source code as a zip

Please *do not* include the `.stack-work` folder into the submission.

**Note:** Upon submission, Gradescope will only test your code on the *small public test suite*,

so it will show maximum 27/160 points.

After the deadline, we will regrade your submission on the full private test suite

and you will get your full points.

Problem 1: Tail Recursion

We say that a function is *tail recursive*

if every recursive call is a [tail call](https://wiki.haskell.org/Tail_recursion)

whose value is immediately returned by the function.

(a) 15 points

Without using any built-in functions, write a

*tail-recursive* function

“`haskell

assoc :: Int -> String -> [(String, Int)] -> Int

“`

such that

“`haskell

assoc def key [(k1,v1), (k2,v2), (k3,v3);…])

“`

searches the list for the first i such that `ki` = `key`.

If such a ki is found, then vi is returned.

Otherwise, if no such ki exists in the list,

the default value `def` is returned.

Once you have implemented the function, you

should get the following behavior:

“`haskell

ghci> assoc 0 “william” [(“ranjit”, 85), (“william”,23), (“moose”,44)])

23

ghci> assoc 0 “bob” [(“ranjit”,85), (“william”,23), (“moose”,44)]

0

“`

(b) 15 points

Use the library function `elem` to **modify the skeleton** for

`removeDuplicates` to obtain a function of type

“`haskell

removeDuplicates :: [Int] -> [Int]

“`

such that `removeDuplicates xs` returns the list

of elements of `xs` with the duplicates, i.e.

second, third, etc. occurrences, removed, and

where the remaining elements appear in the same

order as in `xs`.

Once you have implemented the function, you

should get the following behavior:

“`haskell

ghci> removeDuplicates [1,6,2,4,12,2,13,12,6,9,13]

[1,6,2,4,12,13,9]

“`

(c) 20 points

Without using any built-in functions, write a

tail-recursive function:

“`haskell

wwhile :: (a -> (Bool, a)) -> a -> a

“`

such that `wwhile f x` returns `x’` where there exist values

`v_0`,…,`v_n` such that

– `x` is equal to `v_0`

– `x’` is equal to `v_n`

– for each `i` between `0` and `n-2`, we have `f v_i` equals `(true, v_i+1)`

– `f v_n-1` equals `(false, v_n)`.

Your function should be tail recursive.

Once you have implemented the function,

you should get the following behavior:

“`haskell

ghci> let f x = let xx = x * x * x in (xx < 100, xx) in wwhile f 2

512

“`

(d) 20 points

Fill in the implementation of the function

“`haskell

fixpointL :: (Int -> Int) -> Int -> [Int]

“`

The expression `fixpointL f x0` should return the list

`[x_0, x_1, x_2, x_3, … , x_n]` where

* `x = x_0`

* `f x_0 = x_1, f x_1 = x_2, f x_2 = x_3, … f x_n = x_{n+1}`

* `xn = x_{n+1}`

When you are done, you should see the following behavior:

“`haskell

>>> fixpointL collatz 1

[1]

>>> fixpointL collatz 2

[2,1]

>>> fixpointL collatz 3

[3,10,5,16,8,4,2,1]

>>> fixpointL collatz 4

[4,2,1]

>>> fixpointL collatz 5

[5,16,8,4,2,1]

>>> fixpointL g 0

[0, 1000000, 540302, 857553, 654289,

793480,701369,763959,722102,750418,

731403,744238,735604,741425,737506,

740147,738369,739567,738760,739304,

738937,739184,739018,739130,739054,

739106,739071,739094,739079,739089,

739082,739087,739083,739086,739084,

739085]

“`

The last one is because `cos 0.739085` is approximately `0.739085`.

(e) 20 points

Without using any built-in functions,

**modify the skeleton** for `fixpointW`

to obtain a function

“`haskell

fixpointW :: (Int -> Int) -> Int -> Int

“`

such that `fixpointW f x` returns

**the last element** of the list

returned by `fixpointL f x`.

Once you have implemented the

function, you should get the

following behavior:

“`haskell

ghci> fixpointW collatz 1

1

ghci> fixpointW collatz 2

1

ghci> fixpointW collatz 3

1

ghci> fixpointW collatz 4

1

ghci> fixpointW collatz 5

1

ghci> fixpointW g 0

739085

“`

Problem 2: Random Art

At the end of this assignment, you should be able to produce

pictures like those shown below. To do so, we shall:

1) devise a grammar for a certain class of expressions,

2) design a Haskell datatype whose values correspond to these expressions,

3) write code to evaluate the expressions, and then

4) write a function that randomly generates such expressions and plots them — thereby

producing random psychedelic art.

**Color Images**

![](/img/color1.jpg)\ ![](/img/color2.jpg)\ ![](/img/color3.jpg)

**Gray Scale Images**

![](/img/art_g_sample.jpg)\ ![](/img/gray2.jpg)\ ![](/img/gray3.jpg)

The expressions are described by the grammar:

“`

e ::= x

| y

| sin (pi*e)

| cos (pi*e)

| ((e + e)/2)

| e * e

| (e<e ? e : e)

“`

where pi is the constant we all learned in grade school, rounded so that it

fits in a Dobule. All functions are over the variables

x,y, which are guaranteed to produce a value in the range [-1,1] when x and

y are in that range. We can represent expressions of this grammar

using values of the following datatype:

“`haskell

data Expr

= VarX

| VarY

| Sine Expr

| Cosine Expr

| Average Expr Expr

| Times Expr Expr

| Thresh Expr Expr Expr Expr

“`

(a) 15 points

First, write a function

“`haskell

exprToString :: Expr -> String

“`

to enable the printing of expressions. Once you have implemented

the function, you should get the following behavior:

“`haskell

ghci> exprToString sampleExpr0

“sin(pi*((x+y)/2))”

ghci> exprToString sampleExpr1

“(x<y?x:sin(pi*x)*cos(pi*((x+y)/2)))”

ghci> exprToString sampleExpr2

“(x<y?sin(pi*x):cos(pi*y))”

“`

(b) 15 points

Next, write a function

“`haskell

eval :: Double -> Double -> Expr -> Double

“`

such that `eval x y e` returns the result of evaluating

the expression `e` at the point `(x, y)`. That is, evaluating

the result of `e` when `VarX` has the value `x` and `VarY` has

the value `y`.

* You should use functions from Prelude like

`sin`, `cos`, and `pi` to build your evaluator.

* Recall that `Sine VarX` corresponds to

the expression `sin(pi*x)`

Once you have implemented the function,

you should get the following behavior:

“`haskell

ghci> eval 0.5 (-0.5) sampleExpr0

0.0

ghci> eval 0.3 0.3 sampleExpr0

0.8090169943749475

ghci> eval 0.5 0.2 sampleExpr2

0.8090169943749475

“`

If you execute

“`haskell

ghci> emitGray “sample.png” 150 sampleExpr3

“`

(or just run `make` if your `ghci` is not working)

you should get a file `img/sample.png` in

your working directory. To receive full

credit, this image must look like the

leftmost grayscale image displayed above.

Note that this requires your `eval` to

work correctly. A message `Assert failure…` is an

indication that your `eval` is returning a value

outside the valid range `[-1.0,1.0]`.

(c) 20 points

Next, consider the skeleton function:

“`haskell

build :: Int -> Expr

build 0

| r < 5 = VarX

| otherwise = VarY

where

r = rand 10

build d = error “TBD:build”

“`

Change and extend the function to generate interesting expressions `Expr`.

– A call to `rand n` will return a random number between (0..n-1)

Use this function to randomly select operators when

composing subexpressions to build up larger expressions.

For example, in the above, at depth `0` we generate the expressions

`VarX` and `VarY` with equal probability.

– `depth` is the nesting depth: a random expression of depth `d` is

built by randomly composing sub-expressions of depth `d-1` and the

only expressions of depth `0` are `VarX` and `VarY`.

With this in place you can generate random art using the functions

“`haskell

emitRandomGray :: Int -> (Int, Int) -> IO ()

emitRandomColor :: Int -> (Int, Int) -> IO ()

“`

For example, running

“`haskell

ghci> emitRandomGray 150 (3, 12)

“`

will generate a gray image `img/grag_150_3_12.png` by:

randomly generating an `Expr`

1. Whose `depth` is equal to `3`,

2. Using the **seed** value of `12`.

Re-running the code with the same parameters will yield

the same image. (But different `seed` values will yield

different images).

The gray scale image, is built by mapping out a single

randomly generated expression over the plane.

The color image (generated by `emitRandomColor`) is built

by generating three `Expr` for the Red, Green and Blue

intensities of each pixel.

Play around with how you generate the expressions, using the

tips below.

– Depths of 8-12 produce interesting pictures, but play around!

– Make sure your expressions don’t get *cut-off* early with

`VarX`, `VarY` as small expressions give simple pictures.

– Play around to bias the generation towards more interesting operators.

Save the parameters (i.e. the depth and the seeds)

for your favorite three color images in the bodies of

`c1`, `c2`, `c3` respectively, and favorite three gray

images in `g1`, `g2` , `g3`.

(d) 20 points

Finally, add **two** new operators to the grammar, i.e. to the

datatype, by introducing two new datatype constructors, and adding the

corresponding cases to `exprToString`, `eval`, and `build`.

The only requirements are that the operators must return

values in the range `[-1.0,1.0]` if their arguments (i.e. `VarX` and `VarY`)

are in that range, and that one of the operators take **three**

arguments, i.e. one of the datatype constructors is of the form:

`Ctor Expr Expr Expr`

You can include images generated with these new operators

when choosing your favorite images for part (c).