CSE 130, Summer 2009

Programming Languages: Principles and Paradigms

Programming Assignment 4

The purpose of this assignment is to get some hands-on experience with the type system, laziness, pattern matching, and purely functional programming (with curried functions) in Haskell. It is to be completed individually according to the course collaboration policy.

You can work on this assignment using GHCi on ACS machines or on your own machine. (GHCi is the interactive interpreter provided with the Glasgow Haskell Compiler.)

• On an ACS GNU/Linux machine you will need to run prep cs130u before you can run ghci.
• Here's one way to load PA4.hs and run the tests defined in it:

  $ ghci PA4.hs
  GHCi, version 6.10.4: http://www.haskell.org/ghc/  :? for help
  Loading package ghc-prim ... linking ... done.
  Loading package integer ... linking ... done.
  Loading package base ... linking ... done.
  [1 of 1] Compiling PA4              ( PA4.hs, interpreted )
  Ok, modules loaded: PA4.
  *PA4> runTests
  Loading package HUnit-1.2.0.3 ... linking ... done.
  [error messages omitted]
  Cases: 15  Tried: 15  Errors: 15  Failures: 0
  Counts {cases = 15, tried = 15, errors = 15, failures = 0}
  *PA4>
  

  You could also echo runTests | ghci PA4.hs all at the command line, or load the file from inside GHCi using :l followed by the module name (without the .hs extension). Note that if any error occurs while loading a file, GHCi will load nothing from the file.
• In the code you'll need to replace everything undefined with a suitable definition and add your own tests to those given. You might find the HUnit 1.0 User's Guide useful when writing tests.

Tasks

Part 1

Define the following functions:

• contains is a function of two sets that simply gives True iff its first argument contains its second. Sets are represented by lists, but the elements appear in no particular order; an element repeated in the list is in the set, just as if it appears once.
• cross is a function of two sets that gives a relation containing all pairs where the first element is from the first set and the second element is from the second set.
• inverse takes a relation and gives its inverse.
• asRelationOn takes an binary function and a set of elements in the function's domain, and it gives a relation corresponding to that function as defined on that set.

All these functions should handle infinite sets and relations wherever possible. The tests provided contain some examples.

Part 2

Define the following functions:

• divides gives True iff its first argument (evenly) divides its second.
• divisors gives a list of all the positive integers that divide its argument.
• isPrime gives True iff its argument is a prime number. A prime number is a positive integer with exactly 2 divisors (1 and itself).

Now, define the infinite list primes that contains all and only the prime numbers. Make sure to write some tests that convince you of this!

Part 3

Examine the BinaryTree type, which has two variants: Branch and Leaf. Note the type variables a for values in branches, and b for those in leaves. So the type is polymorphic, but we will use a BinaryTree as an abstract syntax tree representing a simple arithmetic expression on integers, so a will be a BinOp type and b will be a Num.

Now define the following functions, whose type declarations are provided for you:

• getFunction takes a BinOp and gives a corresponding Haskell function.
• showParenPre takes the value stored in a branch and two Strings representing its left and right children, and gives a String representation of that branch and its children in parenthesized prefix notation (like Scheme).
• showPost takes the value stored in a branch and two strings representing its left and right children, and gives a String representation of that branch and its children in postfix (or "reverse polish") notation.
• treeApply takes two functions, one for branches and another for leaves, and gives a function that traverses a tree applying the first function at the branches and the second function at the leaves. See the examples of its use in the tests.

Testing

As with previous assignments, you will need to think carefully about where your code might fail and add your own test cases to the test file. Your submission will be tested against a more comprehensive suite of tests than we gave you and we may also assess the quality of your testing.

Hints

In addition to the ideas and examples in Chapter 7 of PLAI you may find it useful to be familiar with ($), (++), all, elem, fst, snd, and show, and list comprehensions. If you import List you'll also have access to intersect, union, and nub. There's lots of other useful stuff in the Haskell prelude you can use without importing anything.

Submitting Your Work

• Copy your files to an ACS GNU/Linux machine (if they're not already there).
• Before submitting your work, it's a good idea to make sure it runs in GHCi on an ACS GNU/Linux machine and passes all the tests we've given you.
• In the directory where your files are, run bundle-pa4 and follow the directions. (If you haven't run prep cs130u yet, you'll have to do that first.)
• You can overwrite earlier submissions until the deadline, so submit early and often!
• After the deadline the bundle script will no longer work. Late submissions will be accepted only by arrangement with the instructor.