Tutorial on Haskell and GpH

• Home
• Course structure
• Slides
• Coursework
• FAQ
• Reading List
• News

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.

1. 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.
2. For anything more than one-liners, edit your lab.hs file and :reload it in the interpreter.
3. Detailed documentation on using ghci is available here.
4. Also check the Haskell section of the FAQ for help in getting started.

Basic Haskell expressions

To get started, give Haskell expressions to

1. multiply 4 and 5
2. calculate the area of a circle with radius 4.7; define a constant for pi
3. 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.

1. 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
    

2. Show how sumTill 3 reduces to 6

1. 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.

1. 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
2. Show how prod [3 .. 5] reduces to 60.
3. Use a higher order function to write prodH, with the same semantics as prod.

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

1. 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.

1. 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

sample solutions

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:

1. 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.
2. 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.
3. 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.
4. 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.

sample solution

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
= 4

Write 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:

1. power_circ_par.hs,
2. parsum.hs, (including documentation on how to compile and run)
3. parfib.hs,
4. parfact.hs,
5. queens.hs
6. 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.ps

This 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 pars, 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:

1. 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.
2. 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

---