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.
Login to VM
$ ssh email@example.com
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.
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
To exit from ghci use :quit or :q
To see the type of a function or value use :type or :t
> :t "Hello World!" > [Char]
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
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 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
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
> let singleNodeTree = Branch 'n' Empty Empty > :t singleNodeTree singleNodeTree :: Tree Char
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))
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
> 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
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.
> 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.
> 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
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
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 = ...
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
: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
Num also has two functions
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)