Assignment 2: Random Art (160 points)

Due by Monday 4/29 11:59pm

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 and src/RandomArt.hs has skeleton functions with missing bodies that you will fill in,

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

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

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

You can think of this function as repeatedly performing a given operation f on a given value x until the conditional statement in f, whose value is the first item in the returned tuple, is false. The second item in the returned tuple is the input for the next recursive call. Thus, the final value will be (false, <first value for which condition is no longer true>).

(d) 20 points

Fill in the implementation of the function

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

The fixpoint of a function f is a point at which f(x) = x. The expression fixpointL f x 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}
• x_n = x_{n+1}

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.

It is possible for a function to have multiple fixpoints. This function should stop at the first one encountered.

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

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