| Starter code (and tests): | pa4.hs |
The purpose of this assignment is to get some hands-on experience with laziness, the type system, and pattern matching 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.
You can cause GHCi to load a file by passing it a file name on the command line.
You can also load a file using :l file,
in this case leaving off the .hs file extension.
Note that if any error occurs while loading a file, GHCi will load nothing from the file. For this reason it may come in handy to comment out large blocks using {- the delimiters surrounding this phrase -}.
Using Haskell's pattern matching, define the following functions, whose type declarations are provided for you in the starter code:
split takes a list and returns a tuple of two lists that are,
as nearly as possible, equal halves of its argument.
When the list is odd in length, the first half is the shorter.
merge takes a predicate
and two lists sorted according to the predicate,
and merges them into into a single list sorted according to the predicate.
mergeSort takes a predicate and
sorts a list according to the predicate,
employing the split and merge functions you wrote
and implementing the merge-sort algorithm.
Hint: You may want to look at Haskell's div function.
Define the following functions, whose type declarations are provided for you in the starter code:
divides gives
True only if its first argument (evenly) divides its second.
divisors
gives a list of all the positive integers that divide its argument.
isPrime
gives True only if 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 define some tests that convince you it contains what it should!
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 an a value
and strings representing the left and right children of a node,
and gives a function that gives a string representation of a tree
in parenthesized prefix notation (like Scheme).
showPost takes an a value
and strings representing the left and right children of a node,
and gives a function that gives a string representation of a tree
in postfix (or "reverse polish") notation.
treeApply takes two functions,
one for branches and another for leaves, and gives a function that
traverses the tree applying the first function at the branches
and the second function at the leaves.
For the precise types of its parameters, see the type declaration given
and the examples of its use in the tests.
Hints: You may want to look at Haskell's show function and (++) operator, and refer to Chapter 7 of PLAI for examples of functions that operate on defined types.
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 tests.