Transcript Functional Programming Lecture 3

Functional Programming
Lecture 3 - Lists
Muffy Calder
The List Types
• A list can have any number of elements
• All the elements must have the same type
• If the elements have type a
then the list has type [a]
• You can put any type of value in a list
– For every type a there is a type [a]
x1,…,xn::a
[x1,…,xn]::[a]
a :: Type
[a] :: Type
list type rules
List Notation – finite, simple lists
• Put square brackets around the list and separate the
elements with commas
• All elements must have the same type
– [1, 2, 3, 4] :: [Int]
– [ ] :: [a] for every type a
• Can have expressions in the list
– [13, 2+2, 5*x] => [13, 4, 150]
• Can have a list of lists
[[1,2], [3,7,1], [ ], [900]] :: [[Int]]
a list of lists!
Strings
A string is just a list of characters.
[‘c‘, ‘a‘, ‘t‘] is same as “cat” .
The Standard Haskell library contains
type String = [Char]
(A type synonym.)
“cat” :: String
[‘c‘, ‘a‘, ‘t‘] ::String
• What is the type of [“cat”,”dog”]?
More List Notation
• Give the head and the tail of the list, as x:xs
– x is the head
– xs is the tail
– when x :: a and xs :: [a],
then x:xs :: [a]
– : is pronounced cons
– example [1,2,3,4] == 1:(2:(3:(4:[])))
== 1:(2:(3:[4]))
x:: a xs :: [a]
x:xs ::[a]
More List Notation
• Taking lists apart: head and tail
• head gives first element of a nonempty list
• head :: [a] -> a
– head [a,b,c,d]
= head (a : [b,c,d])
= a
– it is an error to apply head to []
• tail removes first element from a nonempty list
• tail :: [a] -> [a]
– tail [a,b,c,d]
= tail (a : [b,c,d])
= [b,c,d]
Head and Tail
head (x:xs) = x
-- head.1
tail (x:xs) = xs
-- tail.1
• Why no head.0?
xs :: [a]
tail xs :: [a]
xs ::[a]
head xs :: a (sometimes!)
• Theorem:
• For every nonempty list xs.
((head xs):(tail xs)) == xs
Do you believe this?
Could you prove it?
Sequences
You can use “..” in the “usual” (!) way.
[1..5] => [1,2,3,4,5]
[1..n] => [1, 2, 3, …, n]
[10,13..20] => [10, 13, 16, 19]
[a,b..c] => [a, a+(b-a), a+2*(b-a), …]
['a' .. 'z'] => "abcdefghijklmnopqrstuvwxyz”
['a', 'c' .. 'z'] => "acegikmoqsuwy" :: [Char]
[‘0‘ .. ‘9‘] => “0123456789”
The length of a list
length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs
(length.0)
(length.1)
Defining a function this way uses:
pattern matching and primitive recursion.
length [3,8,1] => 3
length [ ] => 0
length “hello” => 5
length [1..n] => n
length [1..] => infinite loop
Mapping
• One of the most important list operations
• Apply a function to each element of a list
map :: (a->b) -> [a] -> [b]
map sqrt [1,4,9,16] => [1.0, 2.0, 3.0, 4.0]
The type of map
map :: (a->b) -> [a] -> [b]
map takes two arguments
a function of type a->b
a list of type [a]
and returns a result
a list of type [b]
f:: a -> b
xs::[a]
map f xs :: [b]
The function has to take an element of the
argument and produce an element of the result
map f [] = []
map f (x:xs) = (f x) : (map f xs)
(map.0)
(map.1)
Indexing a list
The !! operator lets you access a list element
by index (the indices start from 0)
[x0, x1, x2, … xn] !! i => xi
List Concatenation (++)
Takes two lists and joins them together
[1,2,3] ++ [9,8,7] => [1,2,3,9,8,7]
All the elements of the result list must have
the same type; therefore both argument lists
must have the same type
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x:(xs++ys)
(++.0)
(++.1)
Examples
Define a function which concatenates a list of strings.
E.g. concat [“make”, “into”, “bigstring”]
=> “makeintobigstring”
concat :: [String] -> String
concat [] = []
concat x:xs = x ++ concat xs
a better version
concat2 [] = []
concat2 [x] = x
concat2 x:xs = x ++ “ “ ++ concat2 xs
concat2 [“make”, “into”, “bigstring”]
=> “make into bigstring”
Take and drop
• builds a sublist by
– taking n elements from the front
– dropping n elements from the front
take 3 “abcde” => “abc”
drop 3 “abcde” => “de”
take,drop :: Int -> [a] -> [a]
take n [] = []
take n (x:xs)
| (n==0) = []
| otherwise = x: (take n-1 xs)
drop n [] = []
drop n (x:xs)
| (n==0) = (x:xs)
| otherwise = drop (n-1) xs
Defining functions over lists
• Split the list in the middle
– use (++) take drop
– this method gives a higher level, more abstract
view of lists - sometimes better for high level
programming
• Split the first element from the rest
– use (:) head tail
– this method reflects the internal representation
of lists, and is used to implement standard
functions
Examples
Define a function which sums the numbers in a list:
sumlist :: [Int] -> Int
sumlist [] = 0
sumlist (x:xs) = x+ sumlist xs
Define a function which multiplies the numbers in a
list:
multlist :: [Int] -> Int
multlist [] = 1
multlist x:xs = x * multlist xs
Define a function which returns the last element in a
list:
last :: [a] -> a
first attempt
last [] = []
last x:xs = last xs
but, what about last [1]?
last [x] =x
last (x:xs) = last xs
equations are tried in the order they are declared.