This lab covers more recursive functions over lists, the concept of parametric polymorphism, and how it can be used to write functions that operate on more general types than before. We will see some examples of custom recursive data types, and how to write recursive functions over them.

Don’t forget to submit all attempts at the exercises to git to receive your participation marks. The deadline will be the start of your next lab in week 7.

Table of Contents


Pre-lab Checklist

  • You should have finished and submitted Lab 5.
  • You are comfortable with writing functions using guards and case expressions.
  • You can write recursive functions over lists and numbers.
  • You are familiar with list patterns.

Getting Started

  1. Go to the project’s dashboard under the Project tab and click on the Fork button. The gitlab url for this lab is https://gitlab.cecs.anu.edu.au/comp1100/2024s2/2024s2studentfiles/comp1100-2024s2-lab06

  2. You will be asked where to fork the repository. Click on the user or group to where you’d like to add the forked project. You should see your own name here. Once you have successfully forked a project, you will be redirected to a new webpage where you will notice your name before > project-name. This means you are now the owner of this repository. The url in your browser should reflect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/comp1100-2024s2-lab06

  3. Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.

  4. Put your exercise solutions in the file Lab06.hs. This file is pre-filled with unfinished functions that match the exercises below.


Parametric Polymorphism

We’re going to be introducing a new topic, parametric polymorphism. Parametric polymorphism is when a function operates on values without depending on their underlying type, and so we can use such functions for many different types of inputs, rather than writing a function for each.

Parametric polymorphism is contrasted with ad-hoc polymorphism, which is where a function works for some types, but not others. We will see this later in Lab 10.

Consider the following function lengthListInt, that finds the length of a list of Integer.

lengthListInt :: [Integer] -> Integer
lengthListInt list = case list of
    [] -> 0
    x:xs -> 1 + lengthListInt xs

Suppose we also had some Strings, and we wanted to find the length of them. So, we write another function,

lengthListStr :: String -> Integer
lengthListStr string = case string of
    [] -> 0
    x:xs -> 1 + lengthListStr xs

and we find that we’re really just repeating ourselves. Other than the names of the functions, and the type declarations, these functions are completely identical. When we compute the length of a list, we don’t really care about the elements inside the list, just the shape of the list itself. So we should be able to write the one function that will work for any kind of list, regardless of its contents.

We do this by using a type variable, (by convention, a,b,c,...), meant to represent any arbitrary type.

So the new type signature would be

lengthList :: [a] -> Integer

There’s nothing inherently special about using a,b,c,... for arbitrary types in the type declaration. We could have also used apple, banana, carrot,..., but it’s good to follow convention, like pattern matching against a list with x:xs, to make your code more readable.

Not all functions can be written using a general arbitrary type. If we take our sumList function from last time,

sumList :: [Integer] -> Integer
sumList list = case list of
    []   -> 0
    x:xs -> x + sumList xs 

and we tried to generalise it to an arbitrary type, we’d find that Haskell would get upset, as addition isn’t defined for all types. Try entering "hello" + "world" into GHCi and see what happens. What you’ll receive is an error message

