In this lab you'll get familiar with creating new instances of type classes.
This week, you'll be writing code to implement new numerical types as
instances of type classes. Write a file called
lab3.hs in which you will implement two new
numerical types:
A type called AbstractInteger. This is an integer type
that only contains Zero, Succ AbstractInteger
(successor of an abstract integer) and Pred AbstractInteger
(predecessor of an abstract integer). All operations on
AbstractIntegers must maintain the invariant that a given
AbstractInteger can have only Preds or
Succs, but not both (or it can be Zero). So,
Pred (Pred Zero) is a valid AbstractInteger, but
Pred (Succ Zero) is not, since it should have been normalized to
just Zero.
Make your AbstractInteger derive the Eq and
Show type classes automatically. Also implement
AbstractInteger as an instance of the Ord type
class by defining your own comparison routine, and then separately as an
instance of the Num type class by defining the appropriate
functions for that type class. Note that some functions of the type class
have default implementations, so feel free to implement the minimal set of
operations (see the documentation for more information on which functions
have default implementations). However, do not define operations on
AbstractIntegers by converting to and from the corresponding
operations on ordinary Haskell Integers; define these operations
only in terms of AbstractIntegers. Hint: multiplication can
easily be defined recursively in terms of addition.
Write a function called ai_toInteger to convert
AbstractIntegers to Haskell Integers (this is
useful for testing).
Write two recursive factorial functions (one
non-tail-recursive, the other tail-recursive, neither one using higher-order
functions such as foldr) which work on any instance of both
Ord and Num, including
AbstractIntegers and regular Integers. Make sure
you test for invalid inputs and raise an error on invalid inputs (that's why
you need the input type to be an instance of Ord). Be careful
not to use your factorial functions on large AbstractIntegers
unless you're prepared to wait a long time, chew up a huge amount of memory
and see your screen covered with Succs inside tons of
parentheses. Note: if you don't know the difference between a
tail-recursive and a non-tail-recursive function, look here.
Note that the numbers 0 and 1 (and, indeed, all
literal integers) are not necessarily of type Int or type
Integer; they can be of any type which is an instance of
the Num class. Try typing
0 :: AbstractInteger
into ghci and see what happens.
A Quaternion type. As you all remember from your courses
on the history of differential geometry ;-), quaternions are a sort-of
generalization of complex numbers developed initially by the Irish
mathematician Sir William Rowan Hamilton to solve dynamics problems more
easily. Recently, they have been used a lot for 3-D computer graphics
purposes, so aspiring video-game hackers also need to know about quaternions.
As you know, complex numbers have two components (the real and imaginary
components). In contrast, quaternions have four: the real, imaginary
i, imaginary j, and imaginary k
components. By analogy with i for complex numbers (the
square root of -1), there are now three special numbers,
i, j, and k,
related by these rules:
i * i = -1
j * j = -1
k * k = -1
i * j = k
j * i = -k
j * k = i
k * j = -i
k * i = j
i * k = -j
Note that this means that
i, j, and
k anti-commute under multiplication.Your job is to implement a Quaternion type in Haskell. Your
type can automatically derive the Eq type class, but provide an
explicit implementation of the Show class for
Quaternions so that a quaternion will be pretty-printed as
e.g. "1.0 + 2.0i + 3.0j + 4.0k". Use Double values for
the components. Implement Quaternions as an instance of the
Num type class as you did for AbstractIntegers.
Note that absolute value for quaternions means the square root of the sum of
squares of all the components. To make the absolute value into a quaternion
(which you have to do to implement the Num class) you should set
the non-real components to zero. The signum of a quaternion is the original
number scaled by the real component of the absolute value (i.e. each
component is divided by the same scale value). Addition is componentwise,
and as for multiplication... you can either do the algebra yourself or look
it up on-line (see below).
Note that Quaternions cannot usefully implement the
Ord type class -- why is that? Write the answer in a comment in
your submission.
To test your class, show that the rules for multiplying the unit
components i, j, and
k all hold as described above. Include this test code in
your submission as a function called testQuaternions, which will
simply print out all possible pairwise products of these three numbers
(including the numbers multiplied by themselves). This function should have
type IO () and should display the arguments of the
multiplications as well as the results.
The file lab3.hs, containing your implementation
of the numerical type classes described above. Also include answers to the
questions asked above in comments in your code, as well as the requested test
routines.