Haskell Assignment

This assignment will demonstrate some of the basic concepts of Haskell and functional programming that distinguishes them from imperative programming languages, such as higher-order function, pattern matching, recursion and type classes.

Installation

Login to VM

$ ssh user@pvggit.cs.lth.se

Make a new directory for Haskell in your hopl directory

$ mkdir hopl/haskell
$ cd hopl/haskell

(For clarities sake) Create two separate files for assignment 1+2 and 3

$ touch binTree.hs
$ touch poly.hs

I have installed the GHC compiler. Rather than manually compiling your code, use the interactive environment ghci.

$ ghci

From ghci, load your files using :load or :l (lower case L)

> :l binTree
> :l poly

After making changes to your file(s), reload it/them using :reload or :r

> :r

To exit from ghci use :quit or :q

> :q

To see the type of a function or value use :type or :t

> :t "Hello World!"
> [Char]

Assignments

Haskell has type inference, which means that most of the time, even though Haskell has static typing, you do not need to explicitly say what type a function or variable is. The compiler can infer it from the context in which it is used. However(!), it is considered good coding convention to supply your functions with types. So, for all functions you write, also include their type! As an example, below is a function that calculates the length of a list:

len :: Num b => [a] -> b
len []     = 0
len (_:xs) = 1 + len xs

Here, len is a function that takes a list of type a (any type), and returns a value of type b, where additionally type b must be an instance of the type class Num. Num b could be replaced with e.g. Int b, which means that b must not only be numeric, but an integer, which is fine in this case. (Note: The type variables a and b in the type definition are arbitrary, they could be named anything. Num is a type class, Int is a type.)

(Fun fact: The type Int is a 32 bit integer, the type Integer has no upper limit of how big numbers it can represent.)

There are a total of five problems to solve, 1a+b), 2a+b) and 3). If it turns out that the assignments take too long (more than 4 hours) you can skip 1b) and/or 2b). Send completed assignment to Mattias.Nordahl@cs.lth.se, please include how long it took to complete.

Part I: Binary trees

Below is a type definition of a binary tree.

data Tree a = Empty | Branch a (Tree a) (Tree a)
        deriving (Eq, Show)

(deriving (<type class>) automatically makes a type an instance of a type class and creates default functions for them.) A tree consists of empty nodes and branches. A branch is a node that has some value and two additional (sub) trees. A leaf in the tree is thus a branch that has two Empty sub trees. An empty tree and a tree with only one node can be created as:

> let emptyTree = Empty
> :t emptyTree
emptyTree :: Tree a

and

> let singleNodeTree = Branch 'n' Empty Empty
> :t singleNodeTree
singleNodeTree :: Tree Char

This tree:

     a
    / \
   b   c
  / \   \
 d   e   f
    /
   g

can thus be represented as:

Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' (Branch 'g' Empty Empty) Empty)) (Branch 'c' Empty (Branch 'f' Empty Empty))

Balanced trees

A balanced tree is a tree where the left and right side of any node is as close to being equal in height as possible. The height difference between the left and right side of the tree must thus be less than or equal to 1.

1a) Write a function balTree that creates a balanced tree containing a given number of nodes. The value in each node can be fixed, e.g. to the character 'x'. The function type will thus be

balTree :: Int -> Tree Char

Example input/output:

> balTree 6
Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)) (Branch 'x' (Branch 'x' Empty Empty) Empty)

(Optional) 1b) Write a function isBalTree that, given a tree, returns boolean True if the tree is balanced or False if it is not.

Example input/output: OBS! I had made a mistake in the example below (False/True, now marked with ** ). It is fixed and I've added a new example that should actually return False.

> isBalTree (Branch 1 (Branch 2 (Branch 4 Empty Empty) Empty) (Branch 3 Empty Empty))
True
> isBalTree (Branch 1 (Branch 2 (Branch 4 Empty Empty) (Branch 5 Empty Empty)) (Branch 3 Empty Empty))
**True**
> isBalTree (Branch 1 (Branch 2 (Branch 4 Empty (Branch 9 Empty Empty)) (Branch 5 Empty Empty)) (Branch 3 Empty Empty))**
False

