Transcript Lect_8_9

Functional Programming
Universitatea Politehnica Bucuresti
2008-2009
Adina Magda Florea
http://turing.cs.pub.ro/fp_09
Lecture No. 8 & 9








The Haskell Programming Language
Introduction
Types and classes
Defining functions
List comprehensions
String comprehensions
Recursive functions
High order functions
Haskell - history


1987 – an international committee of researchers
initiates the development of Haskell, a standard lazy
functional language
1998 - The committee publishes the Haskell 98
report, defining a stable version of the language
1. Haskell - introduction



Haskell is a typeful programming language: types are
pervasive (unlike Scheme)
Because Haskell is a purely functional language, all
computations are done via the evaluation of expressions
(syntactic terms) to yield values (abstract entities that we
regard as answers).
Every value has an associated type.
5 :: Integer
'a' :: Char
inc :: Integer -> Integer
[1,2,3] :: [Integer]
('b',4) :: (Char,Integer)
Haskell - introduction


All Haskell values are "first-class" - they may be
passed as arguments to functions, returned as
results, placed in data structures, etc.
Haskell types, on the other hand, are not first-class.
Types describe values, and the association of a
value with its type is called a typing.
Haskell - introduction





Functions in Haskell are normally defined by a series of
equations. For example, the function inc can be defined by the
single equation:
inc
n = n+1
An equation is an example of a declaration.
Another kind of declaration is a type signature declaration with
which we can declare an explicit typing for inc:
inc :: Integer -> Integer
In Haskell function application is denoted using a space
f a b + c*d
Function application has higher priority than all other operators
f a + b -> (f a) + b
Haskell - introduction
Mathematics

f(x)

f(x,y)

f(g(x))

f(x,g(y))

f(x)*g(y)
Haskell

fx

fxy

f (g x)

f x (g y)

fx*gy
Naming requirements




Function and argument names must begin with lower case
letters:
myFun
fun1 arg_2
By convention, list arguments usually have an s suffix on
their name:
xs ns nss
In a sequence of definitions, each definition must begin in
precisely the same column
a = 10
a = 10
b = 20
b = 20
c = 30
c = 30
The layout rule avoids the needs for explicit syntax to
indicate the grouping of definitions
2. Types and classes



Every expression has a type t, which can be
automatically calculated at compile time by type
inference:
e :: t
:type calculates the type of an expression:
:type not False
not False :: Bool
Basic types
Bool
Char
String
Int (fixed precision)
Float
Integer (arbitrary precision)
Types and classes




List type – sequence of values of the same type:
[False,True,False] :: [Bool]
Tuple type – a sequence of values of different
types:
(False, True) :: (Bool, Bool)
(False,'a',True) :: (Bool, Char, Bool)
The list type does not encode its size
The type of a tuple encodes its size
Function types


A function is a mapping from values of one type to
values of another type:
not
:: Bool -> Bool
isDigit
:: Char -> Bool
t1 -> t2 is the type of functions that map values of
type t1 to values of type t2
add
:: (Int,Int) -> Int
add (x,y) = x = y
zeroto
zeroto n
:: Int -> Int
= [0..n]
Polymorphic types





Polymorphic type expressions - describe
families of types.
[a] is the family of types consisting of, for
every type a, the type of lists of a.
Lists of integers (e.g. [1,2,3]), lists of
characters (['a','b','c']), even lists of lists of
integers, etc., are all members of this family.
a – type variable
Haskell has only universally quantified types
Polymorphic types



Polymorphic types - some types are strictly
more general than others in the sense that the
set of values they denote is larger.
The type [a] is more general than [Char].
The latter type can be derived from the
former by a suitable substitution for a.
Polymorphic types

With regard to this generalization ordering,
Haskell's type system possesses two
important properties:

every well-typed expression is guaranteed
to have a unique principal type

the principal type can be inferred
automatically
Polymorphic types




An expression's or function's principal type is the
least general type that, intuitively, contains all instances
of the expression.
head
:: [a] -> a
head (x:xs) = x
For example, the principal type of head is [a]->a;
[b]->a, a->a, or even a are correct types, but too
general, whereas something like [Integer]->Integer is
too specific.
The existence of unique principal types is the hallmark feature of the
Hindley-Milner type system, which forms the basis of the type systems of
Haskell, ML, Miranda, and several other (mostly functional) languages.
Curried functions

Functions with multiple arguments are also possible
by returning functions as results:
add
add x y


:: Int -> (Int -> Int)
=x+y
add takes an integer x and returns a function add x.
In turn this function takes an integer y and returns
the result x + y
Curried functions


add and add_1 produce the same result but add_1
takes its two arguments at the same time, while add
takes them one at a time.
add_1 :: (Int,Int) -> Int
add :: Int -> (Int -> Int)
Functions that take their arguments one at a time are
called curried functions, in honor of the work of
Haskell Curry on such functions
Curried functions

Functions with more than two arguments can be
curried by returning nested functions.
mult
:: Int -> (Int -> (Int -> Int))
mult x y z = x*y*z

mult takes an integer x and returns a function mult
x, which in turn takes an integer y and returns a
function mult x y, which finally takes an integer z
and returns the result x*y*z
Curried functions
add
add x y
:: Integer -> Integer -> Integer
=x+y
Integer->Integer->Integer
is equivalent to

Integer->(Integer->Integer);
i.e. -> associates to the right.

Curried functions

As a consequence it is natural for a function
application to associate to the left
mult x y z

means
((mult x) y) z
Unless tupling is explicitly required, all functions in
Haskell are normally defined in curried form
Why currying?

Curried functions are more flexible than functions
on tuples because useful functions can often be
made by partially applying a curried function
add 1
inc

:: Int -> Int
= add 1
This is an example of the partial application
of a curried function, and is one way that a
function can be returned as a value.
Why currying?


Pass a function as an argument.
The map function is a perfect example:
map
map f []
map f (x:xs)

:: (a->b) -> [a] -> [b]
= []
= f x : map f xs
This is an example of the partial application
of a curried function, and is one way that a
function can be returned as a value.
Polymorphic functions



A function is called polymorphic if its type contains
one or more type variables
length:: [a] -> Int
head :: [a] -> a
id
:: a -> a
Type variables must begin with lower case letters and
are usually named a, b, c, etc.
Type variables can be instantiated to different types in
different circumstances
length [False, True]
length [1,2,3,4]
Overloaded functions



A polymorphic function is called overloaded if its type
contains one or more class constraints
sum
:: Num a => [a] -> a
For any numeric type a, sum takes a list of values of
type a and returns a value of type a
Constrained type variables can be instantiated to any
types that satisfy the constraint
sum [1,2,3]
sum [1.1, 2.2, 3.3]
sum ['a', 'b', 'c']
ERROR
Type classes
Haskell has a number of type classes, including:


Num – Numeric types

Eq – Equality types

Ord – Ordered types
(+)
:: Num a => a -> a -> a
(==)
(<)
:: Eq a => a -> a -> Bool
:: Ord a => a -> a -> Bool
3. Defining functions

Conditional expressions
abs
abs n
:: Int -> Int
= if n >= 0 then n else -n
signum
signum n

:: Int -> Int
= if n < 0 then -1 else
if n == 0 then 0 else 1
In Haskell, conditional expressions must always have an
else branch, which avoids any possible ambiguity
problems with nested conditionals
Guarded equations

As an alternative to conditionals, functions can also
be defined using guarded equations
abs
abs n

:: Int -> Int
| n >= 0
= n
| otherwise = -n
Guarded equations can be used to make definitions
involving multiple conditions easier to read:
signum
:: Int -> Int
signum n | n < 0
= -1
| n == 0
= 0
| otherwise = 1
Pattern Matching

Many functions have a particularly clear definition
using pattern matching on their arguments
not
:: Bool -> Bool
not False = True
not True = False
Pattern Matching

Functions may be defined in many different ways
using pattern matching
(&&)
True
True
False
False
:: Bool -> Bool -> Bool
&& True = True
&& False = False
&& True = False
&& False = False
can be defined more compactly by
True && True
_
&& _
= True
= False
Pattern Matching

The following definition is more efficient
True
False

Patterns are matched in order. For example the
following definition returns False
_
True

&& b = b
&& _ = False
&& _
= False
&& True = True
Patterns may not repeat variables. For example, the
following definition gives an error
b && b
_ && _
=b
= False
ERROR
List patterns

List – cons operator :
[1,2,3,4]

Functions on lists can be defined using x:xs patterns
head
head (x:_)
tail
tail (_:xs)

means
1:(2:(3:(4:[])))
:: [a] -> a
=x
:: [a] -> [a]
= xs
x:xs patterns must be parenthesised. For example,
the following definition gives an error
head x:_
=x
ERROR
Integer patterns