No instance for (Num [Char]) arising from a use of `+'

which is an esoteric way of Haskell saying “You’re asking me to try and perform addition on strings, and I don’t know what that means.” Now clearly, [Integer] -> Integer is not the only type the sumList function could have. We could have also defined the type to be [Double] -> Double.

There is indeed a way to generalise the function to a type [n] -> n, where n is a “number-like” type, and this is called ad-hoc polymorphism, which we will see in greater detail later in the course, as we haven’t yet seen type classes.

Put all of your solutions to the following exercises in the file Lab06.hs. Note that most of the functions below are missing type signatures. It’s your job to add them.


More List Operations

Exercise 1

Write a function unMaybe that takes a list of Maybe a, and returns a list containing the elements.

Any Nothing’s present in the original list should be discarded. You will have to work out the type declaration. Make it as general as possible.

> unMaybe [Just 1, Nothing, Just 2]
[1,2]
> unMaybe [Nothing, Just "hello", Just "world"]
["hello","world"]

Submission required: Exercise 1 unMaybe


Exercise 2

Write a parametric polymorphic function join, that takes two lists of the same type, and joins them together.

Your function should work for joining lists of integers, or joining strings, or joining any two lists (so long as they contain elements of the same type). You will have to figure out the type declaration of the function yourself. You should not use ++ or any other predefined functions.

>join [1,2,3] [4,5,6]
[1,2,3,4,5,6]
>join "hello" "world"
"helloworld"

Submission required: Exercise 2 join

join is such a common function, that it already has a name in Haskell. We call the operation of joining two lists together concatenation, and Haskell denotes this operation using the function ++. Note that ++ is an infix operator, like addition or subtraction, so it goes between two arguments, rather than in front of.

>[1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]

Exercise 3

Using our new function (++) (or join), try to define rev, a function that takes a list and returns the same list, reversed.

Make sure the function is polymorphic!

>rev "Hello, World!" 
"!dlroW ,olleH"
>rev [1,2,3]
[3,2,1]

Submission required: Exercise 3 rev


Exercise 4

Write a function that takes two lists and performs a “riffle” shuffle, alternating back and forth to return all elements from both lists.

If one list has more elements than the other, just add the rest of the non-empty list to the end.

>riffle [1,2,3] [4,5,6]
[1,4,2,5,3,6]
>riffle [1,2,3] [10,20,30,40,50,60]
[1,10,2,20,3,30,40,50,60]
>riffle ['h','s','e','l','l'] ['a','k']
"haskell"

Submission required: Exercise 4 riffle

Recursion using an accumulator

We’ve seen recursive functions usually follow the same sort of pattern shown below.

sumUpTo :: Integer -> Integer
sumUpTo n
    |n == 0 = 0
    |otherwise = n + sumUpTo (n-1)

There’s another way we can do this, by having another variable to record the total so far, and to then return that temporary variable. We usually call this temporary variable an accumulator. We modify the accumulator by using an additional function, called a helper function.

sumUpTo' :: Integer -> Integer
sumUpTo' n = sumHelper n 0
    where
    sumHelper :: Integer -> Integer -> Integer
    sumHelper num acc
        |num == 0 = acc
        |otherwise = sumHelper (num-1) (acc + num)

Exercise 5

You might have noticed that the rev function above, depending on how you defined it, struggles to keep up with reversing lists with more than 10,000 elements or so. Try running both last (rev [1..10000]) and Haskell’s inbuilt reverse function, last (reverse [1..10000]). Compare the running time of both functions. If your implementation of reverse takes much longer time to run than Haskell’s version, consider what could be causing the problem. Have a chat to another classmate or a tutor if you’re not sure.

Try writing a new function, fastRev, that reverses the list in a more efficient manner.

Evaluating last (fastRev [1..10000]) should appear to be instantaneous if you’ve written it correctly.

(Hint: Try writing this recursive function using a helper function, and an accumulator used to temporarily store the new reversed list.)

Submission required: Exercise 5 rev (improved)


Recursive Data Types

We can also build our own custom recursive data types, that is, types that include themselves in their own definition.

Consider the following data type to represent natural numbers:

data Nat = Z | S Nat

This definition looks a little bit like a list, in that every natural number is either:

  • Zero, represented by Z.
  • The successor (the number one more than) of another natural number.

In this universe, the number two would be S (S Z), that is, the number after the number after zero.

We can pattern match against this definition, just like we can for lists.

isOne :: Nat -> Bool
isOne n = case n of
    Z     -> False
    (S Z) -> True
    (S _) -> False

increment :: Nat -> Nat
increment n = (S n)

decrement :: Nat -> Nat
decrement n = case n of
    Z   -> error "predecessor: Zero has no predecessor"
    S m -> m

isOne will check if the given number is equal to one, that is, equal to the successor of zero. increment increases a number by one, and decrement decreases a number by one, if possible (zero being the smallest natural number).


Exercise 6

Try and write a function natEq that checks if two natural numbers are equal. What should the type be?

>natEq (S Z) (S Z)
True
>natEq (S (S Z)) (S Z)
False

Submission required: Exercise 6 natEq


Exercise 7

Try and define addNat, which performs addition on natural numbers. What should the type be?

>addNat Z (S Z)
(S Z)
>addNat (S (S Z)) (S (S (S Z)))
S (S (S (S (S Z))))

(Hint: Think about how addition can be implemented by repeatedly incrementing a number.)

Submission required: Exercise 7 addNat


Exercise 8

Write a function isNatEven that checks if a natural number is even.

(Hint: If a number is even, then subtracting 2 means it’s still even.)

>isNatEven Z
True
>isNatEven (S Z)
False
>isNatEven (S (S Z))
True

Submission required: Exercise 8 isNatEven


Exercise 9

Write functions that can convert from an Integer to a Nat, and back again.

>natToInt (S (S Z))
2
>intToNat 3
S (S (S Z))

Submission required: Exercise 9 natToInt, intToNat

Submit all your attempts at the above exercises via git.


Extensions

[Optional, not required for participation marks]


Extension 1

The powerset P(S) of a set S is defined to be the set of all subsets of S.

For example, if S={1,2,3} then P(S)={{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Write a function powerset that takes a list, and returns a list of all possible sublists.

powerset [1,2,3]
[[1,2],[1,2,3],[1],[1,3],[2],[2,3],[],[3]]

Extension 2

Write a function rucksack that accepts a list of positive integers and a target sum, which returns all sub-sequences of the original list that add up to the target sum.

The type of rucksack will be

rucksack :: [Integer] -> Integer -> [[Integer]]

and as an example to demonstrate how it works:

>rucksack [3,7,5,9,13,17] 30 
[[13,17],[3,5,9,13]]

Note that 13+17=30, and 3+5+9+13=30. This is a simplified version of the well known knapsack problem.


Extension 3

Suppose we wanted a recursive data type to represent all the integers, including negative numbers. Try to define such a data type.

Compare your implementation with your classmates, or ask a tutor, and justify why you chose the solution you did.

You’ll note that in the type Nat above, each natural number has a unique representation. There’s one and only one way to write 3, for instance, as

S (S (S Z))

Your type for Integer should satisfy the same property, i.e., I shouldn’t be able to construct -0 or -(-2) using your new type, as these are the same things as 0 and 2, but with a different representation. Having a unique representation can make checking for equality much easier.

bars search times