CSE 230 W11 - Homework #1, Due Friday, January 14th

Preliminaries

Before starting this part of the assignment:

1. Read chapters 1 — 3 of The Haskell School of Expression.
2. Download and install the Glasgow Haskell Compiler (GHC).

Assignment (Part 1)

1. Create a file hw1.hs with the definitions of shapes and shape-manipulating functions from Chapter 2 of SOE. Test these definitions using ghci.

2. In the same file, define functions rectangle and rtTriangle as suggested at the end of Section 2.1 (Exercise 2.1). Each should return a Shape built with the Polygon constructor.

3. Define a function

> sides :: Shape -> Integer

which returns the number of sides a given shape has. For the purposes of this exercise, an ellipse has 42 sides, and empty polygons, single points, and lines have zero sides.

4. Define a function

> bigger :: Shape -> Float -> Shape

that takes a shape s and expansion factor e and returns a shape which is the same as s but bigger by a factor of e.

5. The Towers of Hanoi is a puzzle where you are given three pegs, on one of which are stacked n discs in increasing order of size. To solve the puzzle, you must move all the discs from the starting peg to another by moving only one disc at a time and never stacking a larger disc on top of a smaller one.

To move n discs from peg a to peg b using peg c as temporary storage:

1. Move n - 1 discs from peg a to peg c.
2. Move the remaining disc from peg a to peg b.
3. Move n - 1 discs from peg c to peg b.

Write a function

> hanoi :: Int -> String -> String -> String -> IO ()

that, given the number of discs n and peg names a, b, and c, where a is the starting peg, emits the series of moves required to solve the puzzle. For example, running

> hanoi 2 "a" "b" "c"

should emit the text

move disc from a to c
move disc from a to b
move disc from c to b

Preliminaries

Before starting this part of the assignment:

1. Download the SOE code bundle from the Haskell School of Expression page.

2. Verify that it works by changing into the SOE/src directory and running ghci Draw.lhs, then typing main0 at the prompt:

cd SOE/src
ghci Draw.lhs
*Draw> main0

You should see a window with some shapes in it.

NOTE: If you have trouble installing SOE, see this page

Assignment (Part 2)

1. The Sierpinski Carpet is a recursive figure with a structure similar to the Sierpinski Triangle discussed in Chapter 3:

Sierpinski Carpet

Write a function sierpinskiCarpet that displays this figure on the screen (in the same file as your code for Part 1).

Note that you either need to run your program in SOE/src or add this path to GHC’s search path. Also, the organization of SOE has changed a bit, so that now you use import SOE instead of import SOEGraphics.

2. Write a function myFractal which draws a fractal pattern of your own design. Be creative! The only constraint is that it shows some pattern of recursive self-similarity.

Warm Up

1. Read chapters 5 and 7 of SOE.
2. Do problem 5.2 from SOE (but do not turn in).
3. Do problems 5.3, 5.4, 5.5, 5.6, 7.1, and 7.2 from SOE, and turn them is as part of the source code you create below.
4. Write the function map in terms of foldr, and turn it in in the same way.

Preliminaries

This assignment involves transforming XML documents. To keep things simple, we will not deal with the full generality of XML, or with issues of parsing. Instead, we will represent XML documents as instances of the following simplified type:

> data SimpleXML =
>    PCDATA String
>  | Element ElementName [SimpleXML]
>  deriving Show
> 
> type ElementName = String

That is, a SimpleXML value is either a PCDATA (“parsed character data”) node containing a string or else an Element node containing a tag and a list of sub-nodes.

First, download the required files for this assignment: hw1.tar.gz. Unpack the files and make sure that you can successfully run the main program (in Main.hs). We’e provided a Makefile, which you can use if you like. You should see this output:

Converting... Results differ: ’WRITE ME!’ vs ’<html><body><h1>A Mi’

Next, have a look at the provided files:

• Main.hs is the main program — it’s just a test harness for the rest.
• Mine.hs is your part. This is where you will put the code you write, and it’s the only file you will turn in. At the moment, it contains just stubs.
• XMLTypes.hs contains the type definitions for our simplified XML trees.
• Play.hs contains a sample XML value. To avoid getting into details of parsing actual XML concrete syntax, we’ll work with just this one value for purposes of this assignment. The XML value in Play.hs has the following structure (in standard XML syntax):

<PLAY>
  <TITLE>TITLE OF THE PLAY</TITLE>
  <PERSONAE>
    <PERSONA> PERSON1 </PERSONA>
    <PERSONA> PERSON2 </PERSONA>
    ... -- MORE PERSONAE
    </PERSONAE>
  <ACT>
    <TITLE>TITLE OF FIRST ACT</TITLE>
    <SCENE>
      <TITLE>TITLE OF FIRST SCENE</TITLE>
      <SPEECH>
        <SPEAKER> PERSON1 </SPEAKER>
        <LINE>LINE1</LINE>
        <LINE>LINE2</LINE>
        ... -- MORE LINES
      </SPEECH>
      ... -- MORE SPEECHES
    </SCENE>
    ... -- MORE SCENES
  </ACT>
  ... -- MORE ACTS
</PLAY>

• sample.html contains a (very basic) HTML rendition of the same information as Play.hs. You may want to have a look at it in your favorite browser. The HTML in sample.html has the following structure (with whitespace added for readability):

<html>
  <body>
    <h1>TITLE OF THE PLAY</h1>
    <h2>Dramatis Personae</h2>
    PERSON1<br/>
    PERSON2<br/>
    ...
    <h2>TITLE OF THE FIRST ACT</h2>
    <h3>TITLE OF THE FIRST SCENE</h3>
    <b>PERSON1</b><br/>
    LINE1<br/>
    LINE2<br/>
    ...
    <b>PERSON2</b><br/>
    LINE1<br/>
    LINE2<br/>
    ...
    <h3>TITLE OF THE SECOND SCENE</h3>
    <b>PERSON3</b><br/>
    LINE1<br/>
    LINE2<br/>
    ...
  </body>
</html>

Assignment (Part 3)

Write a function formatPlay that converts an XML structure representing a play to another XML structure that, when printed, yields the HTML specified above (but with no whitespace except what’s in the textual data in the original XML).

The main action that we’ve provided will use your function to generate a file dream.html from the sample play. The contents of this file after your program runs must be character for character identical to sample.html. Our main action tests this.

Important: The purpose of this assignment is not just to “get the job done” — i.e., to produce the right HTML. A more important goal is to think about what is a good way to do this job, and jobs like it. To this end, your solution should be organized into two parts:

1. a collection of generic functions for transforming XML structures that have nothing to do with plays, plus

2. a short piece of code (a single definition or a collection of short definitions) that uses the generic functions to do the particular job of transforming a play into HTML.

Obviously, there are many ways to do the first part. The main challenge of the assignment is to find a clean design that matches the needs of the second part.

You will be graded not only on correctness (producing the required output), but also on the elegance of your solution and the clarity and readability of your code and documentation. Style counts. It is strongly recommended that you rewrite this part of the assignment a couple of times: get something working, then step back and see if there is anything you can abstract out or generalize, rewrite it, then leave it alone for a few hours or overnight and rewrite it again. Try to use some of the higher-order programming techniques we’ve been discussing in class.