COMP105 (Haskell Functional Programming)

This lecture covers the answers to last year’s class test which is available here.

2019 Class Test

Question 6

Tail recursion is when once you have recursed there is nothing left to process. Having an accumulator is a sign that this is the case.

This lecture is on tail recursion.

Strict Evaluation of factorial

fact 1 = 1
fact n = n * fact (n-1)

When calling fact 4 under strict evaluation the computer will compute the following:

4 * fact 3
4 * (3 * fact 2)
4 * (3 * (2 * fact 1))
4 * (3 * ( 2 * 1))
24

This will make a very large tree of values to be evaluated

Recursion and Memory

Recursion seems to use a lot of memory.

4 * (3 * (2 * fact 1))

This is the call stack:

• Each recursive call adds a new value to the stack.
• We can only evaluate the stack then we hit a base case.

We will run out of memory if the call stack it too big.

Tail Recursion

This is the solution to the problem with running our of memory.

A function is tail recursive if there is nothing left to do after the recursive call.

If there is something to do after the recursive call then it is not tail recursive.

is_even 0 = True
is_even 1 = False
is_even n = is_even (n-2)

This is tail recursive as there is nothing added to the call stack. We are passing a single value and not generating additional values.

• There is nothing left to do after the recursive call.
• No call stack is built up.
• Less memory is used.

This is an important concept in all languages:

• Even for most imperative languages.
• Most C compilers will optimize tail recursive calls.

Writing Tail Recursive Functions

We can make functions tail recursive:

• By adding an accumulator as an argument.
• It is initialized to some value.
• Each recursive call modifies it.
• Just like for folds and scans.

fact_tail 1 acc = acc
fact_tail n acc = fact_tail (n-1) (acc * n)

factorial n = fact_tail n 1

This is the same function as before but implemented with a helper function that is tail recursive. You can see that it uses a running total so that it doesn’t have to store many values and then add them together later.

No call stack built up, so no problems in strict evaluation.

In lazy evaluation the memory problem is just transferred to the accumulator.

fact_tail in Lazy Evaluation

If we call factorial 4 in a lazily evaluated language:

fact_tail 4 1
fact_tail 3 (4*1)
fact_tail 2 (3*4*1)
fact_tail 1 (2*3*4*1)
24

You can see that the memory problem is still here in lazy evaluation.

Fixing fact_tail

We can fix this with the $! (strict evaluation) operator.

fact_tail 1 acc = acc
fact_tail n acc = fact_tail (n-1) $! (acc * n)

factorial n = fact_tail n 1

Now there are no memory problems as the accumulator is evaluated strictly.

This is only okay because we know that we are going to evaluate the accumulator for sure.

Left Folds via Tail Recursion

foldl is naturally implemented via tail recursion.

• In strict languages, foldl should be preferred over foldr.

foldl f acc []     = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

> foldl (=) 0 [1,2,3,4,5]
15

Strict Left Folds

The previous implementation is strict but will have memory issues in Haskell. foldl' is the strict version of foldl.

• It is in the Data.List package.

It is implemented like so:

foldl' f acc [] = acc
foldl' f acc (x:xs) = (foldl' f $! (f acc x)) xs

This will usually use less memory than foldl.

This is saying that f is lazy f acc x is strict and xs is lazy.

Left Folds and Laziness

A left fold can destroy laziness.

• We must reach the end of the list to get the accumulator.

  This mean that if you’re operating on an infinite list then your program will never terminate.

Here is a binding that generates an infinite list.

> let f = foldr (\ x acc -> x : acc) [] [1..]
> take 4 f
[1,2,3,4
]

If you rewrite this using a left fold then it won’t terminate.

> let g = foldl(\ acc x -> acc ++ [x]) [] [1..]
> take 4 g
<will never terminate>

You shouldn’t use foldl if you are going to evaluate an infinite list.

Summary

foldr

• Should be used by default in Haskell.
  • Because it preserves laziness.

foldl

• There is not real reason to use this in Haskell.

foldl'

• Should be used when we know that laziness won’t help.
  • If we know that we will fold the entire list.
• Can have performance benefits.

Exercises

1.  sum_helper acc [] = acc
    sum_helper acc (x:xs) = (sum_helper $! (acc + x)) xs
    sum list = sum_helper 0 list
   

2.  length_helper acc [] = acc
    length_helper acc (_:xs) = (length_helper $! (acc + 1)) xs
    length list = legnth_helper 0 list
   

3.  length = foldl' (\ acc _ -> acc + 1) 0
   

Lazy Lists

Lists are never evaluated until they are needed. This means that take 1 [1..10] is just as efficient as take 1 [1..1000].

Infinite Lists

The reason why we are able to make infinite lists is a result of lazy evaluation. As evaluation only happens right at the end, the program won’t hang by trying to evaluate it in the background. You can make simple infinite list like so:

[1,1..]

Or like this:

all1s :: [Int]
all1s = 1 : all1s

As a result of this you are able to do infinite computations on infinite lists provided that you can resolve to a finite value.

all2s = zipwith (+) all1s all1s

This will produce an infinite sum of infinite lists.

Example

sieve (x:xs) = x : filter (\y -> y `mod` x /= 0) (sieve xs)

You can then use this function to define other useful infinite lists:

primes = sieve [2..]

> take 10 primes
[2,3,]
> primes !! 1000
7927

The $ Operator

The $ function evaluates a function.

Take this function and apply it to this argument

Strict Evaluation

The $! operator makes Haskell evaluate strictly:

> let f x = 1

> f $ undefined
1

> f $! undefined
Error

For most code you won’t notice the difference but it can change the error outputs.

Evaluation Strategies

inc x = x + 1
square x = x * x

So square (inc 2) = (2 + 1) * (2 + 1) = 9 . How does Haskell evaluate this?

Strict Evaluation

In strict evaluation, we always apply the innermost function first:

square (inc 2)
	square (3)
	3 * 3
	9

Here we first apply inc and then apply square.

This means that when we call a function we first evaluate its argument.

This is the method that imperative languages use to evaluate functions. Haskell does not evaluate this way

Lazy Evaluation

In lazy evaluation, we always apply the outermost functions first:

square (inc 2)
	inc 2 * inc 2
	3 * 3
	9

First apply square then apply inc.

This method waits as long as possible until computing values.

In the following, nothing is computed until we ask for the value of z.

> let x = 1 + 1
> let y = x + x
> let z = y / 2
> z
2.0

> let x = 1 + undefined
> let y = x + x
> let z = y / 2
> z
*** Exception: Prelude.undefined

You can see here that the error only occurs when the binding is evaluated.

If a value is never used, it is never computed:

> let f x = 1
> f undefined
1

You can see here that the argument is not evaluated. This results in the program not crashing due to evaluating undefined.

Imperative Languages

Imperative languages are always strict:

• So programmers know the order of their side effects.

Functional Languages

For pure functions the order of evaluation is irrelevant.

• You always get the same answer.

• No need to worry about side effects.

Some functional languages are strict by default:

• ML
• Ocaml