Functions on integers can be defined using n+k
patterns, where n is an integer variable and k>0 is
an integer constant :
pred
:: Int -> Int
pred (n+1) = n

n+k patterns only match integers k>0
pred 0

ERROR
n+k patterns must be parenthesised because function
application has priority over +
pred n+1 = n
ERROR
Lambda expressions
Functions can be constructed without naming the
functions by using lambda expressions

lambda expressions can be used to give a formal
meaning to functions using currying
add x y = x+y
means
add = \x -> (\y -> x+y)

Lambda expressions
odds n = map f [0..n-1]
where
f x = x*2 + 1
can be simplified to
odds n = map (\x -> x*2 +1) [0..n-1]
Sections



An operator written between its two arguments can
be converted into a curried function written before
its two arguments by using parentheses
(+) 1 2
3
This convention allows one of the arguments of the
operator to be included in the parentheses
(1+) 2
3
(+2) 1
3
In general, if @ is an operator then functions of the
form (@), (x@) and (@y) are called sections.
Why sections ?

Useful functions can sometimes be constructed in a
simple way using sections. For example:
(1+) - successor function
(1/) – reciprocation function
(*2) – doubling function
(/2) – halving function
4. List comprehensions


In mathematics, the comprehension notation can be
used to construct new sets from old sets:
{x2 | x  {1..5}}
In Haskell, a similar comprehension notation can
be used to construct new lists from old lists
[x^2 | x <- [1..5]]

[1,4,9,16,25]
The expression x <- [1..5] is called a generator as it
states how to generate values for x
List comprehensions

Comprehensions can have multiple generators,
separated by commas
[(x,y) | x <- [1,2,3], y<- [4,5]]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

Changing the order of the generators changes the order
of the elements in the final list:
[(x,y) | y<- [4,5], x <- [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

Multiple generators are like nested loops with later
generators as more deeply nested loops whose variables
change value more frequently
Dependent generators


Later generators can depend on the variables that
are introduced by earlier generators
[(x,y) | x <- [1..3], y<- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
Using a dependant generator we can define the
library function that concatenates a list of lists:
concat
:: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]
concat [[1,2,3],[4,5],[6]]
[1,2,3,4,5,6]
Guards


List comprehensions can use guards to restrict the
values produced by earlier generators
[x | x <- [1..10], even x]
[2,4,6,8,10]
Using a guard we can define a function that maps a
positive integer to its list of factors:
factors
:: Int -> Int
factors n
= [x | x <- [1..n], n `mod` x == 0]
factors 15
[1,3,5,15]
Guards

Using factors we can define a function that decides
if a number is prime
prime
prime n
prime 15
prime 7
:: Int -> Bool
= factors n == [1,n]
False
True
Guards

Using a guard we can now define a function that
returns the list of all primes up to a given limit:
primes
primes n
:: Int -> [Int]
= [x | x <- [2..n], prime x]
primes 40
[2,3,5,7,11,13,17,19,23,29,31,37]
The Zip function

A useful library function is zip, which maps two
lists to a list of pairs of their corresponding
elements:
zip
:: [a] -> [b] -> [(a,b)]
zip ['a','b','c'] [1,2,3]
[('a',1),('b',2),('c',3)]
The Zip function

Using zip we can define a function that returns the
list of all pairs of adjacent elements from a list:
pairs
:: [a] -> [(a,a)]
pairs xs = zip xs (tail xs)
pairs [1,2,3,4]
[(1,2),(2,3),(3,4)]
Is the list sorted?

Using pairs we can define a function that decides if
the elements in a list are sorted:
sorted
:: Ord a => [a] -> Bool
sorted xs =
and [x<= y | (x,y) <- pairs xs]
sorted [1,2,3,4]
True
Positions

Using zip we can define a function that returns the
list of all positions of a value in a list:
positions
:: Eq a => a -> [a] -> [Int]
positions x xs =
[ i | (x',i) <- zip xs [0..n], x == x']
where n = length xs - 1
positions 0 [1,0,0,1,0,1,1,0]
[1,2,4,7]
5. String comprehensions


Internally, strings are represented as lists of
characters:
"abc" :: String
['a','b','c'] :: [Char]
Because strings are just special kinds of lists, any
polymorphic function that operates on lists can also
be applied to strings
length "abc"
3
take 3 "abcde"
"abc"
zip "abc" [1,2,3,4]
[('a',1),('b',2),('c',3)]
String comprehension


List comprehension can be used to define functions
on strings
Ex function that counts the lower case letters in a
string:
lowers
:: String -> Int
lowers xs =
length [x | x <- xs, isLower x]
lowers "Haskell"
6
6. Recursive functions
length
:: [a] -> Int
length []
=0
length (_:xs) = 1 + length xs
reverse
reverse []
reverse (x:xs)
:: [a] -> a
= []
= reverse xs ++ [x]
Recursive functions
zip
zip [ ] _
zip _ [ ]
zip (x:xs) (y:ys)
:: [a] -> [b] -> [(a,b)]
=[]
=[]
= (x,y) : zip xs ys
(++)
[ ] ++ ys
(x:xs) ++ ys
:: [a] -> [a] -> [a]
= ys
= x: (xs ++ ys)
drop
drop 0 xs
drop (n+1) [ ]
drop (n+1) (_:xs)
:: Int -> [a] -> [a]
= xs
=[]
= drop n xs
Recursive functions
sort
:: [Int] -> [Int]
sort [ ]
=[]
sort (x:xs)
=
sort smaller ++ [x] ++ sort larger
where
smaller = [a | a <- xs, a<= x]
larger = [b | b <- xs, b>x]
QUCKSORT
Non-empty lists can be sorted by sorting
the tail values <= the head
sorting the tail values > the head
and then appending the resulting lists
on either side of the head value
High-order functions
The next slides are based on:
Programming in Haskell,
Graham Hutton,
Cambridge University Press (January 15,
2007)

7. High-order functions

A function is called higher order if it takes a
function as an argument or returns a
function as a result
twice
:: (a -> a) -> a -> a
twice f x = f (f x)
The Map function

map is a library function – applies a
function to every element of a list
map
:: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]
map f [ ]
=[]
map f (x:xs) = f x : map f xs
map (+1) [1,3,5,7]
[2,4,6,8]
The Filter function

filter is a library function – selects every
element of a list that satisfies a predicate
filter
filter p xs
:: (a -> Bool) -> [a] -> [a]
= [ x | x <- xs, p x]
filter p [ ]
=[]
filter p (x:xs) =
|px
= x : filter p xs
| otherwise = filter p xs
filter even [1..10]
[2,4,6,8,10]
The Foldr function

A number of functions on lists can be
defined using the following simple pattern
of recursion:
f[]
=v
f (x:xs) = x op f xs

f maps the empty list to some value v and
any non-empty list to some function op
applied to its head and f of its tail
The Foldr function

For example
sum [ ]
=0
sum (x:xs) = x + sum xs
product [ ]
=1
product (x:xs) = x * product xs
and [ ]
= True
and (x:xs) = x && and xs
The Foldr function

The higher order function foldr (fold right)
encapsulates this simple pattern of recursion, with
the function op and the value v as arguments
sum
= foldr (+) 0
product
= foldr (*) 1
or
= foldr (||) False
and
= foldr (&&) True
The Foldr function
foldr
:: (a -> b -> b) -> b -> [a] -> b
foldr f v [ ]
=v
foldr f v (x:xs) = f x (foldr f v xs)

However it is best to think of foldr nonrecursively as simultaneously replacing each (:) in
a list by a given function and [ ] by a give value
The Foldr function
sum [1,2,3]
= foldr (+) 0 [1,2,3]
Replace each (:) by
(+) and [ ] by 0
= foldr (+) 0 (1: (2: (3: [ ])))
= 1 + (2 + (3 + 0)) = 6
product [1,2,3]
= foldr (*) 1 [1,2,3]
= foldr (*) 1 (1: (2: (3: [ ])))
= 1 * (2 * (3 * 1)) = 6
Replace each (:) by
(*) and [ ] by 1
The Foldr function
sum [1,2,3]
= foldr (+) 0 [1,2,3]
= foldr (+) 0 (1: (2: (3: [ ])))
= 1 + (2 + (3 + 0)) = 6
product [1,2,3]
= foldr (*) 1 [1,2,3]
= foldr (*) 1 (1: (2: (3: [ ])))
= 1 * (2 * (3 * 1)) = 6
The Composition function

The library function (.) returns the composition of
two functions as a single function
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
odd :: Int -> Bool
odd = not . even