PROGRAMARE FUNCȚIONALĂ

Curs 5

Definirea funcțiilor
DEFINIREA FUNCŢIILOR

New from old

Expresii condiţionale. Ecuaţii gardate

Potrivirea şabloanelor (pattern matching)
folosirea şablonului vid
şabloane pe tuple
şabloane pe liste
operatorul constructor “:”
şabloane pe întregi

Lambda expresii. Aplicaţii practice

Secţiuni. Aplicaţii
New from old
e.g.
Decide if a character is a digit:
isDigit :: Char → Bool
isDigit c = c ≥ ’0’ && c ≤ ’9’
Decide if an integer is even:
even :: Integral a ⇒ a → Bool
even n = n `mod` 2 == 0
Split a list at the nth element:
splitAt :: Int → [a ] → ([a ], [a ])
splitAt n xs = (take n xs, drop n xs)
Reciprocation:
recip :: Fractional a ⇒ a → a
recip n = 1 / n
Conditional expressions
 Conditional expressions use a logical expression called a
condition to choose between two results of the same type. If
the condition is True, then the first result is chosen, and if it is
False, then the second result is chosen.
e.g.
 the library function abs is defined as follows:
abs :: Int → Int
abs n = if n ≥ 0 then n else − n
 the library function signum is NESTED defined as follows:
signum :: Int → Int
signum n = if n < 0 then − 1 else
if n == 0 then 0 else 1

Note
 conditional expressions in Haskell must always have an
else branch, which avoids the well-known “dangling else”
problem.
Guarded equations
 Guarded equations use a sequence of logical
expressions called guards in order to choose among
a sequence of results of the same type. If the first
guard is True, then the first result is chosen;
otherwise if the second guard is True then the
second result is chosen and so on.
e.g.
 the library function abs can also be defined as
follows:
abs n | n ≥ 0 =n
| otherwise = −n
 The symbol | is read as “such that”, and the guard
otherwise is defined in the standard Prelude simply
by otherwise = True.
Conditional expressions vs
Guarded equations
The main benefit of guarded equations
over conditional expressions is that
definitions with multiple guards are
easier to read.
e.g.
 function signum can also be defined
as follows:
signum n | n < 0 = −1
| n == 0 =0
| otherwise = 1
Pattern matching
 The pattern matching use a sequence of syntactic
expressions called patterns in order to choose among a
sequence of results of the same type. If the first pattern is
matched, then the first result is chosen; otherwise, if the
second pattern is matched, then the second result is chosen,
and so on.
e.g.
 the library function not is defined as follows:
not :: Bool → Bool
not False = True
not True = False
 the library operator && (conjunction) can be defined as
follows:
(&&) :: Bool → Bool → Bool
True && True = True
True && False = False
False && True = False
False && False = False
Pattern matching
e.g.
 the library operator && (conjunction) can be
defined using the wildcard pattern ‘_’ as follows:
(&&) :: Bool → Bool → Bool
True && True = True
_ && _ = False
and also
(&&) :: Bool → Bool → Bool
True && b = b
False && _ = False
Note
 Under lazy evaluation, for the first definition using
wildcard pattern, if the first argument is False,
then the result False is returned without the need
to evaluate the second argument.
Pattern matching
Note
 For technical reasons the same name may not be
used for more than one argument in a single
equation.
e.g.
The next definition for the operator &&
b && b = b
_ && _ = False
is invalid because of the above naming
requirement.
 A valid version of this definition can be obtained
by using a guard in order to decide if the two
arguments are equal:
b && c | b == c =b
| otherwise = False
Pattern matching. Tuple patterns
 A tuple of patterns is itself a pattern, which
matches any tuple of the same arity whose
components all match the corresponding
patterns in order.
e.g.
 the library functions fst and snd are
defined as follows:
fst :: (a, b) → a
fst (x , _) = x
snd :: (a, b) → b
snd (_ , y) = y
Pattern matching. List patterns
 A list of patterns is itself a pattern, which
matches any list of the same length whose
elements all match the corresponding
patterns in order.
e.g.
 a function test that decides if a list
contains precisely three characters
beginning with an ’a’ can be defined as
follows:
test :: [Char ] → Bool
test [’a’, _, _ ] = True
test _ = False
Pattern matching. List patterns
 The operator ‘:’, named cons, constructs a new list by
prepending a new element to the start of an existing list.
e.g.
 the list [1, 2, 3] can be decomposed as follows:
[1, 2, 3]
= {list notation }
1 : [2, 3]
= {list notation }
1 : (2 : [3])
= {list notation }
1 : (2 : (3 : [ ]))

Note
 [1, 2, 3] is just an abbreviation for 1 : (2 : (3 : [ ])).
 In order to avoid excess parentheses when working with
such lists, the cons operator is assumed to associate to the
right; e.g. 1 : 2 : 3 : [ ] means 1 : (2 : (3 : [ ])).
Pattern matching. List patterns
 The operator ‘:’ can also be used to construct
patterns, which match any non-empty list whose first
and remaining elements match the corresponding
patterns in order.
e.g.
 the previous function test can also be defined as follows:
test :: [Char ] → Bool
test (’a’ : _) = True
test _ = False
 the library functions null, head and tail are defined as follows:
null :: [a ] → Bool
null [ ] = True
null ( _:_ ) = False
head :: [a ] → a
head (x : _ ) = x
tail :: [a ] → [a ]
tail (_ : xs) = xs
Pattern matching. List patterns
Note
 cons patterns must be
parenthesised, because function
application has higher priority than all
other operators (here, ‘:’).
e.g.
 the definition tail _: xs = xs without
parentheses means (tail _) : xs = xs,
which is both the incorrect meaning
and an invalid definition.
Pattern matching. Integer patterns
 Haskell allows integer patterns of the form n + k,
where n is an integer variable and k > 0 is an integer
constant.
e.g.
 a function pred that maps zero to itself and any
strictly positive integer to its predecessor can be
defined as follows:
pred :: Int → Int
pred 0 =0
pred (n + 1) = n
Note
 Integer patterns only match positive integers.
 For the same reason as cons patterns, integer
patterns must be also parenthesised.
Lambda expressions
 Functions can also be constructed using lambda
expressions, which comprise a pattern for each of the
arguments, a body that specifies how the result can be
calculated in terms of the arguments, but do not give a name
for the function itself.
 In other words, lambda expressions are nameless functions.
e.g.
 a nameless function that takes a single number x as its
argument, and produces the result x + x , can be
constructed as follows:
\x → x + x
Note
 Despite the fact that they have no names, functions
constructed using lambda expressions can be used in the
same way as any other functions.
e.g.
> (\x → x + x) 2
4
Lambda expressions.
Practical applications
1. can be used to formalise the meaning of
curried function definitions;
e.g.
The definition
add x y = x + y
can be understood as meaning
add = \x → (\y → x + y)
which makes precise that add is a
function that takes a number x and
returns a function, which in turn takes
a number y and returns the result
x + y.
Lambda expressions.
Practical applications
2. are useful when defining functions that return
functions as results by their very nature, rather
than as a consequence of currying;
e.g.
 the library function const that returns a constant
function that always produces a given value
can be defined as follows:
const :: a → b → a
const x _ = x
 However, it is more appealing to define const in
a way that makes explicit that it returns a
function as its result, by including parentheses
in the type and using a lambda expression in
the definition itself:
const :: a → (b → a)
const x =λ_→x
Lambda expressions.
Practical applications
3. can be used to avoid having to name a function
that is only referenced once;
e.g.
 the function odds that returns the first n odd
integers can be defined as follows:
odds :: Int → [Int]
odds n = map f [0 . . n − 1]
where f x = x ∗ 2 + 1
The library function map applies a function to
all elements of a list.
 However, because the locally defined function f
is only referenced once, the definition for odds
can be simplified by using a lambda expression
as follows:
odds n = map (\x → x ∗ 2 + 1) [0 . . n − 1]
Sections
 Functions such as + that are written between their two
arguments are called operators.
Notes
 Any function with two arguments can be converted into
an operator by enclosing the name of the function in
single back quotes, as in 7 `div` 2.
 The converse is also possible. In particular, any operator
can be converted into a curried function that is written
before its arguments by enclosing the name of the
operator in parentheses, as in (+) 1 2.
 This convention also allows one of the arguments to be
included in the parentheses, as in (1+) 2 and (+2) 1.
 If ⊕ is an operator, then expressions of the form (⊕), (x ⊕), and
(⊕ y) for arguments x and y are called sections, whose
meaning as functions can be formalised using lambda
expressions as follows:
(⊕) = \x → (\y → x ⊕ y)
(x ⊕) = \y → x ⊕ y
(⊕ y) = \x → x ⊕ y
Sections. Main applications
1. can be used to construct a number of simple but useful
functions in a particularly compact way;
e.g.
(+) is the addition function \x → (\y → x + y)
(1+) is the successor function \y → 1 + y
(1/) is the reciprocation function \y → 1 / y
(∗2) is the doubling function \x → x ∗ 2
(/2) is the halving function \x → x / 2
2. are necessary when stating the type of operators, because
an operator itself is not a valid expression in Haskell;
e.g.
(&&) :: Bool → Bool → Bool
3. are also necessary when using operators as arguments to
other functions
e.g.
and :: [Bool ] → Bool
and = foldr (&&) True
Exercises
1. Using library functions, define a function
halve :: [a ] → ([a ], [a ])
that splits an even-lengthed list into two halves.
For example:
> halve [1, 2, 3, 4, 5, 6]
([1, 2, 3], [4, 5, 6])
2. Consider a function safetail :: [a ] → [a ] that behaves as the
library function tail, except that safetail maps the empty list to
itself, whereas tail produces an error in this case. Define
safetail using:
(a) a conditional expression;
(b) guarded equations;
(c) pattern matching.
Hint: make use of the library function null.
3. In a similar way to &&, show how the logical disjunction
operator || can be defined in four different ways using pattern
matching.
Exercises
4. Redefine the following version of the conjunction operator using
conditional expressions rather than pattern matching:
True && True = True
_ && _ = False
5. Do the same for the following version, and note the difference
in the number of conditional expressions required:
True ∧ b = b
False ∧ _ = False
6. Show how the curried function definition mult x y z = x ∗ y ∗ z
can be understood in terms of lambda expressions.