COMP1100/1130 [2020 S1]:
PROGRAMMING AS PROBLEM SOLVING Research School of Computer Science
Menu
menu
» Labs » Week 6: More Lists, Parametric polymorphism, Recursive Data Types
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.
Table of Contents
Pre-Lab Checklist Parametric Polymorphism More List Operations Recursive Data Types Extensions
Pre-lab Checklist
You should have Ynished 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/2020s1studentYles/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 re]ect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/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 Yle lab06.hs. This Yle is pre-Ylled with unYnished 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.
Consider the following function lengthListInt, that Ynds the length of a list of Integer.
Suppose we also had some Strings, and we wanted to Ynd the length of them. So, we write another function,
and we Ynd 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
Not all functions can be written using a general arbitrary type. If we take our sumList function from last time,
and we tried to generalise it to an arbitrary type, we’d Ynd that Haskell would get upset, as addition isn’t deYned 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 deYned the type to be [Double] -> Double.
More List Operations Exercise 1
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.
Submission required: Exercise 1 unMaybe Exercise 2
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 Ygure out the type declaration of the function yourself. You should not use ++ or any other predeYned functions.
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 inYx operator, like addition or subtraction, so it goes between two arguments, rather than in front of.
Exercise 3
Make sure the function is polymorphic!
Submission required: Exercise 3 rev Exercise 4
If one list has more elements than the other, just add the rest of the non-empty list to the end.
Submission required: Exercise 4 riffle Recursion using an accumulator
We’ve seen recursive functions usually follow the same sort of pattern shown below.
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.
Exercise 5
You might have noticed that the rev function above, depending on how you deYned 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 ejcient 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 deYnition.
Consider the following data type to represent natural numbers:
data Nat = Z | S Nat
This deYnition 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 deYnition, just like we can for lists.
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
Submission required: Exercise 6 natEq Exercise 7
(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.)
Submission required: Exercise 8 isNatEven Exercise 9
Write functions that can convert from an Integer to a Nat, and back again.
Submission required: Exercise 9 natToInt, intToNat
Submit all your attempts at the above exercises via git.
Extensions [COMP1100 Optional, COMP1130 Compulsory]
These exercises should only be attempted after completing all the exercises above. Feel free to do this at home and discuss with your peers on Piazza, or with tutors at a drop-in consultation.
Extension 1:
The powerset P(S) of a set S is deYned 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.
Submission required: Extension 1 powerset Extension 2:
The type of rucksack will be
rucksack :: [Integer] -> Integer -> [[Integer]]
and as an example to demonstrate how it works:
Note that 13+17=30, and 3+5+9+13=30. This is a simpliYed version of the well known knapsack problem.
Submission required: Extension 2 rucksack Extension 3:
Compare your implementation with your classmates, or ask a tutor, and justify why you chose the solution you did.
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.
Submission required: Extension 3 recursively defined integers
Don’t forget to submit all attempts at the exercises to git to recieve your participation marks.
This lab contains additional exercises for COMP1130 students. COMP1100 students are encouraged to attempt them once they have completed the compulsory exercises to receive the participation marks for the lab.
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.
lengthListInt :: [Integer] -> Integer lengthListInt list = case list of
[] -> 0
x:xs -> 1 + lengthListInt xs
lengthListStr :: String -> Integer lengthListStr string = case string of
[] -> 0
x:xs -> 1 + lengthListStr xs
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.
sumList :: [Integer] -> Integer sumList list = case list of
[] ->0
x:xs -> x + sumList xs
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 Yle lab06.hs. Note that most of the functions below are missing type signatures. It’s your job to add them.
Write a function unMaybe that takes a list of Maybe a, and returns a list containing the elements.
> unMaybe [Just 1, Nothing, Just 2]
[1,2]
> unMaybe [Nothing, Just “hello”, Just “world”] [“hello”,”world”]
Write a parametric polymorphic function join, that takes two lists of the same type, and joins them together.
>join [1,2,3] [4,5,6] [1,2,3,4,5,6]
>join “hello” “world” “helloworld”
>[1,2,3] ++ [4,5,6] [1,2,3,4,5,6]
Using our new function (++) (or join), try to deYne rev, a function that takes a list and returns the same list, reversed.
>rev “Hello, World!” “!dlroW ,olleH”
>rev [1,2,3]
[3,2,1]
Write a function that takes two lists and performs a “riie” shuie, alternating back and forth to return all elements from both lists.
>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,30,3,30,40,50,60]
>riffle [‘h’,’s’,’e’,’l’,’l’] [‘a’,’k’] “haskell”
sumUpTo :: Integer -> Integer sumUpTo n
|n == 0 = 0
|otherwise = n + sumUpTo (n-1)
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)
isOne :: Nat -> Bool
isOne n = Z
(S Z) (S _)
increment increment
case n of -> False -> True -> False
:: Nat -> Nat n = (S n)
:: Nat -> Nat
n = case n of
Z -> error “predecessor: Zero has no predecessor” S m -> m
decrement decrement
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
Try and deYne 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))))
>isNatEven Z
True
>isNatEven (S Z)
False
>isNatEven (S (S Z))
True
>natToInt (S (S Z)) 2
>intToNat 3
S (S (S Z))
powerset [1,2,3] [[1,2],[1,2,3],[1],[1,3],[2],[2,3],[],[3]]
Write a function rucksack that accepts a list of positive integers and a target sum, which returns all subsequences of the original list that add up to the target sum.
>rucksack [3,7,5,9,13,17] 30 [[13,17],[3,5,9,13]]
Suppose we wanted a recursive data type to represent all the integers, including negative numbers. Try to deYne such a data type.
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
Updated: 06 Jun 2020
Responsible Ojcer: Director, RSCS
Page Contact:
Course Convenor
Contact ANU
Copyright
Disclaimer
Privacy
Freedom of Information
+61 2 6125 5111
The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906