For this machine problem you'll write lots of functions that deal with lists. Lists represent the simplest possible recursive data type that can hold an arbitrary number of elements, and as such it is often the first type we reach for when prototyping programs. You should learn to use them, and use them well!
As with the last machine problem, claim your repository via the invitation link
on the class homepage and git clone
your starter code.
Next, before continuing, remember to sign the honor pledge in the "package.yaml" file so we know who your submission belongs to.
In "src/MP2a.hs" you will find the declarations for ten function that you need to implement, each prefaced by a comment containing a specification and sample calls/results.
Because the goal here is to practice writing list-processing functions from scratch, you are to avoid using any list processing and higher-order functions defined by the Haskell standard library. List comprehensions are technically legal, but avoid them too if you can (just for now!). You may, however, use arithmetic and character processing functions.
The functions you will implement are listed below, for reference:
cycleN :: Int -> [a] -> [a]
chunksOf :: Int -> [a] -> [[a]]
unzip4 :: [(a,b,c,d)] -> ([a], [b], [c], [d])
intersperse :: a -> [[a]] -> [a]
removeAll :: (Eq a) => [a] -> [a] -> [a]
sublist :: (Int,Int) -> [a] -> ([a],[a])
luhn :: [Int] -> Bool
runLengthEncode :: String -> [(Int,Char)]
runLengthDecode :: [(Int,Char)] -> String
vigenere :: String -> String -> String
John Conway's Game of Life is a well known "game" with a very simple set of rules that can simulate incredibly sophisticated behavior (as sophisticated, in fact, as any computer program). Its setting -- which we'll refer to as the game's "world" -- is a two-dimensional grid of cells, each one either living or dead, and considered to be in contact with its eight neighbors (i.e., orthogonally or diagonally adjacent cells).
Given the state of each cell in the world at time \(t_n\), we can compute the state of each cell at time \(t_{n+1}\) (i.e., one generation later) using the following rules:
The image below depicts a world before and after the rules are applied to a group of cells.
Many living cell patterns have been discovered that result in stable/non-changing shapes and repeatedly oscillating shapes, among other types (see the example patterns in the Game of Life Wikipedia article for some). An interesting fact about the Game of Life is that there is no algorithm which can reliably predict whether or not a given pattern will appear in the world given some starting state (this is related to the halting problem, covered in CS 330).
Since each world state (after the initial state) is a pure function of the preceding one, and the game world can be easily modeled using lists, implementing the Game of Life makes for another fun list processing exercise!
We will represent the game world using the type: ((Int,Int), [[Bool]])
. I.e.,
as a tuple where the first element is a tuple of two integers \((w,h)\)
representing the width and height of the world, and the second element is a list
of lists of Booleans representing the 2D grid, where each sublist of length
\(w\) represents the cells in a row of the world, with \(h\) sublists total.
A barren (i.e., containing only dead cells) world can be created with the following function, which takes as input the width and height:
makeWorld :: (Int,Int) -> ((Int,Int), [[Bool]])
makeWorld dims@(w,h) = (dims, replicate h (replicate w False))
In "src/MP2b.hs" you will find declarations for functions you must complete to implement the Game of Life. The first two functions compute the number of live neighbors of a cell and the next world state:
liveNeighbors :: ((Int,Int), [[Bool]]) -- world
-> (Int,Int) -- cell
-> Int -- number of living neighbors
nextWorld :: ((Int,Int), [[Bool]]) -- world
-> ((Int,Int), [[Bool]]) -- next world (one generation later)
To animate the game, you will need to write a function that returns a picture for a given world state:
drawWorld :: ((Int,Int), [[Bool]]) -- world
-> Picture -- graphical depiction of world
The picture of the world should be scaled to fit the fixed size 500x500 output window, with cells depicted as squares in a 2D grid, shaded black/white (or whatever color scheme you choose, provided it has reasonable contrast) to indicate their status. Here's a screenshot of a running game:
To do your drawing, you will likely need to use the following functions from the
Gloss library: color
, rectangleSolid
, scale
, translate
, pictures
.
Consult the Gloss
documentation
for details. The window coordinate system has (0,0) centered in the window, and
you will need to map your cells onto that coordinate system. To keep things
consistent, we ask that you map cells as shown below (the blue lines depict the
window coordinate system, while the red lines delineate a 5x5 cell grid -- your
implementation should work for grids of arbitrary size up to 50x50).
The easiest way to draw your world is to draw unit (1x1) squares for each cell starting at (0,0), then translate and scale the entire resulting picture to fit inside the window. The following code, for instance, produces the picture below it:
let w = 500 -- screen width
h = 500 -- screen height
n = 3 -- number of squares
sq = color black (rectangleSolid 1 1) -- unit square
in scale (w/n) (h/n) $
translate (-n/2 + 0.5) (-n/2 + 0.5) $
pictures [translate i i sq | i <- [0..n-1]]
Finally, you will implement a function that processes events in the window affecting the world:
handleEvents :: Event -- event (e.g., mouse button press)
-> ((Int,Int), [[Bool]]) -- world
-> ((Int,Int), [[Bool]]) -- next world (after processing event)
We provide a starter definition for the handleEvents
function for you,
shown here:
handleEvents :: Event -> ((Int,Int), [[Bool]]) -> ((Int,Int), [[Bool]])
handleEvents
(EventKey (MouseButton LeftButton) Up _ (mx,my))
world = undefined
handleEvents _ world = world
The only event we're interested in is the left mouse button (or trackpad) click.
When the button is released, this function will be called with the event for
which we include a pattern match. The window coordinates where the click
occurred (mx,my)
are found in the event, which you must map onto your cell
grid. Clicking on a cell forces it to be alive in the resulting world (the rest
of the world is unchanged).
When you're ready to test your animation and/or event handling code, run stack
exec mp2
after a successful build. If you wish, you may tweak the starting
world state specified in "app/Main.hs" (it defaults to starting with a barren
landscape of 25x25 cells).
We include test functions in "test/MP2aSpec.hs" and "test/MP2bSpec.hs" for you,
which you can run with the stack test
command. The output of this command will
give you a full report on passing/failing functions.
Note that we only define working tests for the functions in part A. It isn't
required, but we strongly encourage you to write your own tests for
liveNeighbors
, nextWorld
, and any other top-level helper functions that you
write for part B. Even better, spec out your functions with tests before
starting to implement them for the satisfaction of watching test failures turn
into test successes!
Each function in part A is worth 4 points. The liveNeighbors
and nextWorld
functions are worth 8 points each, and functioning drawing/animation and
event handling are worth 16 points. The assignment is worth a maximum of
\(4\times10
+ 2 \times 8 + 16 = 72\) points.
First, make sure you correctly signed and committed the "package.yaml" file. We won't be able to easily map your repository to your name if you don't!
To submit your work, simply commit all changes and push to your GitHub repository.