Others are lazy by default:

• Haskell

Lazy vs. Strict

If strict evaluation finds an answer, the lazy evaluation fill find the same answer.

Sometimes lazy evaluation can find an answer when strict evaluation cannot:

> fst (1, 1 `div` 0)
1

A strict evaluator would crash in this example.

Sometimes lazy evaluation can be more efficient than strict:

• Particularly if some values are computed but never used.

Lazy evaluation only ever computed a value when it is needed. This can lead to big efficiency savings:

• When computing the the head of a doubled list.

Summary

Strict evaluation:

• Evaluate things as soon as possible.
• Gives certainty over order of side effects.

Lazy evaluation:

• Evaluate things only when they are needed.
• Potentially eliminates unneeded computation.

Exercise

1. 1

2. [5,10,*** Exception: divide by zero

   This is due to the fact that it evaluates last so will print the first two elements. This is opposed to crashing immediately.

3. *** Exception: divide by zero

IO Example

In this lecture we are covering an extended example on making ASCII art of a given input char. It will add chars onto the resultant output when you give them as input.

As this is an example lecture I will be taking notes on key concepts, for the full example see the slides.

The source code for this example is given here.

Printing Text-Mode Graphics

This is a stub, see the slides above for more details.

Updating the Screen

Interactive Loop

This is a stub, see the slides above for more details.

Main Function

This is a stub, see the slides above for more details.

Useful IO Functions

This lecture covers many useful functions included with Haskell. I won’t be writing out examples but I will be writing down names and descriptions to search through.

For more detailed examples view the slides for this lecture.

print

This prints out any show-able type.

putStr

This prints a string without adding a new line.

With this you have to manually end the line with:

putStr '\n'

readLn

This function gets a line of input and then calls read. This saves you calling read when getting a line with getLine.

To give an explicit type use the syntax:

x <- readLn :: IO Int

This is due to the fact that when readLn is reading the line it is still in the IO ‘box’.

forever

This repeat an IO action forever. It is in the Control.Monad package. This is a higher order IO action as it takes another IO action as an input.

It can be used to make interactive code that runs a function forever.

sequence

This IO action will run a list of IO actions and will return a list containing the return values of the IO actions.

The IO actions must have the same type otherwise they can’t be put in the same list.

sequence works well with map:

sequence (map print [1..10])

This saves you typing out all the IO actions to sequence on.

sequence_

This IO action is the same as sequence but it will return the type IO (). You would want to use this when the IO actions you are running return IO () themselves.

mapM

You can use this map on monads. This is similar to running sequence in conjunction with map. This is the same as the code from before:

mapM print [1..10]

mapM_

This is similar to sequence_.

when

This executes an IO action if a condition is true.

when True (putStrLn "hi")

This is similar to if in pure functional code.

unless

This is the opposite of when. It will execute if the condition is false.

Exercises

1.  timesTwo = do
        n <- readLn :: IO Int
        print (n * 2)
   

2.  import Control.Monad
    ltFiveOnce = do
        x <- getLine
        when (length x < 5) (putStrLn "yes")
        when (length x >= 5) (putStrLn "no")
    ltFive = forever ltFiveOnce
   

3.  addThree = do
    x <- sequence [readLn,readLn,readLn]
    print (sum x)
   

Writing Programs

To write a program in Haskell we write a main function.

main :: IO ()
main = putStrLn "Hello world!"

main always:

• Takes no arguments
• Returns an IO type.

To run the program, we first need to compile it:

 $ ghc -dynamic hello.hs 
[1 of 1] Compiling Main ( hello.hs, hello.o )
Linking hello ...
 $ ./hello

As I am running arch Linux with dynamically linked libraries I must use the -dynamic flag when compiling. For distros with static libraries this is not required.

Command Line Arguments

Most command line programs take arguments:

• getArgs :: IO [String] returns those arguments.
• This function is in System.Environment

import System.Environment

main :: IO ()
main = do
    args <- getArgs
    let output = "Command line arguments: " ++ show args
    putStrLn output

This function will return the command line arguments as a list of strings.

Looping in IO Code

The only way to loop in IO code is to use recursion.

printN :: String -> Int -> IO ()

printN _ 0 = return ()
printN str n =
    do
        putStrLn str
        printN str (n-1)

This program will write back a given string n times to separate lines.

• No variables.
• No loops.

Using Command Line Arguments

import System.Environment
main :: IO ()
main = do
    args <- getArgs
    let n = read (args !! 0) :: Int
    printN (args !! 1) n

 $ ./repeat_string 3 hello
hello
hello
hello

File IO

readFile will read the contents of a file:

readFile :: String -> IO String

Suppost that example.txt contains:

line one
line two
line three

> readFile "example.txt"
"line one\nline two\nline three\n"

writeFile writes a string to a file.

writeFile :: String -> String IO ()

The file will be overwritten!

> writeFile "output.txt" "hello\nthere\n"

The file output.txt will then contain:

hello
there

Finishing the marks.csv Example

We wrote the report function in Lecture 18-1. Now we can turn it into a program:

import System.Environment
main :: IO ()
main = do
    args <- getArgs
    let infile = args !! 0
        outfile = args !! 1
    input <- readFile infile
    writeFile outfile (report input)

Exercises

1.  import System.Environment
    main :: IO ()
    main = do
        args <- getArgs
        infile <- readFile (args !! 0)
        let string = (lines infile) !! 0
        putStrLn string
   

2.  import System.Environment
    main :: IO ()
    main = do
        args <- getArgs
        let num = read (args !! 0) :: Int
        putStrLn $ show (num + 1)
   

3.  main :: IO ()
    main = do
        putStrLn "Write a line of text to be written to output.txt."
        string <- getLine
        writeFile "output.txt" (string ++ ['\n'])
   

   Remember to end files with \n so that they are read properly.

Writing IO Code

We can write our own IO actions:

print_two :: String -> String -> IO ()
Print_two s1 s2 = putStrLn (s1 ++ s2)

> print_two "abc" "def"
abcdef

Note that the return type is IO ().

Combining Multiple IO Calls

The do syntax allows us to combine multiple IO actions.

get_and_print :: IO ()
get_and_print =
    do
        x <- getLine
        y <- getLine
        putStrLn (x ++ " " ++ y)

This syntax allows us two write a sequence of statements that will be executed in order.

You could also write this with the following syntax:

get_and_print :: IO ()
get_and_print = do
    x <- getLine
    y <- getLine
    putStrLn (x ++ " " ++ y)

The do Syntax

A do block has the following syntax:

do
    v1 <- [IO action]
    v2 <- [IO action]
    ...
    vk <- [IO action]
    [IO action]

• v1 through vk unbox the results of IO actions.
• The final IO action is the return value.

The v <- portion can be skipped if you are using an IO action purely for the side effect.

let in do Blocks

let expressions can be used inside do block in order to complete pure computations:

add_one :: IO ()
add_one =
    do
        n <- getLine
        let num = (read n) :: Int
            out = show (num + 1)
        putStrLn out

In a do block you can type anything out that you would type into the command line of GHCI.

if in do Blocks

guess :: IO ()
guess = do
    x <- getLine
    if x == "42"
        then putStrLn "Correct!"
        else putStrLn "You are very wrong."

Both branches of the if mut have the same type.

do Blocks

do blocks let you sequence multiple actions:

• Works with IO actions.
• Will not work in pure functional code.

Functional programs consist of:

• A small amount of IO code.
• A large amount of pure functional node.

Don’t try to write your entire program in IO code.

Putting Values in the IO Box

Sometimes we need to pus a pure value into IO.

• We can use the return function to do this.

> :t "hello"
"hello" :: [Char]

> :t return "hello"
IO [Char]

example :: IO String
example = do
    x <- getLine
    return (tail x)

You must use return to get the value out of an impure function.

print_if_short :: String -> IO ()
print_if_short str =
    if length str <= 2
        then putStrLn str
        else return ()

Both sides of the if must have the type IO ():

• So we use return () in the else part.

return

This function is not the same as in imperative languages return does not stop execution. It just convert pure values to IO values.

Monad

The type of return mentions monads.

> :t return
return :: Monad m => a -> m a

This is because IO is a monad.

• Whenever you see Monad m => substitute IO for m.
• So return :: a -> IO a

You don’t need to know anything about monads for COMP105.

Exercises

1.  doubleEcho :: IO ()
    doubleEcho = do
        x <- getLine
        putStrLn x
        putStrLn x
   

2.  firstWord :: IO ()
    firstWord = do
        string <- getLine
        if (words string) == []
            then putStrLn ""
            else putStrLn (head . words $ string)
   

3.  printEven :: Int -> IO ()
    printEven x = if (even x) 
        then (putStrLn x)
        else return ()
   

   This doesn’t need to be done in a do block as it is just one line.

So far, we have studied pure functional programming. Pure functions:

• Have no side effects.
• Always return a value.
• Are deterministic.

All computation can be done in pure functional programming.

IO

Sometimes programs need to do non-pure things:

• Print something to the screen.
• Read or write a file.
• …

IO v.s. Pure Functional

graph LR
IO --> p[Pure Functional]
p --> IO

• Impure IO code talks to the outside world.
• Pure functional code does the interesting computation.
• IO code can call pure functions; pure functions cannot call IO.

We can call the “functions” that complete IO: IO actions. This is because they are not functions.

getLine

getLine read a line of input from the console.

> getLine
hello there
"hello there"

> :t getLine
getLine :: IO String

The IO Type

This type marks a value as being impure.

If a function returns an IO type then it is impure:

• It may have side effects.
• It may return different values for the same inputs.

The IO type should be thought of as a box:

• The box hold a value from an impure computation.
• we can use <- to get an impure value from the IO type.

> x <- getLine
Hello
> x
"Hello"

Values must be unboxed before you use them in a pure function.

getChar

This function is similar to getLine but returns a single Char instead of a string.

putStrLn

This IO action prints a string onto the console.

> putStrLn "Hello"
Hello

There are no quotation marks as we are seeing this being written to the StdOut and not via read.

> :t putStrLn
putStrLn :: String -> IO ()

The unit type has the IO type indicating that it has a side effect.

The Unit Type

The unit type is a type represented by (). It only has one value which is itself.

This is used to indicate that nothing interesting is returned. An example of this is with putStrLn where is doesn’t return a value but does have the side effect of printing to the StdOut.

Exercise

1. It will ask for two lines. It will then print out the two lines with a space between them back to the StdOut.
2. It will read in a line with the expectation that there will be a number on it. It will then convert the line into an Int and print out the number + 1.
3. Error due to mismatched types. putStrLn expects a String but an IO type was given.

Trees

graph TD
a[ ] --> b[ ]
a --> c[ ]
b --> d[ ]
b --> e[ ]
d --> f[ ]
d --> g[ ]
c --> h[ ]
c --> i[ ]

A tree is composed of:

• Leaf nodes.
  • Leaves have no children.
• Branch nodes.
  • Has a child which is a leaf.

A Tree Type in Haskell

Any binary tree can be represented in this data type.

data Tree = Leaf | Branch Tree Tree deriving(Show)

graph TD
a[ ] --> b[ ]
a --> c[ ]
c --> h[ ]
c --> i[ ]

Branch Leaf (Branch Leaf Leaf)

Recursion on Trees

We can write recursive function that process tress.

• Usually the recursive case will process both branches.

This function counts all the nodes in a tree:

size :: Tree -> Int

size (Leaf) = 1
size (Branch x y) = 1 +size x + size y

For trees usually the base case is the Leaf and the recursive rule operates on the two sub-trees of the branch node.

> size (Branch Leaf (Branch Leaf Leaf))
5

Trees with Data

Nodes in a tree often hold data.

graph TD
9 --> 4
4 --> 1
4 --> 6
1 --> 10 
1 --> 7
2 --> 3 
2 --> 0
9 --> 2

Type of Trees with Data

This type allows each branch and leaf to have data of a single type associated with it:

data DTree a = DLeaf a
             | DBranch a (DTree a) (DTree a)
             deriving (Show)

graph TD
1 --> 7
7 --> 2 
7 --> 9
1 --> 4

DBranch 1 (DBranch 7 (DLeaf 2) (DLeaf 9)) (DLeaf 4)

Recursion on Trees with Data

This function adds together the numbers from all the branches and leaves in a tree with data.

tree_sum :: Num a => DTree a -> a

tree_sum (DLeaf x)       = x
tree_sum (DBranch x 1 l) = x + tree_sum l + tree_sum r

> tree_sum (DBranch 1 (DBranch 7 (DLeaf 2) (DLeaf 9)) (DLeaf 4))
22

Example - Fibonacci Numbers

Before we used this code to calculate the Fibonacci numbers. This is slow due to the large amount of branching:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

graph TD
A[fib 4] --> B[fib 3]
A --> C[fib 2]
B --> D[fib 2]
B --> E[fib 1]
D --> F[fib 1]
D --> G[fib 0]
C --> H[fib 1]
C --> I[fib 0]

How many recursive calls does the code make?

We can make a function to build the call tree.

fib_tree :: Int -> Tree

fib_tree 0 = Leaf
fib_tree 1 = Leaf
fib_tree n = Branch (fib_tree (n-1)) (fib_tree (n-2))

> fib_tree 4
Branch (Branch (Branch Leaf Leaf) Leaf) (Branch Leaf Leaf)

This is the same structure as the tree at the top of the example.

To count the nodes in this tree we can use the function size from earlier:

fib_calls n = size (fib_tree n)

> fib_calls 10
177
> fib_calls 20
21891
>fib_calls 30
2692537

As we can see multiple recursion can be very slow if used incorrectly.

Example - Finding a File

Suppose that we have a directory structure:

graph TD
h["~/"] --> d["docs/"]
d --> a[a.txt]
d --> b[b.txt]
h --> c[c.txt]

Write a function that, given a filename, finds the path to that file.

We can formulate the files as a data tree:

let fs =
    DBranch "~/"
        (DBranch "docs/" (DLeaf "a.txt" ) (DLeaf "b.txt"))
        (DLeaf "c.txt")

This is the same as the DTree above.

Note that the file might not exist:

• So we will use the maybe type.

> find_file "a.txt" fs
Just "home/docs/a.txt"

> find_file "d.txt" fs
Nothing

Implementation

find_file file (Dleaf x)
    | x == file = Just file
    | otherwise = Nothing
    
find_file file (DBranch x l r) =
    let
        left  = find_file l
        right = find_file r
    in
        case (left, right) of
            (Just y, _) -> Just (x ++ y)
            (_, Just y) -> Just (x ++ y)
            (_, _)      -> Nothing

This implementation has two cases, one for the leaf and one for the branch.

Exercises

1.  leafSum :: DTree Int -> Int
    leafSum (DLeaf x)       = x
    leafSum (DBranch _ l r) = leafSum l + leafSum r
   

2.  treeElem :: Eq a => a -> DTree a -> Bool
    treeElem x (DLeaf y) = x == y
    treeElem x (DBranch y l r) = (x == y) || treeElem x l || treeElem x r
   

Recursive Types

We have seen types which contain other types. In a recursive custom type, some constructors contain the type itself.

data IntList = Empty | Cons Int IntList deriving(Show)

Some examples using this type:

Empty -- []
Cons 1 (Empty) -- [1]
Cons 1 (Cons 2 Empty) -- [1,2]

Here is a more general list using a type variable:

data List a = Empty | Cons a (List a) deriving(show)

This is the same as the previous example but using any type (provided that it is the same type all the way through the list). To use this as an infix operator like : you would do the following:

> 1 `Cons` (2 `Cons` Empty)
Cons 1 (Cons 2 Empty)

Functions with Recursive Types

We can write functions for our custom list type:

our_head :: List a -> a

our_head Empty		= error "Empty list"
our_head (Cons x _)	= x

This takes the first item in our custom list type and prints it.

To get the tail you would use this function:

our_tail :: List a -> List a

our_tail Empty		= error "Empty list"
our_tail (Cons _ x)	= x

Recursing on Recursive Types

We can also write recursive functions to process our recursive types. This is exactly the same as recusing on a list:

our_sum :: List Int -> Int

our_sum Empty 		= 0
our_sum (Cons x xs) = x + our_sum xs

Custom Lists

Here is a new list type that can contain two different types.

data TwoList a b = TwoEmpty
				| ACons a (TwoList a b)
				| BCons b (TwoList a b)
					deriving(show)

This is the type when making a list that contains a Char and a Bool:

> :t 'a' `ACons`(False `BCons` TwoEmpty)
TwoList Char Bool

This is not the same as a list with tuples as the next item in the list can be of type a or type b not of both all the time. There is a cost also as you have to explicitly say if it is type a or type b.

Exercises

1.  ourElem :: Eq a => List a -> a -> Bool
    ourElem Empty _ = False
    ourElem (List x xs) y
        | x == y 	= True
        | otherwise = ourElem xs
   

2.  ourRange :: Int -> List Int
    ourRange 0 = Empty
    ourRange x = Cons x (ourRange (x - 1))
   

3.  data ThreeList a b c = ThreeEmpty
                         | ACons a (ThreeList a b c)
                         | ACons b (ThreeList a b c)
                         | ACons c (ThreeList a b c)
                         deriving(show)
   

Maybe

data Maybe a = Just a | Nothing

> :t Just "hello"
Maybe [Char]
> :t Just False
Maybe Bool
> :t Nothing
Maybe a

From here you can see that when you call the Just constructor you force the type variable a to be a particular type and if you call Nothing then no type is assigned to a.

The Maybe type is used in pure functional code that might fail.

safe_head [] = Nothing
safe_head (x:_) = Just x

> safe_head [1,2,3]
Just 1 
> safe_head []
Nothing

Given that the function will always give an output this means that it wont give an exception and crash the program.

Example

safe_get_heads list =
    let
        mapped = map safe_head list
        filtered = filter (/=Nothing) mapped
        unjust = (\ x -> case x of Just a -> a)
    in
        map unjust filtered

> safe_get_heads [[],[1],[2,3]]
[1,2]

This code will not crash in the event that an empty list is given to head.

Exceptions in Haskell

Haskell does include support for exceptions

> head []
*** Exception: Prelude.head: empty list

Exceptions are not pure functional:

• Every function returns exactly one value.
• You can’t catch exceptions in pure functional code.
• Exceptions are mostly used in IO code.

The Maybe type provides a way to do exception-like behaviour in pure functional code.

Can this function fail for some inputs?

• Use the Maybe type.

Exceptions should only be used in IO code:

• File not found, could not connect to server, etc.
• These are unpredictable events.

Either

data Either' a b = Left a | Right b

> :t Left 'a'
Either Char 'b'
> :t Right 'b'
Either a Char

The Either type is useful if you want to store different types in the same list:

is_left (Left _)    = True
is_left _           = False

> let list = [Left "one", Right 2, Left "three", Right 4]
> map is_left list
[True,False,True,False]

Example - Filtering off Left

get_lefts list = 
    let
        filtered = filter is_left list
        unleft = (\ (Left x) -> x)
    in
        map unleft filtered

> get_lefts list
["one","three"]

Example - Squaring Mixed Number Types

square (Left x) = Left (x ** 2)
square (Rightx) = Right (x ^ 2)

> let nums = [Left pi, Right (4::Int), Left 2.7182]
> map square nums
[Left 9.86,Right 16,Left 7.38]

Meaningful Error Messages

Either can also be used to give detailed error messages.

safe_head_either []     = Right "empty list"
safe_head_either (x:xs) = Left x

> safe_head_either []
Right "empty list"
> safe_head_either [1,2,3]
Left 1

This is required as a function can’t return values of two different types.

Exercises

1.  safeTail :: [a] -> Maybe [a]
    safeTail []     = Nothing
    safeTail x:xs   = Just xs
   

2.  safeDiv :: Int -> Int -> Maybe Int
    safeDiv _ 0 = Nothing
    safeDiv x y = Just (div x y)
   

3.  safeGet :: [a] -> Int Either a String
    safeGet x y
        | x < 0 = Right "Negative index."
        | length x <= y = Right "Index too large."
        | otherwise = Left (x !! y)
   

Parameterised Custom Types

Type Variables in Custom Types

We can use type variables in custom types:

data Point a = Point a a

Here we say we are making a new type where the constructor point is made of type a.

> :t Point (1::Int) (2::Int)
Point Int

We can also use multiple variable in the same type.

data Things a b c = Things a b c deriving (Show)

> Things "string" 1 True
Things "string" 1 True

When using a type that includes type variables the resultant type has its own type based on the types of data it was given. This links to how you can’t compare lists of two different types.

We can write functions using these types:

first_thing (Things x _ _) = x

> first_thing (Things 1 2 3)
1
> :t first_thing
first_thing :: Things a b c -> a

case Expressions

case expressions allow you to do pattern matching inside of functions.

data Example = One Int | Two Float

f :: Example -> Int
f x = case x of One a -> a
                Two b -> 0

> f (One 3)
3
> f (Two 4.0)
0

Example

Using case you can write functions that formerly would have been implemented in pattern matching:

f [] = 0 
f (x:xs) = 1 + f xs

f' list = case list of  []      -> 0
                        (x:xs)  -> 1 + f xs

Syntax

The syntax for a case expression is:

case [expression] of    [pattern 1] -> [expression]
                        [pattern 2] -> [expression]
                        ...
                        [pattern k] -> [expression]

All patterns should be on the same column in order for Haskell to process the expression correctly.

Additionally you can use the _ as a catch all at the end of the expression.

You can put them all on one line using the following syntax:

case x of {One a -> a; Two b -> 0}

Finally case is an expression so you can treat its result as a value:

> (case 1 of 1 -> 1) + (case 2 of 2 -> 1)
2

Exercises

1.  data BigThings a b c d = BigThings a b c d derive Show
   

2.  middleTwo :: BigThings a b c d -> (b, c)
    middleTwo (BigThings _ x y _) = (x, y)
   

3.  data Example = One Int | Two Float
    isOne :: Example -> Bool
    isOne x = case x of One _ -> True
                        _     -> False
   

More Complex Custom Types

More Complex Constructors

More complex constructors can contain other types.

data Point = Point Int Int deriving (Show, Read, Eq)

This is saying that the type Point has one constructor called Point and in that constructor there are two Int. The constructor name has no relation to the type name.

It is common that if your type has only one constructor to call constructor the same name as the type.

> Point 1 4
> Point 1 4

> read "Point 10 10" : Point
> Point 10 10

> Point 2 2 /= Point 3 1
> True

It is also common to use pattern matching to work with complex constructors:

shift_up (Point x y) = Point x (y +1)

> shift_up (Point 1 1)
> Point 1 2

> :t shift_up
> shift_up :: Point -> Point

Example

This example completes a computation using almost entirely our own custom types. We are also using pattern matching on our types:

move :: Point -> Direction -> Point

move (Point x y) North = Point x (y+1)
move (Point x y) South = Point x (y-1)
move (Point x y) East = Point (x+1) y
move (Point x y) West = Point (x-1) y

> move (Point 0 0) North
> Point 0 1

More Complex Constructors Continued

Types can have multiple constructors each of which can have their own types:

data Shape = circle Float | Rect Float Float deriving (Show)

> :t Circle 2.0
> Circle 2.0 :: Shape

> :t Rect 3.0 4.0
> Rect 3.0 4.0 :: Shape

Example

area :: Shape -> Float

area (Circle radius) = pi * radius ** 2
area (Rect x y) = x * y

> area (Circle 2.0)
> 12.56371

> area (Rect 3.0 4.0)
> 12.0

Records

You can use data types to build custom records:

data Person = Person String String Int String

get_first_name	(Person x _ _ _) = x
get_second_name	(Person _ x _ _) = x
get_age		(Person _ _ x _) = x
get_nationality	(Person _ _ _ x) = x

> get_age (Person "joe" "bloggs" 25 "UK")
> 25

Record Syntax

To make things easier, Haskell provides a record syntax:

data Person = Person {	firstName :: String,
			secondName :: String,
			age :: Int,
			Nationality :: String}
			deriving (Show)

> Person "joe" "bloggs" 25 "UK"
> Person {firstName = "joe", secondName = "bloggs", age = 25, nationality = "UK"}

This is similar to the previous example where we made our own record type.

Records can be created out of order, whereas normal data types cannot.

data Example = Example {a :: String,
						b :: Int}
						deriving (Show)

> Example "one" 2
> Example {a = "one", b = 2}

> Example {b = 3, a = "zero"}
> Example {a = "zero", b = 3}

If you create an out of order function then you should put them in {} with their labels so that Haskell can identify them.

Example

This example takes a co-ordinate Point to locate the shape in 2D space.

data AdvShape = AdvCircle Point Float | AdvRect Point Point deriving (Show)

area' (AdvCircle _ radius) = pi * radius ** 2
area' (AdvRect (Point x1 y1) (Point x2 y2)) =
	let
		w = abs (x1 - x2)
		h = abs (y1 - y2)
	in
		fromIntergral (w * h)

Exercises

1.  data Point = Point Int Int deriving (Show, Read, Eq)
    distance :: Point -> Int
    distance (Point x y) = x + y
   

2.  data HTTPResponse 	= Data Int String 
                | Error String
                deriving (Show, Read, Eq)
   

3.  data Student = Student {name :: String
                address :: String
                marks :: [Int]
                }
                deriving (Show, Read, Eq)
   

Custom Types

There are two ways to make types in Haskell.

The type Keyword

The type keyword gives a new name to an existing type.

• All types must start with capital letters.

type String' = [Char]

exclaim :: String' -> String'
exclaim str = str + "!"

> exclaim "hello"
> "hello!!

Type is useful when you want to give a meaningful name to a complex type.

type VoteResults = [(Int,String)]

results :: VoteResults

The data Keyword

The data keyword is used to create an entirely new type.

data Bool' = True | False

• | should be read as OR.
• Each of the values is a constructor.
  • Each constructor should start with a capital letter.

To find out more about a type you can use the GHCI :info command. For more information about a type constructor then you can use the type command.

Example

data Direction = North | South | East | West

rotate North = East
rotate East = South
rotate South = West
rotate West = North

> :t rotate
> rotate :: Direction -> Direction

Type Classes

By default, a new data type is not part of any type class. This means that running rotate will give an error. As is GHCI doesn’t know how to show it.

We can use the deriving keyword to fix this:

data Direction = North | South | East | West deriving (Show)

This will automatically put the type into the class Show and will allow it to print to the prompt.

Hakell can automatically implement the following type classes:

• Show
  • Will print out the type as it is in the code.
• Read
  • Will parse the type as it is in the code.
• Eq
  • The natural definition of equality.
• Ord
  • Constructors that come first are smaller.

You can add these to the tuple that deriving takes as input. You should include all type classes that make sense for your type so that you can use the functions you want.

Exercises

1. type Marks = (String, [Int])
2. data Colour = Red | Blue | Green deriving (Show, Read)

3.  toRGB :: Colour -> (Float, Float, Float)
    toRGB Red = (1,0,0)
    toRGB Green = (0,1,0)
    toRGB Blue = (0,0,1)
   

   You should note that as this type isn’t in the class eq then you can’t use guard and equality testing on it.

First Past the Post Example

This example covers a first past the post election. This means whoever gets the most votes wins. We are aiming to make a function that performs this task:

> winner ["red", "blue", "red", "red", "green"]
> "red"

Getting the Candidates

First we need to figure out who the candidates are:

uniq [] = []
uniq (x:xs) = x : uniq (filter (/=x) xs )

This function will remove duplicates from a list of strings. For every new element found the filter will remove all further occurrences from the rest of the list before recursing on the list.

Counting the Votes

This function counts the number of votes for a particular candidate:

count x list = length (filter (==x) list)

Vote Totals

This function will count all the votes for each candidate and put the number of votes and then the candidate in a list of tuples.

total votes = 
	let
		candidates = uniq votes
		f = (\ c -> (count c votes, c))
	in
		map f candidates

Comparing Candidates

Tuples are compared lexicographically. This means that each element is compared in turn to find which satisfies the function.

> max (3, "red") (2, "blue")
> (3,"red")

This means that if two candidates have the same number then the string is compared.

maximum

The function maximum takes a list and returns the largest item in the list:

> maximum [(3, "red"), (2, "blue"), (4, "green")
> (4, "green")

Finding the Winner

snd returns the second value in a tuple:

winner votes = snd . maximum . totals $ votes

Applying this satisfies the requirement:

> winner ["red", "blue", "red", "red", "green"]
> "red"

Alternative Vote Example

In the alternative vote system, voters rank the candidates:

• In each round, the candidate with the least number of first preference votes is eliminated.
• The winner is the last candidate left once all other have been eliminated.

> let votes = [["red", "blue", "green"],
				["blue", "green"],
				["green", "red"],
				["blue", "red"],
				["red"]]
> av_winner votes
> "red"

You don’t need many preferences and each list is a single person’s preferences.

See the slides for full examples.

Ranking the Candidates

sort sorts all of the items in a list and orders them from smallest to biggest.

Getting the First Choice Votes

head doesn’t accept empty lists as input. This should be taken into account when removing items from lists unevenly.

Final Function

All of the components give this function:

av_winner votes =
	let
		ranked = rank_candidates votes
		first = head ranked
	in
		if length ranked == 1
		then first
		else av_winner (remove_cand first votes)

Marks to Report Example

This lecture covers a mini assignment example about converting a csv file containing students marks into a report containing the students averages. These are presented in the following format:

aaa		70	65	67	60
bbb		55	60	55	65
ccc		40	40	40	40
ddd		80	60	75	60
ccc		0	0	0	100

And should be transformed to be:

aaa		65.5
bbb		58.75
ccc		40.0
ddd		68.75
ccc		25.0

See the slides for the full examples.

Reading files in Haskell

We can read a file using readFile:

• This is an IO function.
• We will study this in more detail later on.

> readfile "marks.csv"
> "aaa		70	65	67	60\nbbb		55	60	55...

The \n character is the newline character.

lines

The lines function takes a string containing multiple lines into a list of strings. The complement to this function is the function unlines. This will do the opposite.

Parsing the File

Using the functions words and lines we can put the file into a list of lists of strings, in order to process the file.

Getting the Averages

The function read will convert a string into a float.

Writing the Output File

The function writeFile will write some data into a file:

> writeFile "test.txt" "hello"

This is not a pure function and we will see it again later.

All in One Function

The pure function portion of the exercise will read as the following:

report file = 
	let
		parsed		= map words . lines $ file
		students	= map name parsed
		averages	= map average parsed
		zipped		= zipWith report_line students averages
	in
		unlines zipped

More Higher Order Functions - Continued

takewhile

This function takes while a condition is true.

> takeWhile (<=5) [1..10]
> [1,2,3,4,5]

This is different to filter which only removes individual elements.

> takeWhile (\ x -> length x <= 2) ["ab","cd","efg"]
> ["ab", "cd"]

Implementation

takeWhile' :: (a -> Bool) -> [a] -> [a]

takeWhile' _ [] = []
takeWhile' f (x:xs)
	| f x = x : takeWhile' f xs
	| otherwise = []

dropWhile

This is the opposite of the previous function:

> dropWhile (==1) [1,1,2,2,3,3]
> [2,2,3,3]

You can also use functions:

> dropWhile (\ x -> x < 10 && x > 0) [1,2,3,10,4,5]
> [10,4,5]

Implementation

dropWhile' :: (A -> Bool) -> [a] -> [a]

dropWhile' _ [] = []
dropWhile' f (x:xs)
	| f x = dropWhile' f xs
	| otherwise = x:xs

takeWhile & dropWhile Example

This function splits up the words in a string into a list of strings containing no spaces.

split_words "" = []
split_words string =
	let
		first = takeWhile (/= ' ') string
		up_to_space = dropWhile (\= ' ') string
		after_space = dropWhile (== ' ') up_to_space
	in
		first : split_words after_space

> split_words "one two		three"
> ["one","two","three"]

words

The function that was made in the last example has a standard implementation called words.

unwords

This is the companion function to words. They aren’t quite inverses as unwords will put spaces inbetween each word.

zipWith

This function zips two lists together using a function:

> zipWith (+) [1,2,3] [4,5,6]
> [5,7,9]

> zipWith (\ x y -> if x then y else -y) [True, False, True] [1,2,3]
> [1,-2,-3]

Implementation

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

Examples

mult_by_pos list = zipWith (*) list [0..]

> mult_by_pos [1,2,3]
> [0,2,6]

interleave str1 str2 = 
	let
		zipped = zipWith (\ x y -> [x,y]) str1 str2
	in
		concat zipped

> interleave "abc" "123"
> "a1b2c3"

In this example concat is used to make lists of strings into a single string.

Exercises

1.  getNumber string = takeWhile (\ x -> elem x ['0'..'9']) string
   

2.  wordCount string = length $ words string
   

3.  numberWords string = zip $ words string $ [1..]
   

More Higher Order Functions

Scan

The scan set of functions is similar to the fold set of functions. However instead of outputting a single value it outputs a list showing the accumulator at each step in the function:

> scanr (+) 0 [1,2,3,4]
> [10,9,7,4,0]

The function scanr is implemented like so:

scanr' :: (a-> b -> b ->) -> b -> [a] -> [b]

scanr' _ init [] = [init]
scanr' f init (x:xs) =
	let
		recursed = scanr' f init xs
		new = f x (head recursed)
	in
		new : recursed

Scan Variants

There are also left to right versions of scan:

> scanl (+) 0 [1..10]
> [0,1,3,6,10,15,21,28,36,45,55]

A good way to understand the accumulator in a fold is to do a scan and observe the output.

Fibonacci Example

fib_pairs n = scanl (\ (a,b _ -> (b,a + b)) (0,1) [1..n]
fib_to_n n = map fst (fib_pairs n)

> fib_pairs 3
> [(0,1),(1,1),(1,2)]

> fib_to_n 3
> [0,1,1]

Exercises

1.  prefixMaximum list = scanl1 max list
   

   As max is already a two argument function that takes acc and x, then we don’t have to make our own anonymous function.

2.  powersOfTwo n = scanl (\ acc _ -> 2 * acc) 1 [1..n]
   

Fold Continued

A fold output can be a different type to the input list.

to_csv list = foldr (\x acc -> show x ++ "," ++ acc)  "" list

> to_csv [1,2,3,4]
> "1,2,3,4,"

By using foldr you cannot get the desired outcome as it applies the same rule to every item in the list.

foldr1

The function foldr1 uses the final value of the list to initialise the accumulator:

foldr1 :: (a -> a -> a) -> [a] -> a

foldr1' _ [] = error "empty list"
foldr1' -[x] = x
foldr1' f (x:xs) = f x (foldr1' f xs)

> foldr1' (+) [1,2,3,4,5]
> 15

As the accumulator has the same type as the list elements foldr1 cannot have a different type to that of the elements in the list.

Example

maximum' list = foldr1 (\ x acc -> if x > acc then x else acc) list

> maximum [1,2,3,4,3,2,1]
> 4

In this example foldr1 is required as your initialisation may become the maximum value.

foldl

foldr processes lists from the right. The opposite of this is foldl which processes lists from the left. For many functions like + the ordering doesn’t matter but for other functions such as /.

Type of foldl

The function f has its type flipped compared to the other fold function:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b

This also means that you should swap your functions:

• foldr (\ x acc -> ...
• foldr (\ acc x -> ...

Example

reverse_list list = foldl (\ acc x -> x : acc) [] list

> reverse_list [1,2,3,4]
> [4,3,2,1]

Exercises

1. sumFsts list = foldr (\ (x,_) acc -> x + acc) 0 list
2. minimum list = foldr1 (\ x acc -> if x < acc then x else acc) list
3. dash string = foldl (\ acc x -> acc ++ [x, '-']) "" string

Fold

Some functions take lists and turn them into a single value. This type of computation is called a fold. The things that you can change are:

• The base case.
• The operation applied to the list.

foldr

foldr' :: (a -> b -> b) -> b -> [a] -> b

foldr' _ init [] = init
foldr' f init (x:xs) = f x (foldr' f init xs)

> foldr' (+) 0 [1..10]
> 55

> foldr' (*) 1 [1..10]
> 3628800

The Folded Function

sum'' list = foldr (\ x acc -> acc + x) 0 list

The folded function f takes two arguments:

• x is an element form the list.
• acc is the accumulator.

The function outputs a new value for the accumulator:

• The initial value for the accumulator is init.
• The final value for the accumulator is the output of foldr.

Example

foldr (\ x acc -> acc + x) 0 [1,2,3,4]

Values for the accumulator:

init	= 0
0 + 4	= 4
4 + 3	= 7
7 + 2	= 9
9 + 1	= 10

Final output: 10

An Imperative Equivalent:

foldr f init input_list

In python this would be implemented as:

acc = init
input_list.reverse()

for i in range(len(input_list)):
	acc = f(input_list[i], acc)

return acc

foldr Examples

Whenever you fold a binary operator you are putting that operator in-between each element on the list. If you are using foldr then you will put the initial value on the right hand side.

concat' list = foldr (++) [] list

> concat' ["Hello ", "there."]
> "Hello there."

all' list = foldr (&&) True list

> all' [True, True, True]
> True

length' list = foldr (\ _ acc -> acc + 1) 0 list

> length' [1,2,3,4]
> 4

This example shows that you just need to apply a function to the accumulator for each element in the list. It doesn’t need to be specifically including items in the list:

count_ones list = foldr (\ x acc -> if x == 1 then acc + 1 else acc) 0 list

> count_ones [1,1,2,3,1,4]
> 3

Exercises

1. any' list = foldr (||) False list
2. countEs string = foldr (\ x acc -> if x == 'e' then acc + 1 else acc) 0 string
3. sumOfEvens list = foldr (\ x acc -> if even x then acc + x else acc) 0 list

filter

filterkeeps only the elements for which f returns True.

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' f (x:xs)
	| f x 		= x : rest
	| otherwise	= rest
	where rest 	= filter' f xs
	
filter' even [1..10]
> [2,4,6,8,10]

In comparison to map which applies a function to each element in a list. filter will apply a boolean test to each element in the list and if it fails it will remove the element from the list.

Combining map & filter

square_even :: [Int] -> [Int]
square_even list = map (^2) (filter even list)

square_even [1..10]
> [4,16,36,64,100]

Higher Order Programming

map and filter are examples of higher order programming. This style:

• De-emphasises recursion.
• Focuses on applying functions to lists.
• Are available in imperative languages (Python C++).

There is a whole family of higher order programming functions available in Haskell.

Exercises

1. onlyDiv3 = filter (\x -> mod x 3 == 0)
2. onlyLower = filter (\x -> elem x ['a'..'z'])
3. noEven = map (filter odd)

map

map applies a funciton f to every element in a list.

map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x : map' f xs

This saves you from writing out the generic code for applying a function to a list. This allows you to implement the standard functions instead of having to make your own.

map even [1..5]
> [False,True,False,True,False]

This avoids writing a recursive function for applying simple list operations.

Currying and map

It is common to use curried functions with map:

map (*2) [1..5]
> [2,4,6,8,10]

You can also use map to make other functions:

doubleList = map (*2)

> doubleList [1..5]
> [2,4,6,8,10]

Anonymous Functions and Map

It is also common to use an anonymous functions with map:

map (\x -> x * x) [1..5]
> [1, 4, 9, 16, 25]

This lets you apply your own functions to a list without having to define it.

Nested Maps

When working with nested lists, it is common to use nested maps.

map(map (*2)) [[1,2,3],[4,5,6],[7,8]]
> [[2,4,5],[8,10,12],[14,16]]

import Data.Char

map (map toUpper) ["the","quick","brown"]
["THE","QUICK","BROWN"]

This application uses currying in the inner map. It is also especially useful for lists containing strings.

Exercises

1. cubeList = map (^3)
2. middleElem = map (\ (_,x,_) -> x)
3. ruinStrings = map (map (\ x -> if x == 'e' then 'x' else x))

Anonymous Functions

Sometimes is it convenient to define a function inline. Anonymous functions allow you to use a function without a name.

> (\ x -> x + 1) 7
> 8

This allows you to pass functions to a higher order function without giving it a name:

> apply_twice (\ x -> 2 * x ) 2
> 8

Syntax

The syntax for an anonymous function is:

\ [arg1] [arg2]  ... -> [expression]

The \ is supposed to resemble an lambda $\lambda$.

• Anonymous function are sometimes called $\lambda$-functions in recognition of lambda calculus.

Functions that Return Functions

Higher order functions can also return other functions:

f_than_adds_n :: Int -> (Int -> Int)
f_that_adds_n n = (\x -> x + n)

> let f = (f_that_adds_n 10) in (f 1)
> 11

This function returns another function that you can use in other functions.

Higher order function can take and return functions:

swap f = \ x y -> f y x

This is a two argument function and then swaps the arguments for the function.

g = swap take

This has swapped the arguments for the function take and can be called with g

Currying Revisited

Previously we’ve seen that it is possible to partially apply a function:

add_two = (+2)

This is just a nicer syntax for a function that returns a function:

add_two = (\ x -> x + 2)

Exercises

1.  (\ x y -> x + y)
   

2.  addChar c = (\ string -> string ++ [c])
   

3.  curry' :: ((a, b) -> c) -> (a -> b -> c)
    curry' f = (\ x y -> f (x, y))
   

Higher Order Functions

A higher order function is a function that:

• Takes another function as an argument.
• Returns a function.

apply_twice :: (a -> a) -> a -> a
apply_twice f input = f (f input)

> apply_twice tail [1,2,3,4]
> [3,4]

This function takes a function and an input as an argument and then uses the supplied function twice on the supplied argument.

An example including currying (partial application):

> apply_twice (drop 2) [1,2,3,4,5]
> [5]

A caveat of using this function is that it must return the same type that is is given.

Function Composition

Function composition applies one function to the output of another

• Composing f with g input gives f (g input)

compose :: (b -> c) -> (a -> b) -> a -> c
compose f g input = f (g input)

> compose (+1) (*2) 4
> 9

This is the same thing as applying a function to another function.

The . Operator

The type of . is:

(.) :: (b -> c) -> (a -> b) -> a -> c

The . operator is an infix operator called compose. To complete the same action as will the compose function write:

> ((+1) . (*2)) 4
> 9

This means to apply the left function on the argument and then the right function on the result of the previous function.

f list = length (double (drop_evens (tail list)))

f' list = (length . double . drop evens . tail) list

As you can see from the two different implementations; the use of . removes the need for nested brackets, however:

• It is stylistic.
• You never need to use .
• It is preferred.

The $ Operator

evaluate :: (a -> b) -> a -> b
evaluate f input = f input

The $ operator is exactly the same as evaluate. $ is infix.

The $ operator has the lowest precedence of any operator. As a result it can be used in place of brackets:

((*2) . length) [1,2,3,4]
(*2) . length $ [1,2,3,4]

length ([1,2,3] ++ [4,5,6])
length $ [1,2,3] + [4,5,6]

Exercises

1.  applyThrice :: (a -> a) -> a -> a
    applyThrice f x = f . f . f $ x
   

2.  f :: (Ord a, Enum a) => [a] -> a
    f x = succ . sum . tail . tail $ x
   

More Type Classes

show

This function converts other types to strings. However, it can only take the type class of Show into a string:

show :: Show a => a -> a

Show contains:

• All basic types.
• All tuples of show-able types.
• All lists of show-able types.

read

This converts strings to other types, provided they are formatted correctly:

read "123" :: Int

In this case the use of :: is necessary to tell Haskell what type the function should return.

In cases where type inference can be used, the :: is not required:

not (read "False")

The type of read is the type class Read:

read :: Read a => a -> a

Read contains:

• All basic types.
• All tuples of readable types.
• All lists of readable types.

Ordered Types

The type class to compare two objects by inequality is Ord. This is required for using functions such as >.

(>) :: Ord a -> a -> a -> Bool

All basic types can be compared including tuples and lists. Tuples and lists are compared lexicographically (similar to alphabetically ordering words).

Exercises

1. showTuple :: (Show a, Show b) => (a, b) -> [Char]
2. addThree :: (Num a, Read a) => String -> a
3. headLt10 :: (Num a, Ord a) => [a] -> Bool

Type Classes

Some functions are polymorphic, but can’t be applied to any type. + is a good example. It can work on float and integer but not on mixed types or Char. The type of + is:

(+) :: Num a => a -> a -> a

This means that a is a number in the definition: a -> a -> a.

Num

Num is a type class:

• It restricts the type variable a to only be number types.
• Word, Int, Integer, Float, Double are all contained in Num.
• Char, Bool, tuples and lists are not in Num.

Num Sub-Classes

Num has two sub-classes.

Integral represents whole numbers and contains:

• Word (un-signed integers)
• Int
• Integer

Fractional represents rationals and contains:

• Float
• Double
• Rational

Eq

The types in the class Eq are the types which can be compared with the function ==. There are no default types which aren’t equality testable but if you make your own type then you will have to add it to this class.

Type Class Syntax

The syntax of a class type is:

[Type class 1], [Type class 2], ...) => [Type]

This results in a declaration similar to the following:

equals_two :: (Eq a, Num a) => a -> a -> Bool
equals_two a b = a + b == 2

This type declaration also means that if you use functions like == in your function then you must specify that the type is comparable with Eq a. If you don’t then the compiler will give an error.

The Most General Type Annotation

The most general type annotation is the one that is least restrictive. Ideally you want your type annotation to be the most general without giving an error:

equals_two a b = a + b == 2

-- Too restrictive
equals_two :: Int -> Int -> Bool

-- Most general
equals_two :: (Eq a, Num a) => a -> a -> Bool

-- Too general (will give error)
equals_two :: a -> a -> Bool

The most general type annotation is the one which allows the most valid types

Numbers

In Haskell numbers, such as 10 have a polymorphic type:

10 :: Num p => p

This means that, unless stated explicitly that numbers will be converted to the most suitable type in the class of Num.

You can force a number to be a particular type by using the :: operator:

1 :: Integer
> 1
1 :: Float
> 1.0

The function fromIntegral will take any Integral type and convert it into a Num type. This, for example would allow you to use the / operator on an Integer:

fromIntegral (1 :: Int) / 2
> 0.5

Converting Floats to Integers

Converting floats to integers is a lossy operation. This means that you shoul choose how to complete the rounding:

ceiling 1.6
> 2

floor 1.6
> 1

truncate 1.6
> 1

round 1.6
> 2

Other Type Classes

There are many other type classes in Haskell that won’t be covered:

length :: Foldable t => t a -> Int

This that a should be accepted if it is a list.

If you see any of the following as a types:

• Functor
• Foldable
• Traversable

then think list.

Exercises

1. square_area :: Num a => a -> a -> a
2. triangle_area :: Fractional a => a -> a -> a
3. equal_heads :: Eq a => [a] -> [a] -> Bool

Polymorphic Types

Some functions accept many different types. An example of this is length which accepts many different types of lists.

if you ask what the type of then function length is then it will return the type:

length :: [a] -> Int

a is a type variable. This means that:

• The function can be applied to any list.
• a will represent the type of list elements.

This type is called polymorphism. This is a feature of functional languages.

Type Variables

In the function head it will return the type variable which it was given in the list. Hence asking for the type returns:

head :: [a] -> a

Type variables can appear more than once. These types specify that the return type will be determined by the type of the input.

Multiple type variables can be included in one declaration for example the function fst returns the following:

fst :: (a,b) -> a

As a result the types of function can tell you a lot about what the function does.

Type Annotations

Is it good practice to insert type annotations for your functions. This is so that Haskell assigns the types to your functions that you expect. You do this with the following syntax.

f :: Int -> Int
f x = x + 1

The annotation is usually place before the function definition. If you don’t give a type annotation, then Haskell will infer one for you based on the functions used in your function. This is a result of the language being strongly typed.

Annotating your function can make it easier to catch bugs. This will give the compiler more to work with and make errors more descriptive.

Exercises

1. take :: Int -> [a] -> [a]
2. (:) :: a -> [a] -> [a]
3. (++) :: [a] -> [a] -> [a]