Transcript Functional Programming Lecture 4

Functional Programming
Lecture 4 - More Lists
Muffy Calder
Wildcards and Pattern Matching
When we exploit the structure of an argument
on the lhs of an equation, we call this pattern
matching.
E.g.
tail x:xs = xs
If we do not need the value of an argument on the
rhs of an equation, then we can use _, the
wildcard.
Example:
head x:_ = x
tail (_:xs) = xs
List Comprehensions
Based on the standard “set comprehension”
notation in mathematics
Provides a simple way to define many lists
Provides an exremely powerful method
to define a huge variety of lists
many problems can be solved
just by writing list comprehensions
Comprehension Expressions and
Generators
Basic form of list comprehension:
[ expression | generator]
Form of a generator:
variable <- list
Result: list of expression values, where the
generator variable takes on each value in the list
[x*10 | x <- [1..5]]
=> [10,20,30,40,50]
Comprehension Filters
Used to omit some of the values produced
by a generator
A filter is an expression of type Bool
using a generator variable
If filter is True, the corresponding generator
value is kept
If filter is False, the value is thrown away
E.g.
[x | x <- [1..10], x `mod` 3 == 0] => [3,6,9]
Multiple Generators
For the first value of the first generator,
use each value of the second generator
For the second value of the first generator,
use each value of the second generator,
….. Continue until done …..
E.g.
[x*y | x <- [1..4], y <- [1000..1002]]
=> [1000, 1001, 1002,
2000, 2002, 2004,
3000, 3003, 3006, 4000, 4004, 4008]
More List Comprehension
Examples
spaces :: Int -> String
spaces n = [' '|i <- [1..n]]
> spaces 5
" "
isPrime :: Int -> Bool
isPrime (n+2) = (factors (n+2) == [])
where factors m = [x|x<-[2..(m-1)], m `mod`
x == 0]
> isPrime 5
True
> isPrime 10
False
More List Comprehension
Examples
You can use values produced by earlier qualifiers:
[n*n | n<-[1..10], even n]
=>[4,16,36,64,100]
[(n,m)| m<-[1..3], n <- [1..m]]
 [(1,1),(1,2),(2,2),(1,3),(2,3),(3,3)]
But the generated values do not have to occur in the
expression:
[27| n<-[1..3]]
=> [27,27,27]
[x|x<-[1..3],y<-[1..2]]
=> [1,1,2,2,3,3]
Generators occurring later vary more quickly, i.e. loops
are nested:
[(m,n)| m <-[1..3],n<-[4,5]]
=> [(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
Examples
Define a function which returns the list of even numbers in
a list:
evens :: [Int] -> [Int]
evens [] = []
evens x:xs
| iseven x = x: evens xs
| otherwise = even xs
using primitive recursion
or
using list comprehensions
evens xs = [x| x <- xs, iseven x]
Examples
Define a function which returns the first digit in a string:
firstdig :: String -> Char
isdigit :: Char -> Bool
(in prelude)
isdigit c= c>=‘0’ && c<=‘9’
firstdig [] = ?
firstdig x:xs = if (isdigit x) then x else firstdig xs
firstdig xs = hd digits xs
where digits :: String -> String
digits [] = []
digits x:xs = if (isdigit x) then x:(digits xs)
else digits xs
or using list comprehensions
digits xs = [x| x <- xs, isdigit x]
World’s shortest sorting
algorithm?
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs)
= quicksort[y|y<-xs,y<x] ++ [x] ++
quicksort [y|y<-xs,y>=x]
quicksort [1,5,2,7]
=> [1,2,5,7]
A puzzle
A 14 digit number is to be constructed in the following
way. (Guardian,7 December 2002?)
• It starts with the digit 4 and ends with the digit 3.
• It contains two 7’s, separated by 7 digits, two 6’s,
separated by 6 digits, etc.
• What is the number??
-- program to solve Guardian puzzle December 2002
answer = mksolns (possibles)
l :: [Int]
l = [4,0,0,0,0,4,0,0,0,3,0,0,0,3]
possibles :: [[(Int,Int)]]
-- combinations of positions for 7,6,5,2 and 1
possibles = [[(7,x7),(6,x6),(5,x5),(2,x2),(1,x1)]|
x7 <- [1..4], x6<- [1..5], x5<- [1..6],
x2<- [1..9], x1<- [1..10]]
mksolns :: [[(Int,Int)]] -> [Int]
-- find unique solution amongst all combinations
mksolns (x:xs)
|p=s
| otherwise = mksolns xs
where (s,p) = soln x l
soln :: [(Int,Int)] -> [Int] -> ([Int],Bool)
-- determine whether a list of positions is a solution
soln [] ys = (ys,True)
soln (x:xs) ys
| (noplace x ys) = (ys,False)
| (toobig x) = (ys, False)
| otherwise = soln xs (place x ys)
place :: (Int,Int) -> [Int] -> [Int]
-- place number n at position i in xs
place (n,i) xs = (a ++ [n] ++ b ++ [n] ++ c)
where a = take (i) xs
b = drop (i+1) (take (i+n+1) xs)
c = drop (i+n+2) xs
noplace :: (Int,Int) -> [Int] -> Bool
-- number n cannot be placed at position i in xs
noplace (n,i) xs = ((xs!!i) /= 0) || ((xs!!(i+n+1)) /= 0)
toobig :: (Int,Int) -> Bool
toobig (n,i) = (i+n+1) >= 14
*******************************************************
Main> answer
[4,6,1,7,1,4,5,2,6,3,2,7,5,3]
(125 reductions, 217 cells)
Main>