Summary of Comp1100

Contributors : Pramo

Table of Contents

• Summary of Comp1100
• Table of Contents
• Basic syntax
  • Sum type and product type
    • Sum type
    • Product type
  • When to use uppercase versus when to use lowercase
    • Lowercase
    • Uppercase
  • Prefix and infix notation
• Polymorphism
• Lists
• Trees
• Recursion - Common mistakes
  • Recursion on numbers
  • Recursion on lists
  • Recursion on trees
    • Binary trees
      • Binary search trees
    • Rose trees
• How to write out what a fold does.
• Error messages and debugging
  • Couldn't match expected type ... with actual type ...
  • Not in scope
  • Lacks accompanying binding
  • Parse error
  • other errors
  • Prelude.undefined
• Warnings and debugging
  • Non-exhaustive patterns in function ...
  • Unused variable/function
• List of Prelude functions
  • Basic function
  • Numerical functions
  • Functions on booleans
    • Functions on list that return booleans
  • More functions that work with List
  • Higher order functions
  • Type conversions
  • Other
• Examples for some of the functions
  • Basic function
    • Functions on list that return booleans
  • More functions that work with List
  • Higher order 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
  


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 and Rectangle 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

• 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 to a and the tail to xs. 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
    

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 that zip 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 it
• Ord has >,>=,< and <=
• Num has +,-,*
• Fractional has / defined
• Integral has fromIntegral (this has Int and Integer)
• Show has function show 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 as 1: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 list x is an element and xs is a list, but xs 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 as x:[] 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 and y denote elements and xs is a list, but as mentioned before xs 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 that x: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 element x from the remaining list xs. We recursively call listSum on xs to calculate the sum of the remaining elements, and then add x 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 []))). Because maximumList [] 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 maping 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 use map.

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 children list.
• 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 a RoseTree Int and would be converted to a Int.
• 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 add a 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

1. change the : to the function f, and remove the []
2. add the base case to the right
3. 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. 1 + 2 + 3 + 4 + 5
2. 1 + 2 + 3 + 4 + 5 + 0
3. 1 + (2 + (3 + (4 + (5 + 0))))

similarly foldl f b list

1. change the : to the function f, and remove the []
2. add the base case to the left
3. 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. 1 + 2 + 3 + 4 + 5
2. 0 + 1 + 2 + 3 + 4 + 5
3. ((((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 using instance (==) 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 _ (an otherwise 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

Numerical functions

Functions on booleans

Functions on list that return booleans

More functions that work with List


Higher order functions

Type conversions

Other

Examples for some of the functions

Basic function

Functions on list that return booleans

More functions that work with List

Higher order functions