In this lab you'll get familiar with creating new instances of type classes.

- 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`AbstractInteger`

s must maintain the invariant that a given`AbstractInteger`

can have only`Pred`

s or`Succ`

s, 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`AbstractInteger`

s by converting to and from the corresponding operations on ordinary Haskell`Integer`

s; define these operations only in terms of`AbstractInteger`

s. Hint: multiplication can easily be defined recursively in terms of addition.Write a function called

`ai_toInteger`

to convert`AbstractInteger`

s to Haskell`Integer`

s (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`AbstractInteger`

s and regular`Integer`

s. 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`AbstractInteger`

s unless you're prepared to wait a long time, chew up a huge amount of memory and see your screen covered with`Succ`

s 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 typing0 :: 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, imaginary`i`

, and imaginary`j`

components. By analogy with`k`

for complex numbers (the square root of -1), there are now three special numbers,`i`

,`i`

, and`j`

, related by these rules:`k`

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

- all quaternions have four components
- quaternions do not necessarily commute under multiplication. In fact,
the unit values
,`i`

, and`j`

anti-commute under multiplication.`k`

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`Quaternion`

s 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`Quaternion`

s as an instance of the`Num`

type class as you did for`AbstractInteger`

s. 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

`Quaternion`

s 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`

, and`j`

all hold as described above. Include this test code in your submission as a function called`k`

`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.

- A Gentle Introduction to Haskell, by Hudak, Peterson and Fasel, specifically chapter 5.
- The Wikipedia article on tail recursion.
- The Wikipedia article on quaternions.
- Some more background material on quaternions.