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**
\ \ 
**Gray Scale Images**
\ \ 
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).
