This page covers the tutorials on Haskell and GpH in the course F21DP (C+MPI tutorials are here).

For the impatient, here is a quickstart link to get to the introductory Haskell exercises using the web-based IDE.

## Haskell Exercises Setup

**Table 1. Roadmap through the tutorials based on your experience with functional programming**

No Experience | Little Experience | Some Experience | |
---|---|---|---|

Get Started: | Haskell Basics on School of Haskell | Do the simple samples from the course | Do the tree exercises from the course |

Focus on: | Do the simple samples from the course | Do the tree exercises from the course | Continue with some Haskell exercises below |

Also cover: | Do the tree exercises from the course | Continue with some Haskell exercises below | Continue with the bridging exercises below |

To "do the exercises" go through the text on the web page, or comments in the source code, and complete the missing definitions mentioned there. You are also encouraged to slightly modify the sample sources (as an example check the sum-of-square examples).

Doing the Haskell exercises, you have a choice between two IDEs: a web-based one and a command-line-based-one (see Table 2 for details). A good way to get started with Haskell, is to use the web-based IDE at the School of Haskell, where you can also find an entire course on Introduction to Haskell. Do exercises from that course at your own pace to get a deep understanding of the concepts that were covered in class. Note that for the parallel Haskell exercises you will need to use the command-line based compiler/interpreter, rather than the web-based IDE!

**Table 2. Pick your IDE for doing the exercises**

Web based IDE | Haskell Interpreter | |
---|---|---|

Kind of IDE | Runs in a web browser | Runs from the command-line |

Advantages | Ease of use | Flexibility |

Useful for seq Haskell exercises | yes | yes |

Useful for par Haskell exercises | no | yes |

## Haskell Exercises

As explained above, pick either the web-based IDE or the `ghci` interpreter and `ghc` compiler,
installed on the lab machines, to do these exercises.
You will need ghc to compile, run and measure parallel Haskell programs later in the course and in particular
in your coursework.

- You are recommended to try the exercises from the slides (e.g. the simple examples and the sum-of-square examples) and to build up a file e.g.
`lab.hs`(see GHCi usage in a nutshell) using a text editor. - For anything more than one-liners, edit your
`lab.hs`file and`:reload`it in the interpreter. - Detailed documentation on using ghci is available here.
- Also check the Haskell section of the FAQ for help in getting started.

### Basic Haskell expressions

To get started, give Haskell expressions to

- multiply 4 and 5
- calculate the area of a circle with radius 4.7; define a constant for pi
- concatenate the strings ``Hello '' and ``World''

### Haskell sample sources

Download the sample sources for the simple examples and the sum-of-squares (from slides) and
try them in the interpreter (see this FAQ) or in the web-based IDE.
Check that all versions of `sqs_even` give the same result.

Download the sample sources for the tree example with exercises mentioned in class. Implement the remaining functions mentioned in the source file, and test them (see below).

### Basic Haskell functions

Now, write your own Haskell functions as specificied below.

- Write a Haskell function
`sumTill :: Int -> Int`, so that`sumTill n`calculates the sum of the numbers between`1`and (positive)`n`, e.g.sumTill 4 = 1 + 2 + 3 + 4 = 10

- Show how
`sumTill 3`reduces to 6

- Write a Haskell function
`fib :: Int -> Int`, so that`fib n`calculates the fibonacci number for`n`.`fib`of 0 or 1 is 1, otherwise`fib n = fib (n-1) + fib (n-2)`. Your function does not need to be efficient.

- Write a Haskell function
`prod:: [Int] -> Int`, so that`prod [x1, x2, .. xn]`returns the product of the elements of the list:`x1 * x2 * .. * xn` - Show how
`prod [3 .. 5]`reduces to 60. - Use a higher order function to write
`prodH`, with the same semantics as`prod`.

- Write a Haskell function
`positive:: Int -> Bool`, so that`positive n`is true if`n`is greater than 0, and false otherwise.

`elem :: Eq a => a -> [a] -> Bool`is a prelude function such that`elem x xs`is true if`x`occurs in the list`xs`, and false otherwise.

Use`elem`and a list comprehension to write a Haskell function`intersect :: Eq a => [a] -> [a] -> [a]`, so that`intersect xs ys`returns a list containing only those elements of`xs`that also appear in`ys`.

- Write a Haskell function
`powers:: Int -> [Int]`, so that`powers n`returns an infinite list Based on that function, write a Haskell expression to return the first 5 powers of 3

### Haskell data structures

In Haskell, we can define a binary tree as follows:

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

An example of a function over this tree data type is the function `fringe`
which collects all values in the leaves of the tree:

fringe :: Tree a -> [a] fringe (Leaf x) = [x] fringe (Branch left right) = fringe left ++ fringe right

Based on these definitions, implement the following functions:

