Transcript Tuples and Lists(3)

Tuples and Lists
Lecture 3,
Programmeringsteknik del A.
Tuples
A tuple is a value made up of several other values, its
components.
Examples:
•A point in the plane (x,y)
Round brackets
and commas.
•A point in space
(x,y,z)
•A purchase
(”Dagens Lunch”, 55)
•The null tuple
()
Tuple Types
A tuple type specifies the type of each component.
Examples:
(1,2) :: (Int, Int)
(1.5, 2.25) :: (Float, Float)
(”Dagens Lunch”, 55) :: (String, Int)
() :: ()
Type Definitions
We can give names to types with a type definition:
type Purchase = (String, Int)
All types start with a capital letter.
Now Purchase and (String, Int) are interchangeable:
dagens :: Purchase
dagens = (”Dagens Lunch”, 55)
Pattern Matching
Functions on tuples can be defined by pattern matching:
name :: Purchase -> String
name (s, i) = s
price :: Purchase -> Int
price (s, i) = i
A pattern which must match
the actual argument.
Standard Selector Functions
fst (x, y) = x
snd (x, y) = y
But we cannot define:
select 1 (x, y) = x
What would the type
of the result be?
select 2 (x, y) = y
The type of a function’s result is not allowed to depend on the
values of the arguments.
Lists
A list is also a value made up of other values, its elements.
Examples:
[1, 2, 3]
:: [Int]
[True, False, True]
:: [Bool]
[]
:: [Float]
[(”Dagens Lunch”, 55)]
:: [Purchase]
Tuples vs. Lists
A tuple consists of a fixed
number of components, of
various types.
A list consists of any number
of elements, all of the same
type.
Useful, but not much to
know.
Ubiquitous! Supported by a
rich set of standard functions
and constructions.
Lists Can Make Programs Simpler!
Whenever there is a sequence of values, consider using a list.
Lists for Counting
We often need to count:
[1..10] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1,3..10] = [1, 3, 5, 7, 9]
Example:
fac :: Int -> Int
fac n = product [1..n]
Standard function to
multiply together list elements.
List Comprehensions
We often do the same thing to every element of a list:
Example:
doubles :: [Int] -> [Int]
For each element
x of xs...
doubles xs = [2 * x | x <- xs]
Add 2*x to the
list produced.
doubles [1..3]
[2, 4, 6]
Summing Squares with Lists
n
[1, 2, 3, …, n]
[1, 4, 9, …, n^2]
1 + 4 + 9 + … + n^2
sumsq :: Int -> Int
sumsq n = sum [i^2 | i <- [1..n]]
Add up the elements of a list.
Filtering Lists
A list comprehension can include a condition which elements
must satisfy.
Include only those i
which pass this test.
Example:
factors :: Int -> [Int]
factors n = [i | i <- [2..n], n `mod` i == 0]
factors 12
[2, 3, 4, 6, 12]
Using factors
Counting the number of factors…
numFactors :: Int -> Int
numFactors n = length (factors n)
Testing for a prime number…
isPrime :: Int -> Bool
isPrime n = factors n == [n]
The number of elements
in a list.
Designing List Comprehensions
Ask yourself: Do I want to process a sequence of elements in
turn?
If so, use a list comprehension!
[
|
<-
]
Start by writing down
a framework with gaps
to be filled in.
Designing List Comprehensions
Ask yourself: What is the list whose elements I want to
process?
[
|
<- [2..n]
]
Write it in the gap
after the left arrow.
Designing List Comprehensions
Ask yourself: What will I call each element?
[
|i
<- [2..n]
]
Fill the name in to
the left of the arrow.
Designing List Comprehensions
Ask yourself: Do I want to process every element, or make a
selection from them?
[
| i <- [2..n], n `mod` i == 0]
Write a comma and
a condition at the end
of the comprehension.
Designing List Comprehensions
Ask yourself: What values do I want in the result?
[i
| i <- [2..n], n `mod` i == 0]
Write an expression
before the bar.
Lists vs. Recursion?
Even problems which do not mention lists can often be solved
easily by using lists internally.
Haskell’s powerful list constructions often offer a simpler
alternative to using recursion.
But not always! Recursion is a powerful and general tool -therefore harder to use than special purpose tools, when they
are applicable.
Example: A Library Database
Computerise the librarian’s card file:
John Hughes
borrowed
The Craft of Functional Programming
Simon Thompson
borrowed
Science Goes Boink!
Representing a Loan Card
What is the information on a loan card?
Borrower’s
name.
John Hughes
borrowed
The Craft of Functional Programming
Book title.
type Borrower = String
type Book = String
type Card = (Borrower, Book)
Representing the Card File
What is the contents of the card file?
-- a sequence of loan cards!
type Database = [Card]
example :: Database
example = [ (”John Hughes”, ”The Craft of Functional Programming”),
(”Simon Thompson”, ”Science Goes Boink!”) ]
Querying the Database
What information would we wish to extract?
books :: Database -> Borrower -> [Book]
borrowers :: Database -> Book -> [Borrower]
borrowed :: Database -> Book -> Bool
numBorrowed :: Database -> Borrower -> Int
Which Books Have I Borrowed?
books example ”John Hughes” =
[”The Craft of Functional Programming”]
books example ”Mary Sheeran” = []
No books
borrowed.
books db person =
[book | (borrower, book) <- db, borrower == person]
Pattern matching again.
Quiz
Define:
numBorrowed :: Database -> Borrower -> Int
Quiz
Define:
numBorrowed :: Database -> Borrower -> Int
numBorrowed db person = length (books db person)
Updating the Database
Making and returning loans changes the contents of the
database.
makeLoan :: Database -> Borrower -> Book -> Database
returnLoan :: Database -> Book -> Database
These functions use the
information in the
database beforehand...
… to compute the
information in the
database afterwards.
Making a Loan
makeLoan :: Database -> Borrower -> Book -> Database
makeLoan db borrower book = [(borrower, book)] ++ db
Make a new card.
Returning a Loan
returnLoan :: Database -> Book -> Database
returnLoan db book =
[(borrower, book’) | (borrower, book’) <- db,
book’ /= book]
The Role of Lists
Lists offer a natural way to model real world information -sequences are everywhere!
Lists are easy to manipulate thanks to Haskell’s support: a
good first choice of data structure.
Lists are not always efficient: candidates for replacement by
faster structures later in program development.
Some Standard List Functions
Haskell provides many standard functions to manipulate lists.
Let’s look at a few.
But first:
What is the type of length?
Polymorphic Types
length :: [Int] -> Int
length :: [Float] -> Int
length has many types!
It is polymorphic.
That is why it is useful.
length :: [Card] -> Int
For any type t,
length :: [t] -> Int
A type variable,
which may stand for
any type.
Taking and Dropping
•take n xs
the first n elements of xs,
•drop n xs
all but the first n elements.
Examples:
take 3 (factors 12)
[2, 3, 4]
drop 3 (factors 12)
[6, 12]
Quiz
take and drop have the same (polymorphic) type. What is it?
Quiz
take and drop have the same (polymorphic) type. What is it?
take, drop :: Int -> [a] -> [a]
A must stand for the
same type everywhere.
Examples:
Int -> [Float] -> [Float]
Int -> [String] -> [String]
Not
Int -> [Float] -> [String]
The Zipper
Often we want to combine corresponding elements of two lists:
zip [
”John” ,
”Simon”,
”Mary” ]
[
”Welsh”,
”English”,
”Irish” ]
[ (”John”,”Welsh”),
(”Simon”,”English”), (”Mary”,”Irish”)]
The type of zip
zip :: [a] -> [b] -> [(a, b)]
Example:
zip [1, 2, 3] [”a”, ”b”, ”c”]
[(1,”a”), (2,”b”), (3,”c”)]
Here zip :: [Int] -> [String] -> [(Int, String)]
Example: The Position of x in xs
position :: a -> [a] -> Int
Example: position ”b” [”a”, ”b”, ”c”]
2
Idea: Mark every element with its position, and search for the
one we want.
Marking Elements with Positions
[”a”, ”b”, ”c”]
[(”a”,1), (”b”,2), (”c”,3)]
zip [”a”, ”b”, ”c”]
[ 1,
2,
3]
[(”a”,1), (”b”,2), (”c”,3)]
Use zip xs [1..length xs]
Searching for the Right Element
Select the positions where the element we’re searching for
appears:
positions x xs = [pos | (x’,pos) <- zip xs [1..length xs],
x’ == x]
positions ”b” [”a”, ”b”, ”c”]
[2]
A list. We
want just
a number.
The Complete Position Function
position :: a -> [a] -> Int
position x xs = head [pos | (x’,pos) <- zip xs [1..length xs],
x’ == x]
Select the first
element from the
list of positions.
Example: Calculate Path Lengths
How long is the path?
Representing a Point
type Point = (Float, Float)
x- and y-coordinates.
distance :: Point -> Point -> Float
distance (x, y) (x’, y’) = sqrt ((x-x’)^2 + (y-y’)^2)
Representing a Path
Q
S
R
P
type Path = [Point]
examplePath = [p, q, r, s]
path length = distance p q + distance q r + distance r s
Two Useful Functions
•init xs -- all but the last element of xs,
•tail xs -- all but the first element of xs.
init [p, q, r, s]
[p,
q,
r]
tail [p, q, r, s]
[q,
r,
s]
zip …
[(p,q), (q,r), (r,s)]
The pathLength Function
pathLength :: Path -> Float
pathLength xs = sum [distance p q
| (p,q) <- zip (init xs) (tail xs)]
Example:
pathLength [p, q, r, s]
distance p q + distance q r + distance r s
Rule of Thumb
Question: Do I want to go through the elements of two lists
together?
Answer: Use zip!
Lessons
Lists model any kind of sequence in the real world.
Lists can express many kinds of repeated computation in
programs.
Special constructions and a rich set of polymorphic standard
functions let us manipulate lists very easily indeed.
Look for opportunities to use them!
Reading
This lecture is largely based on Chapter 5 of the text book, up
to section 5.7. Read this, and try exercises 5.11, 5.12, 5.13, and
5.14.
Section 5.8 summarises a number of standard functions on
lists. Knowing these functions will make list programming
much easier for you.