$24
Assignment 2: Random Art Solution
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 ranging from 2 to 10 lines. If any function requires
more than that, you can be sure that you need to rethink
your solution.
The assignment is in the files:
1. [src/TailRecursion.hs](/src/TailRecursion.hs) and
[src/RandomArt.hs](/src/RandomArt.hs) has skeleton
functions with missing bodies that you will fill in,
2. [tests/Test.hs](/tests/Test.hs) has some sample tests,
and testing code that you will use to check your
assignments 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
Most of 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 gives you a flavor of of these tests.
When you run
```shell
$ stack 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 is with the `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
To submit your code,
1) Push your changes to GitLab first.
2) Submit your commit SHA to canvas.
You can find it by typing "git log" on the same folder
as your homework
or, you can find it by clicking on commit tab in GitLab
## 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 procedure.
(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 of the kind shown below. To do so, we shall devise a
grammar for a certain class of expressions, design a Haskell
datatype whose values correspond to such expressions, write
code to evaluate the expressions, and then write a function
that randomly generates such expressions and plots them thus
producing random psychedelic art.
**Color Images**
\ \ 
**Gray Scale Images**
\ \ 
(a) 15 points
The expressions described by the grammar:
```
e ::= x
| y
| sin (pi*e)
| cos (pi*e)
| ((e + e)/2)
| e * e
| (e<e ? e : e)
```
where pi stands for the constant 3.142, all functions 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
```
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 library functions like,
`sin`, and `cos` 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 a a maximum nesting dept; 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).