- Implement a function
`depth :: Tree a -> Int`to compute the depth of the tree, ie. the longest path from the root of the tree to one of the leaves. - Using the
`depth`function, write a function`isBalanced :: Tree a -> Bool`that checks, whether a tree is balanced, ie. the lengths of any 2 paths in the tree does not differ by more than 1. - Write a Haskell function
`mkTree :: [a] -> Tree a`that constructs a balanced binary tree, containing the elements of a given list.**Hint:**Check the prelude function`splitAt`. - Use Haskell classes to overload the
`==`equality operator for trees doing compenentwise equality checks on both arguments.**Hint:**Check the slides for details on Haskell classes and overloading.

### Bridging Exercises

The following exercises are designed to help you with your coursework. By this point, you should have done all the introductory exercises above.

The highest common factor (hcf), or greatest common divisor (gcd), of
two numbers is the largest number that exactly divides them, e.g. the
hcf of 60 and 84 is 12. Euclid proposed an algorithm for finding the
hcf of two numbers `big` and `small`:

if small exactly divides big return small else return hcf small (remainder of big/small)For example

hcf 56 12 = hcf 12 (rem 56 12) = hcf 12 8 = hcf 8 4 = 4Write a Haskell

`hcf :: Integer -> Integer -> Integer`function.

Two numbers are relatively prime is their hcf is 1, e.g. 8 and 9 are
relatively prime, but 6 and 9 are not. Write a Haskell function
`relprime :: Integer -> Integer -> Bool`, that is true if it's arguments
are relatively prime, but false otherwise.

The Euler totient (or phi) function `euler n` is a count of how
many numbers less than `n` are relatively prime to `n`,
e.g. `euler 6` is 2 because 1 and 5 are relatively prime to 6.
Write a Haskell function `euler :: Integer -> Int` that calculates
the totient of it's argument.

Write a Haskell function `sumTotient :: Integer -> Integer -> Int`,
so that `sumTotient lower upper` calculates the sum of the
totients between lower and upper.

## Glasgow parallel Haskell (GpH) Exercises

The sections below show how to compile, run and profile Glasgow parallel Haskell programs. Follow these steps, and refer to the slides on GpH for detail. As usual, check the relevant section of the FAQ for help. There is further guidance on running Glasgow parallel Haskell programs on this page.

### Get sample sources

Pick up the sample sources from the slides, linked below:

- power_circ_par.hs,
- parsum.hs, (including documentation on how to compile and run)
- parfib.hs,
- parfact.hs,
- queens.hs
- foo.hs (simple list strategies)

### Sequential profiling

**Compile** the program like this to enable sequential time and heap profiling for all top-level functions:

ghc -O2 -rtsopts -prof -auto-all -o queens_prof queens.hs

Then **run** the program with these additional runtime flags, turning on profiling:

./queens_prof 12 +RTS -pT -hC

This will generate 2 files: `queens_prof.prof`, which is a text file with time profiling information similar to gprof; and a file `queens_prof.hp` that contains information about heap usage.
To **visualise** the latter do the following:

hp2ps queens_prof.hp evince queens_prof.psThis will generate and display a .ps file that shows heap usage, split by top-level function, over time.

### Parallel profiling

To enable parallel profiling on a program that uses evaluation strategies or explicit `par`s, compile like this:

ghc -O2 -rtsopts -threaded -eventlog -o parsum_thr_l parsum.hs

and run the program with these extra runtime options:

./parsum_thr_l 500M 900 +RTS -N6 -ls

This will generate a file `parsum_thr_l.eventlog` and you can visualise its
data by calling:

/home/pt114/.cabal/bin/threadscope parsum_thr_l.eventlog

### Parallel measurements

To compile for runtime measurements, turn on optimisation but turn off profiling:

ghc -O2 -rtsopts -threaded -o parsum_thr parsum.hs

To run on e.g. 6 cores over an input of 2 billion and print runtime statistics

time ./parsum_thr 2G 900 +RTS -N6

### Exercises

Then do the following exercises:

- The naive fibonacci program from
`parfib.hs`sparks a huge number of small grained tasks. Add a threshhold to reduce the number of sparks produced. - Produce a data parallel version of the
`queens.hs`program.**Hint 1:**you will need to use strategies.**Hint 2:**for performance measurement use a board of at least 12 * 12.**Hint 3:**there are several ways of parallelising the program, and you should explore which works best.

## Advanced GpH Exercises

Pick up this specification and to the GpH instance of the programming part (for the Milan15 course this is **not** and assessed coursework!).

## ParMonad exercises

- run the naive version of parfib and observe the performance
- implement thresholding in this version to improve performance
- pick-up the parsum.hs example from the GpH part, and rewrite it in ParMonad notation
- implement a parallel version of the Euler totient function, using the parallel map in ParMonad notation