Summary of Comp1100
Contributors : Pramo
Table of Contents
- Summary of Comp1100
- Table of Contents
- Basic syntax
- Polymorphism
- Lists
- Trees
- Recursion - Common mistakes
- How to write out what a fold does.
- Error messages and debugging
- Warnings and debugging
- List of Prelude functions
- Examples for some of the functions
Basic syntax
- We wrote some basic functions and we got used to the basic syntax of a function
addOne :: Integer -> Integer addOne int = int + 1
![Syntax of a basic function](Lab1-Intro.png)
Sum type and product type
Sum type
data Season = Spring | Summer | Autumn | Winter
deriving Show
- use cases
Product type
data Shape = Circle Double
| Rectangle Double Double
- A common mistake that is made:
Circle
andRectangle
are data constructors, and they can’t be replaced by_
```Haskell data ANUPersonal = Student Int String – Int denotes the uid, string is the name | Staff Int String
findAge:: ANUPersonal -> Int findAge (_ age _) = age
This function would not work, as you cannot replace the constructor with `_`.
The function can be written as:
```Haskell
findAge:: ANUPersonal -> Int
findAge person = case person of
Staff age _ -> age
Student age _ -> age
Cases | Guards | |
---|---|---|
use | Pattern match | Boolean conditions |
wild card | _ |
otherwise |
Syntax | <pre> <p>data Colour = Red |Yellow |Orange </P> isWeekend:: Colour -> Colour isWeekend nextDay = case day of Red -> Yellow Yellow -> Orange _-> Red«br></pre> |
<pre>oddOrEven :: Int -> String oddOrEven x | mod x 2 ==0 = “Even” | otherwise = “Odd” </pre> |
- The order of the statements matter; Haskell always searches top to bottom.
- Another common mistake that is made is that case statements do not check for equality.
elem a list = case list of [] -> False a:xs -> True x:xs-> elem a xs
- In the above function, the case statement checks if the list can be written in the form [], and if so it executes the first case. If not, it checks if it can be written as something
:
something (in other words it checks if the list has at least one element in it), and if so it would assign the head of the list toa
and the tail toxs
. It does not check if a has a value; it overwrites the value that is already there. - Thus, one way to do this is to use an embedded guard:
elem a list = case list of [] -> False x:xs | x == a -> True | otherwise -> elem a xs
- In the above function, the case statement checks if the list can be written in the form [], and if so it executes the first case. If not, it checks if it can be written as something
When to use uppercase versus when to use lowercase
Lowercase
- All key words (e.g.
where
,case
,of
,instance
) - Function names
- Variables
Uppercase
- Data types
- Type constructors
data BinaryTree a = Null | Node (BinaryTree a) x (BinaryTree a)
In the above example, BinaryTree
is a data type constructor, and Null
and Node
are data constructors.
- Type class names
class Eq a where (==) :: a -> a -> Bool
Here
Eq
is a type class
Prefix and infix notation
Prefix notation is when you write the function before the inputs, e.g. mod 2 3
, while infix is when you write the function between the inputs, e.g. 1+2
. You can change between the two notations:
- to write a prefix function as an infix we use back-ticks, e.g.
2 `mod` 3
- To change an infix function to a prefix we need to write it within
()
, e.g.(+) 1 2
- Note that when you want to get information (:i) or the type signature (:t) of a function using the terminal you need to use the prefix notation of the function, i.e.,
:t +
would not work, but:t (+)
would.
Polymorphism
During our first lab we defined a function that adds one to an input number.
addOne :: Integer -> Integer
addOne int = int + 1
Thus, the function is defined for just Integer
input and would not be able to add one to a Double
or a Float
.
- If we were to define this function again for a
Double
it would look like:addOne :: Double -> Double addOne int = int + 1
- All that changed from the first to the second function was the type signature. It is not great for us to have to define the same function over and over again for different inputs.
- This is where polymorphism comes into play. We use variables to denote the input data type, e.g.
lengthList:: [a] -> Int
- If a function allows for the inputs to be of different types, then you should use two different letters, e.g.
zip:: [a] -> [b] -> [(a,b)]
. This indicates thatzip
is a function that takes in two lists (they can be the same or different) and returns a list of tuples.
Using this we can generalise the above to:
addOne :: a -> a
addOne int = int + 1
But this is not quite right. The type signature of this function says that addOne
is a function that can take any input and returns an output of the same type.
But what happens if we call addOne "two"
with a string input? The output would be "two"+1
but this would return an error.
This is where ad hoc polymorphism is used. This allows us to generalise functions to classes of input. The following classes are the most useful for the course. Data types fall under a specific type class if they have some functions defined for them, for instance if ==
is defined, then that data type falls into the Eq
class.
Eq
has==
defined for itOrd
has>
,>=
,<
and<=
Num
has+
,-
,*
Fractional
has/
definedIntegral
hasfromIntegral
(this hasInt
andInteger
)Show
has functionshow
defined for it
Whenever a function from the above is used, the input needs to be of the class. For instance for the add one, +
was used, and as it is defined for the Num
class, we need to specify that the input can be any type from the Num
class.
In order to do this we write the type constraints before the type signature and then separate it from the type signature using =>
. If you have multiple constraints you should write them out in a tuple e.g. (Num a, Ord b)
.
addOne ::Num a => a -> a
addOne int = int + 1
Lists
Let’s start off by looking at how it’s defined:
data [a] = [] | a:[a]
:
is a function that takes an element and a list (In that order) and adds the element to the start of the list.- A list
[1,2,3]
can be written as1:2:3:[]
- As a general rule, if there are multiple
:
the right-most thing would be a list and all the rest would be elements. - Let’s go over some common mistakes when pattern matching on lists. For the following examples, try guessing the number of elements in the list (sometimes you won’t be able to tell the number, but instead just a lower bound):
x:xs
- This denotes a list with one or more element.
- Explanation:
:
takes an element and a listx
is an element andxs
is a list, butxs
can be any list. It could be empty or have many elements. We do not have a way of knowing this.
[x]
- This is a list with one element.
- Explanation:
[x]
can be written asx:[]
thus indicating that the list is of length one. This does not denote any list
x:y:xs
- A list with two or more elements.
- Explanation:
x
andy
denote elements andxs
is a list, but as mentioned beforexs
can be of any list thus can be of any length.
[x:xs]
- This is a list with a single element .
- Explanation: the output of
:
is a list, thus indicating thatx:xs
will be a list (with one or more elements), but when it is wrapped within[]
brackets, then it becomes a list within a list. However, the main list will only have one element, (e.g.[[1,2,3]]
is the same as[(1:[2,3])]
- that is, the list only has one element[1,2,3]
).Trees
It describes how to define recursive functions on trees here
Recursion
When defining recursive functions on numbers, consider the value of the number, while when it comes to recursion on lists and trees, we try to reduce the number of elements in the list, and the number of nodes in the tree respectively.
When performing recursion, it is important to check if we have reduced the input to the function in the recursive call.
Common mistakes
- The base case should not be an
error
. (When this is the case, the recursive call will reduce the problem, and eventually hit the base case and return an error). - Not reducing the problem size when you do the recursive call (this will cause an infinite recursion).
Recursion on numbers
- Personally, I often find it simpler to first think about how to express the desired behaviour as a piecewise function in mathematics before proceeding to code it. Typically, the resulting code closely resembles the structure of the piecewise function itself.
- Let’s go over an example.
- when coding this up, we would have multiple guards to denote each of the cases for the piecewise function
factorial :: Integer -> Integer factorial x | x< 0 = error "factorial of negative number" | x == 0 = 1 | otherwise = x* factorial (x-1)
The base case occurs when the input is 0, and we simply return 1 because the factorial of 0 is defined to be 1.
Recursion on lists
As mentioned above a list is defined as
data [a] = [] | a:[a]
-
The basic idea when defining recursive functions on lists is to break down a list into smaller sub-problems and perform operations on each element or combine the results from sub-problems to solve a larger problem.
- Let’s consider a simple example of calculating the sum of all elements in a list using recursion in Haskell.
listSum :: [Int] -> Int listSum list = case list of [] -> 0 -- Base case: Sum of an empty list is 0 x:xs -> x + listSum xs -- Recursive case: Add current element to sum of the remaining list
- In this example, the listSum function takes a list of integers
[Int]
as input and returns an integer Int as the result. -
The base case occurs when the input list is empty
[]
. In this case, we simply return 0 because the sum of an empty list is defined to be 0.The recursive case occurs when the list has at least one element (x:xs
, explained in under lists). Here, we break down the problem by separating the first elementx
from the remaining listxs
. We recursively call listSum onxs
to calculate the sum of the remaining elements, and then addx
to it. -
Let’s run over a trace on the above function
listSum [1,2,3,4] = 1 + listSum [2,3,4] = 1 + ( 2 + listSum [3,4]) = 1 + (2 + (3 + listSum [4])) = 1+(2+(3+ (4+ listSum []))) = 1 + (2 + (3 + (4 + 0)))
- Generally the base case would be for an empty list(
[]
), but if that returns an error, we would need to define it for a list of length one (and if that is also an error, we would need to define it for a list with two elements and so on). - Let’s write a function that calculates the maximum of a list (to do this one useful function is
max
which takes in two elements and returns the maximum of the two).-
maximumList list = case list of [] -> error "" x:xs -> max x (maximum xs)
Let’s go over a trace for the above function:
maximumList [1,2,3] = max 1 (maximum [2,3]) = max 1 (max 2 (maximum [3])) = max 1 (max 2 (max 3 (maximum [])))
. BecausemaximumList []
returns an error this function would return an error. (Similarly for any input it would return an error.) - To avoid this we need to add another base case:
maximumList list = case list of [] -> error "" [x] -> x x:xs -> max x (maximum xs)
Due to the additional case, the function would not make a recursive call to the empty list, thus the trace would be
maximumList [1,2,3] = max 1 (maximum [2,3]) = max 1 (max 2 (maximum [3])) = max 1 (max 2 3) = max 1 3 = 3
-
Recursion on trees
In this course we teach three different types of trees,
- Binary trees
- Binary search trees
- Rose trees
Binary trees
A binary tree is defined as
BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
Just like lists this is a recursive data type. But this time it calls on itself twice, for the left subtree and the right subtree.
One major difference from recursion on list is that there would generally be two recursive calls, one for each tree.
For example, if we consider sumTree
as a function that adds all the numbers in a tree:
sumTree:: Num a => BinaryTree a -> a
sumTree tree = case tree of
Null -> error 0
Node l x r -> x + sumTree l + sumTree r
What happens if the Null
returns an error? Let’s take the max tree as an example,
maxTree :: Ord a => BinaryTree a -> a
maxTree tree = case tree of
Null -> error "empty tree does not have a maximum"
Node l x r -> maximum [x, maxTree l, maxTree r]
Here we meet with the same issue as earlier: the recursive call will reduce the problem and eventually hit the Null
case and return an error.
When it came to lists we only needed to add the case for a list with one element, but here we need to add three. This is because the recursive call calls on both the left and the right sub tree, so we need to make sure that neither one of them are Null
.
maxTree :: Ord a => BinaryTree a -> a
maxTree tree = case tree of
Null -> error "empty tree does not have a maximum"
Node Null x Null = x
Node Null x r = max x (maxTree r)
Node l Null r = max x (maxTree l)
Node l x r -> maximum [x, maxTree l, maxTree r]
Binary search trees
Binary search trees are an extension to binary trees. A Binary search tree is a binary tree where
- the node value is greater than all the elements of the left tree,
- the node value is smaller than all the values of the right tree,
- and each of the sub trees are binary search trees too.
In terms of coding for binary search trees, it is mostly the same as that for binary trees, but since we now have more information about the values of the nodes, we can reduce the search space of the tree. For instance we know exactly where the maximum of the tree and the minimum of the tree would be, so we would not need to search both sub trees. We know whether to search for an element in the left tree or the right tree, because we can compare it to the node and identify whether it is greater than (right sub tree), or less than(left sub tree).
Rose trees
One major limitation of binary trees is that it can have at most two non-null children. Rose trees are trees that allow for an arbitrary number of children.
data RoseTree a = RoseNode a [RoseTree a]
When dealing with rose trees, I find the following functions useful:
- map
: a function that applies a function to every element of a list
map (+1) [1,2,3] = [2,3,4]
The first argument to concatMap
is a function that takes an element of type a and returns a list of elements of type b. The second argument is a list of elements of type a. The result of concatMap
is a list of elements of type b obtained by applying the function to each element of the input list and then concatenating the resulting lists.
concatMap tail [[1,2,3],[4,5,6]] = [2,3,5,6]
Because now we have a list of trees as children, the recursive call tends to be map
ing the function to the list.
- If the function we are defining outputs a list, then you would most likely need to use
concatMap
for the recursive call. If not you should usemap
.
For example let’s write a function that returns the sum of all the elements of a roseTree
,
sumTree :: RoseTree Int -> Int
sumTree (RoseNode a list) = .....
- We have the value of the node
Int
and the list of childrenlist
. - We can write out the recursive call; as the function does not output a list we should use
map
.map sumTree list
would return a[Int]
because each element of the list is aRoseTree Int
and would be converted to aInt
. - Each of the element of this list of
Int
denotes the sum of elements of that subtree. - Thus we can calculate the sum of values of the entire subtree by using the
sum
function (explained in list of functions). sum (map sumTree list)
would give us the sum of all the nodes of the subtrees, thus if we adda
to that we would get the sum of the entire tree.
sumTree :: RoseTree Int -> Int
sumTree (RoseNode a list) = a + sum (map sumTree list)
How to write out what a fold does.
I normally write out what a fold does using the following;
consider a list a1:a2:a3.....:[]
foldr f b list
- change the
:
to the functionf
, and remove the[]
- add the base case to the right
- calculate right to left
i.e. foldr (+) 0 [1,2,3,4,5]
Note that [1,2,3,4,5] = 1:2:3:4:5:[]
1 + 2 + 3 + 4 + 5
1 + 2 + 3 + 4 + 5 + 0
1 + (2 + (3 + (4 + (5 + 0))))
similarly
foldl f b list
- change the
:
to the functionf
, and remove the[]
- add the base case to the left
- calculate left to right
i.e. foldl (+) 0 [1,2,3,4,5]
Note that [1,2,3,4,5] = 1:2:3:4:5:[]
1 + 2 + 3 + 4 + 5
0 + 1 + 2 + 3 + 4 + 5
((((0 + 1) + 2 )+ 3 )+ 4) + 5
Error messages and debugging
I have listed out some of the common error messages that are seen during the course, and what each of them are trying to tell you.
Couldn't match expected type ... with actual type ...
this error occurs when you give in inputs that are not of the input type, or when the output does not match the type of the expected output.
- this could also happen if the type signature is typed in wrong (missing an input).
For example:
takeFromList:: String -> Int -> Char takeFromList s i = i !! s
when compiled will return the following error ```Haskell
HaskellSamples.hs:4:15: error:
* Couldn’t match expected type [Char]' with actual type
Int’
* In the first argument of (!!)', namely
i’
In the expression: i !! s
In an equation for `takeFromList’: takeFromList s i = i !! s
|
4 | takeFromList s i = i !! s
| ^
HaskellSamples.hs:4:20: error:
* Couldn’t match type [Char]' with
Int’
Expected: Int
Actual: String
* In the second argument of (!!)', namely
s’
In the expression: i !! s
In an equation for `takeFromList’: takeFromList s i = i !! s
|
4 | takeFromList s i = i !! s
| ^
Failed, no modules loaded
- ``HaskellSamples.hs:4:15:`` tells you the location of the error message, in this case it is in HaskellSamples.hs in the 4th row and 15th column.
- Then it points to the `i` in the statement, and tells you that it "Couldn't match expected type `[Char]` with actual type `Int`".
- The next step in debugging would be to find out the type signature of the function ``(!!)``. This can be checked by typing ``:t (!!)`` in the terminal.
- ```Haskell
ghci> :t (!!)
(!!) :: [a] -> Int -> a
Using this we know that the first input to (!!)
should be a list while the second input should be an Int
. But in what was written ( i !! s
) we gave the inputs in the opposite order, thus to correct it we can write the function as
haskell
takeFromList:: String -> Int -> Char
takeFromList s i = s !! i
No instance for ... arising from a use of ..
This error occurs when type classes have been missed in the type signature of the function.
For example,
data Weekend = Saturday|Sunday
isSunday day = (day == Sunday)
HaskellSamples.hs:8:21: error:
* No instance for (Eq Weekend) arising from a use of `=='
* In the expression: day == Sunday
In an equation for `isSunday': isSunday day = (day == Sunday)
|
8 | isSunday day = (day == Sunday)
| ^^
Failed, no modules loaded.
- Here the error message says “No instance for (Eq
Weekend
) arising from the use of==
” - What this error is saying is that for the data type
Weekend
, the function==
has not been defined. - in order to solve this we can write
deriving Eq
in the data definition, or we can define==
for the data type by usinginstance (==) of
data Weekend = Saturday|Sunday
deriving Eq
isSunday day = (day == Sunday)
Not in scope
This can be due to a few reasons:
- if you are running something on the terminal, this could be because the file is not loaded,
- it could be because a function or a variable is misspelt,
- if you are trying to access a function that is defined in another module, it could be because it is not imported.
For example,
functionOne:: Int -> Int -> Int
functionOne numberOne numberTwo = numberone + numbertwo
HaskellSamples.hs:16:47: error:
* Variable not in scope: numbertwo :: Int
* Perhaps you meant `numberTwo' (line 16)
|
16 | functionOne numberOne numberTwo = numberone + numbertwo
| ^^^^^^^^^
Failed, no modules loaded.
This error is due to the output being calculated using a variable numberone
. This does not exist, as Haskell is case sensitive. This can be corrected by changing the output to numberOne + numberTwo
.
Lacks accompanying binding
This is an error that occurs if you have written the type signature for a function and no function definition.
- Please keep in mind to look for misspellings here in the function name.
For example,
functionOne:: Int -> Int -> Int
functionone x y = x + y
The type signature for `functionOne' lacks an accompanying binding
Perhaps you meant `functionone' (Defined at HaskellSamples.hs:16:1)
|
15 | functionOne:: Int -> Int -> Int
| ^^^^^^^^^^^
Failed, no modules loaded.
Parse error
This error refers to a syntax error. It would usually print parse error (possibly incorrect indentation or mismatched brackets)
. Some common reasons for this include:
- errors in the indentation
- missing parenthesis
- if you have not written the output in a line on a case statement
- using
=
within cases
other errors
- Capital letters and simple letter issues
Prelude.undefined
This does not mean that the Prelude library has not been defined!
Instead, the program has hit some code containing the Prelude function undefined
,
which causes an immediate crash.
sample:: Int -> Int
sample x
| even x = x
| otherwise = undefined
Warnings and debugging
Non-exhaustive patterns in function ...
This warning message occurs when you define a function but haven’t covered all possible pattern matches.
For example,
xOr ::Bool -> Bool -> Bool
xOr x y = case (x,y) of
(True,False) -> True
(False,True) -> True
HaskellSamples.hs:11:11: warning: [-Wincomplete-patterns]
Pattern match(es) are non-exhaustive
In a case alternative:
Patterns of type `(Bool, Bool)' not matched:
(True, True)
(False, False)
|
11 | xOr x y = case (x,y) of
| ^^^^^^^^^^^^^^^...
Ok, one module loaded.
- Generally the error message would give you a list of cases that you have missed, thus the solution is to add conditions for all those cases.
- Sometimes even though you have covered all the cases, haskell is not able to identify that, and thus you would still get the same warning. This can be stopped by changing the last case to a
_
(anotherwise
in a guard).
Unused variable/function
This happens when you have defined a function that is not used, in which case you can remove the function. When a variable is unused you can replace it with an _
.
List of Prelude functions
- These are a list of functions in prelude that I find useful, but there are so many more.
- All of them are written in prefix notation
- You can check the type signature by using :t on your terminal
Basic function
Function | Use |
---|---|
(.) | function composition |
flip | changes the order of the inputs to a function |
fst | takes the first element of a tuple |
snd | gets the second element of a tuple |
curry | Converts a function that takes a tuple, and converts it to a function that takes two inputs |
uncurry | Converts a function that takes two inputs to a function that takes a tuple |
Numerical functions
Function | Use |
---|---|
(+),(-),(*),(/) | arithmetic operators |
(**) | when the power is a floating-point |
(^) | the power is an integral value |
div | integer division |
mod | imodulo function |
ads | absolute value |
sqrt | square root |
exp, log | exponential,logarithm function |
max,min | gets the maximum and the minimum from two numbers |
Functions on booleans
Function | Use |
---|---|
&& | and |
|| | or |
not | not |
Functions on list that return booleans
Function | Use |
---|---|
all | takes a predicate (a function that returns a boolean) and a list and checks if every element in the list satisfies the predicate |
any | takes a predicate (a function that returns a boolean) and a list and checks if atleast one element in the list satisfies the predicate |
and | applies logical and to a list of booleans |
or | applies logical or to a list of booleans |
elem | checks if an element is in a list |
More functions that work with List
![List Functions](list.png)
Function | Use |
---|---|
(:) |
adds an elements to a the start of a list |
(++) | adds two lists together |
(!!) | takes out the element at that index |
minimum, maximum | finds the minimum and the maximum of a list of elements |
head,tail,init,last | shown in image above |
length | length of the list |
reverse | reverses the list |
take | takes the first n elements |
drop | keeps everything other than the first n elements |
elem | checks if an element is present in the list or not |
zip | takes two list and returns a single list with tuples |
unzip | reverses zip and returns the two lists within a tuple |
concat | takes a list of lists and concatenates everything |
sum | adds all the elements of a list |
product | multiplies all the elements of a list |
Higher order functions
Function | Use |
---|---|
map | applies a function to all every element of a list |
filter | removes elements that does not satisfy a condition |
foldr,foldl | right and left folds |
zipWith | Combines two lists element-wise using a binary function. |
iterate | Generates an infinite list by repeatedly applying a function to a starting value. |
repeat | Generates an infinite list with a repeating element |
replicate | Generates a list with a specified number of repeating elements. |
Type conversions
Function | Use |
---|---|
fromIntegral | converts from an integral type |
toInteger | coverts to an Integer |
Other
Function | Use |
---|---|
error | takes a string as input and gives a runtime error |
Examples for some of the functions
Basic function
Function | Use |
---|---|
(.) | ` |
flip | |
fst | fst (42, 'a') = 42 |
snd | snd (42, 'a') = 'a' |
curry | |
uncurry | curry (+) (2,1) = 3 |
Functions on list that return booleans
Function | Use |
---|---|
all | all even [1..10] = False |
any | any even [1..10] = True |
and | and [True, True, True] = True |
or | or [False, False, True] = False |
elem | elem 3 [1..10] = True |
More functions that work with List
Function | Use | |
---|---|---|
(:) |
1:[2,3] = [1,2,3] |
|
(++) | [1,2]++[3,4]=[1,2,3,4] |
|
(!!) | [1,2,3]!!1 = 2 |
\ |
minimum, maximum | minimum [1..10] = 1 |
|
length | length [1,2,3] = 3 |
|
reverse | reverse [1,2,3] = [3,2,1] |
|
take | take 5 [1..10] = [1,2,3,4,5] |
|
drop | drop 5 [1..10] = [6,7,8,9,10] |
|
elem | elem 3 [1..10] = True |
|
zip | zip [1, 2, 3] ['a', 'b', 'c'] = [(1, 'a'), (2, 'b'), (3, 'c')] |
|
unzip | unzip [(1, 'a'), (2, 'b'), (3, 'c')] = ([1, 2, 3], ['a', 'b', 'c']) |
|
concat | concat [[1, 2], [3, 4], [5, 6]] = [1, 2, 3, 4, 5, 6] |
Higher order functions
Function | Use |
---|---|
map | map (+1) [1,2,3] = [2,3,4] |
filter | filter even [1,2,3] = [2] |
foldr,foldl | explained in folds |
zipWith | zipWith (*) [1, 2, 3] [4, 5, 6] = [4,10,18] |
iterate | iterate (+1) -5 = [-5,-4,-3....] an infinite list |
repeat | repeat 3 = [3,3,3,3,3...] an infinite list |
replicate | replicate 3 7 = [7,7,7] |