Assignment 2: Random Art (Points: 27 public / 160 private)

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 and src/RandomArt.hs have skeleton functions with missing bodies for you to fill in,

2. 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:

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

$ 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. Connect your GitHub account to Gradescope and select your repo. If you're in a group, don't forget to add your partner to the submission!

Detailed instructions on how to submit your code directly from the Git repo can be found on Piazza.

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 whose value is immediately returned by the function.

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

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.

Your helper must be tail-recursive.

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]
[1,6,2,4,12,13,9]

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

In other words, f returns a pair where the first element indicates whether the loop should keep going, and the second element is the updated value.

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
512

(d) 20 points

Fill in the implementation of the function

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

A fixpoint of a function f is a value x such that f x == x. 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}

In other words, the list contains the results of calling f repeatedly on the preceding value, until a fixpoint x_n is reached.

This function does not need to be tail-recursive.

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

>>> 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 of 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 (i.e. the fixpoint x_n).

Once you have implemented the function, you should get the following behavior:

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

(e1 < e2 ? e3 : e4) means "if e1 is less than e2, then e3, else e4". The ? and : syntax is the same as the C-style ternary conditional operator.

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:

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

exprToString :: Expr -> String

to enable the printing of expressions. Once you have implemented the function, you should get the following behavior:

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

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:

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

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
  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 maximum nesting depth. A random expression of depth d is built by randomly composing sub-expressions of depth d-1. 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/gray_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.

If your color images look gray, ensure you are using make test and not stack test.

(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 (but are not required to) include images generated with these new operators when choosing your favorite images for part (c).