Due in Lecture March 7.
To turn in your work, please put all of your functions, using the names specified in the homework, in a single file called 'homework7.hs'. Make a separate text file with the output of your tests with clear headings for the output from the different functions. Use the following turnin command to turn the file in electronically:
turnin homework7.hs homework7-output.txtDo not zip or tar the files before turning them in. To check that the turnin was successful, use turnin -v
See the 341 homework submission guidelines for general information, and for tips about how to capture the output from Scheme to turn in.
For each Haskell function you define, also include an explicit type declaration in your program. You can either use the most general type, or restrict it appropriate.
The assignment is to rewrite the infamous Scheme set simplification program (Assignment 5) in Haskell. You should write Haskell functions union, intersect, and difference to perform the appropriate operations on sets. Also, write a Haskell function set_simplify to simplify set expressions. You don't need to write good-set -- you can assume the inputs are well-formed.
You may represent sets as lists for union, intersect, and difference. (More sophisticated representations are possible in Haskell, but we'll use lists for simplicity.) Thus, an appropriate type for union is
union :: Eq a => [a] -> [a] -> [a](The Eq condition is because you'll need to compare elements for equality.)
For set expressions, you can use a declaration such as this:
data SetExpr = Set [Integer]
| Var String
| Union SetExpr SetExpr
deriving (Eq,Show,Read)
This says that a set expression can be a set constant, a variable, or a
union expression. You'll need to add additional elements for intersections
and differences. The "deriving" part of the definition automatically
produces functions that allow set expressions to be compared for equality,
and to be read and printed.
Thus, the type of set_simplify is
set_simplify :: SetExpr -> SetExprTo help you get started, there is a Haskell program on ceylon ~borning/haskell/starter.hs that contains these definitions, plus the beginnings of some tests. It also contains (incorrect) definitions of union and set_simplify -- these definitions allow you to run this program right away in Haskell, however, without getting complaints from Haskell about missing definitions.
For the bolder, there is an alternate version of the starter program, ~borning/haskell/monad-starter.hs that contains these same definitions, but with a more sophisticated testing framework that prints out intermediate test results and the final overall result. This testing framework uses I/O monads, which we probably won't cover in 341 -- but you should be able to figure out how to use the code if you don't mind not understanding every part (or are willing to read about monads in one of the references on the Haskell web site).
You can also download then directly from the web here:
Browse to each file and save it as starter.hs or monad-starter.hsHaskell doesn't have the program/data equivalence that Scheme does, so you can't take a SetExpr and evaluate it using a built-in eval function. However, you can write such a function. For up to 10% extra credit, write a function evaluate_set_expr. You'll need to define a data structure to represent an environment (i.e. a set of bindings of names to values). For this assignment, this environment can be completely separate from the actual Haskell variables and environment, and could be simply a list of pairs of name and value. If you represent an environment in this way, your evaluate_set_expr function would take a SetExpr and an environment, evaluate the set expression in that environment, and return the result. For example, given a suitable declaration for the type Binding, you could define:
environment = [Bind "x" [1,2,3], Bind "y" [3,4,5]] expr = Union (Var "x") (Union (Var "y") (Set [5,6]))Then evaluate_set_expr expr environment should evaluate to [1,2,3,4,5,6].