Assignment 1

Set Up

Install the Haskell stack tool following the instructions here, and clone the starter code repo.

The assignment1 folder is a stack project (you don’t need to create your own), with the following directory structure.

.
├── LICENSE
├── Setup.hs
├── app -- Main executable
│   └── Main.hs
├── assignment1.cabal -- Configuration
├── src -- Library modules
│   ├── LSystem.hs
│   ├── ListProcess.hs
│   └── Primes.hs
├── stack.yaml -- Autogenerated
└── test -- Tests for the library modules
    ├── LSystemSpec.hs
    ├── ListProcessSpec.hs
    ├── PrimesSpec.hs
    └── Spec.hs

All three problems below should be solved by editing the corresponding files in /src/. The starter code for Problem 3 builds an executable and asks you to edit 1 line in /app/Main.hs, but you should not need to understand any of the code outside /src/ to complete the assignment.

It is configured (in the file assignment1.cabal) so that

stack build

builds the program in /app/Main.hs (the executable from Problem 3),

stack test

runs the tests in /test/ (there are tests for all parts of the assignment, and making them pass without any trickiness should be sufficient to complete the assignment), and

stack ghci

loads the code into the REPL (interpreter). We recommend you write your solutions while testing them using the REPL, where you can reload updated code from the various Haskell files by running the following in ghci after saving.

ghci> :r

There are two redundant indications for where you should edit the starter code. First, each definition that requires editing will be marked by TODO in the corresponding comment. Second, the code to be written will be replaced with the Haskell undefined, a value of any type which allows compilation to complete but when evaluated crashes the program.

Problems

Note that all the material for these problems will be covered by the end of lecture Tuesday, Jan 14.

Problem 1 - Primes (/src/Primes.hs)

As you may know, a prime number is a natural number greater than 1 with no divisors other than 1 and itself. We are going to ask you to implement a few functions related to prime numbers.

  1. Write a function isPrime :: Int -> Bool that returns whether a positive integer is prime. Hint: somewhere in there you’ll want to filter some [Int].

  2. Using isPrime, define an infinite list primes :: [Int] which consists of all prime numbers. Hint: filter.

  3. Look into the Sieve of Eratosthenes algorithm for computing prime numbers. The intro on Wikipedia gives a great description. Define the list of positive primes – call it primesSieve :: [Int] – using an implementation of the Sieve of Eratosthenes.

    It will help to write a helper sieve :: [Int] -> [Int] where the first element of the argument to sieve is assumed to be prime. Once again, filter is your friend.

Problem 2 - List Processing (/src/ListProcess.hs)

In class we saw various list processing functions. This problem asks you to puzzle through writing map and filter in terms of foldr.

  1. Implement the map function using a fold. Your solution should look like the following for some expressions g and acc. Figuring out the types these expressions should take is a good way to begin, as always.

  2. Implement the filter function using a fold. Your solution should look like the following for some expressions g and acc.

  3. (Optional Challenge) Implement foldl using foldr. Make sure your implementation works on infinite lists. Can you write foldr using foldl, with the same restriction?

Problem 3 - L-systems (/src/LSystem.hs)

This problem asks you to extend a module representing L-systems, a type of formal grammar. From Wikipedia, “An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial ‘axiom’ string from which to begin construction, and a mechanism for translating the generated strings into geometric structures.” Reading the first example on the Wikipedia page is a good way to understand what this looks like.

The starter code defines a type Action, whose constructors represent the symbols of our language. It then goes on to implement one way of defining rewrite rules, and asks you to complete a somewhat more complex but largely similar implementation. Working through /src/LSystem.hs should be enough for you to figure out what the implementation does and how to write the new one. This is partly an exercise in reading code. Hoogle will be your friend, for looking up type signatures and documentation. You can also always check the type signatures of functions in the REPL.

Finally, the starter code handles translating the L-system you define into a diagram. Each of the Action symbols corresponds to an action of a “turtle” on the screen. Draw draws a line moving forward, Move simply moves forward, RTurn and LTurn turn the turtle by an angle (specified later), Mark marks the current position and orientation and Revert returns to the previous mark. Finally, Constant 0, Constant 1, etc. allow us to have other symbols in our grammar that are not interpreted (i.e. ignored) by our turtle artist.

The code for generating the diagram is in /app/Main.hs, which is compiled by the stack build command into an executable. It should already work with the starter code as is (using the completed implementation of rewrites in the LSystem module), and commenting out the last line in the file with it’s replacement after completing this problem will change the diagram displayed to that defined in the second rewrite implementation.

The following command runs the exectuable draw, outputing a diagram for an LSystem after a given number of iterations (try ~5, a high number of iterations can take a long time to render), and with a given turn angle.

stack exec -- draw -o OUTPUTFILE.png -w 1000 -h 1000 <NITER> <ANGLE>

Submission instructions

Send an email to cs43-win1920-staff@lists.stanford.edu with: