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
-
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
-
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 -
Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
-
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 String
s, 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
For example, if
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.