Complete tree

A complete tree is slightly different from a balanced tree. A complete tree has all of its levels filled, except for possibly the last. If there are not enough nodes to fill the last level, the tree should be "left heavy". The nodes can be numbered moving through each level from left to right. For example, a tree with 7 elements can be filled completely, as in:

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

whereas a tree with 5 elements cannot be filled, and must look like:

      1
    /   \
   2     3
  / \
 4   5

2a) Write a function compTree that creates a complete tree containing a given number of nodes. Let the value in each node be its number as in the examples above.

Example input/output:

> compTree 5
Branch 1 (Branch 2 (Branch 4 Empty Empty) (Branch 5 Empty Empty)) (Branch 3 Empty Empty)

(Optional) 2b) Write a function isCompTree that, given a tree, returns boolean True if the tree is "complete" or False if it is not. Tip: If counting (indexing) the nodes as in the above examples (row by row, left to right), then for a tree to be complete, the first empty node from the right sub tree must come after (have a higher number than) the last non-empty node from the left sub tree.

Example input/output:

> isCompTree (Branch 1 (Branch 2 (Branch 4 Empty Empty) Empty) (Branch 3 (Branch 6 Empty Empty) Empty))
False
> isCompTree (Branch 1 (Branch 2 (Branch 4 Empty Empty) (Branch 5 Empty Empty)) (Branch 3 (Branch 6 Empty Empty) Empty))
True

Part II: Data types and Type classes

Data types (e.g. Bool, Int, Float etc.) can be created by the user herself by using data (like our binary tree type Tree).

Type classes are much like interfaces in Java. A type class can define a number of functions which then all data types that are instances of it must implement. See e.g. the definition of the Eq class below.

class Eq a where  
    (==) :: a -> a -> Bool  
    (/=) :: a -> a -> Bool  
    x == y = not (x /= y)  
    x /= y = not (x == y)

A data type "MyType" may be declared an instance of the Eq class by writing

instance Eq MyType where

followed by an implementation of the (==) function. Since the two functions (==) and (/=) in Eq additionally are defined as each others inverses, it is enough to implement just one of them.

Tip/Fun fact: Functions can be implemented (and used) both as prefix or infix operators, e.g.

instance Eq MyType where
    (==) x y = ...

or

instance Eq MyType where
    x == y = ...

Functions that have only special characters (like +, -, ==, etc.) are infix operator by default. To use as prefix they must be in parentheses. Other functions are prefix by default, but can be used infix if enclosed in ` (left apostrophe?), as in:

mod 5 3 == 5 `mod` 3

3a) Create a new data type Poly, representing a polynomial. A polynomial can be represented as four things; a constant value using the type Integer, an addition of two polynomials, a subtraction of two polynomials or a multiplication of two polynomials. It should be valid Haskell syntax to write the following (representing ((3*7) + (4-2)) ):

> Add (Mul (Const 3) (Const 7)) (Sub (Const 4) (Const 2))

3b) Make your data type Poly an instance of the Show type class, so that it can be shown as a String. (The Show type class has one function show, and is similar to Javas toString. Write :t show to see its type.) Constants should be shown just as their value while addition, subtraction and multiplication should be shown within parenthesis and using their appropriate operator. Writing the example from 3a) in ghci should yield the result:

> Add (Mul (Const 3) (Const 7)) (Sub (Const 4) (Const 2))
((3 * 7) + (4 - 2))

3c) Also make Poly an instance of the type class Eq. Define the (==) function using syntactical equality, thus:

> Add (Const 2) (Const 3) == Sub (Const 7) (Const 2)

should return False! And

> Add (Const 2) (Const 3) == Add (Const 2) (Const 3)

should return True.

3d) Also make Poly an instance of the type class Num. Implement the functions fromInteger, (+), (-) and (*). Num also has two functions abs and signum. These can be implemented as undefined.

  abs       = undefined
  signum    = undefined

Polynomials should now be recognized as numbers. Using explicit typing you can e.g. do:

> 3*7-4*2+12 :: Int
25
> 3*7-4*2+12 :: Poly
(((3 * 7) - (4 * 2)) + 12)