Assignment 2: Random Art Solution




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:


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


$ stack test


Your last lines should have


All N tests passed (…)





K out of N tests failed



**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](

whose value is immediately

returned by the procedure.

(a) 15 points

Without using any built-in functions, write a

*tail-recursive* function


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


such that


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:


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


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



(b) 15 points

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

`removeDuplicates` to obtain a function of type


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:


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



(c) 20 points

Without using any built-in functions, write a

tail-recursive function:


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:


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



(d) 20 points

Fill in the implementation of the function


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:


>>> fixpointL collatz 1


>>> fixpointL collatz 2


>>> fixpointL collatz 3


>>> fixpointL collatz 4


>>> fixpointL collatz 5


>>> fixpointL g 0

[0, 1000000, 540302, 857553, 654289,









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


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:


ghci> fixpointW collatz 1


ghci> fixpointW collatz 2


ghci> fixpointW collatz 3


ghci> fixpointW collatz 4


ghci> fixpointW collatz 5


ghci> fixpointW g 0



## 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**

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

**Gray Scale Images**

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

(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:


data Expr

= VarX

| VarY

| Sine Expr

| Cosine Expr

| Average Expr Expr

| Times Expr Expr

| Thresh Expr Expr Expr Expr


First, write a function


exprToString :: Expr -> String


to enable the printing of expressions. Once you have implemented

the function, you should get the following behavior:


ghci> exprToString sampleExpr0


ghci> exprToString sampleExpr1


ghci> exprToString sampleExpr2



(b) 15 points

Next, write a function


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:


ghci> eval 0.5 (-0.5) sampleExpr0


ghci> eval 0.3 0.3 sampleExpr0


ghci> eval 0.5 0.2 sampleExpr2



If you execute


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:


build :: Int -> Expr

build 0

| r < 5 = VarX

| otherwise = VarY


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


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

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


For example, running


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).

error: Content is protected !!