Transcript examples

PROGRAMMING IN HASKELL
Chapter 9 - Higher-Order Functions,
Functional Parsers
0
Introduction
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)
twice is higher-order because it
takes a function as its first argument.
1
Why Are They Useful?
 Common programming idioms can be encoded
as functions within the language itself.
 Domain specific languages can be defined as
collections of higher-order functions.
 Algebraic properties of higher-order functions
can be used to reason about programs.
2
The Map Function
The higher-order library function called map applies
a function to every element of a list.
map :: (a  b)  [a]  [b]
For example:
> map (+1) [1,3,5,7]
[2,4,6,8]
3
The map function can be defined in a particularly
simple manner using a list comprehension:
map f xs = [f x | x  xs]
Alternatively, for the purposes of proofs, the map
function can also be defined using recursion:
map f []
= []
map f (x:xs) = f x : map f xs
4
The Filter Function
The higher-order library function filter selects every
element from a list that satisfies a predicate.
filter :: (a  Bool)  [a]  [a]
For example:
> filter even [1..10]
[2,4,6,8,10]
5
Filter can be defined using a list comprehension:
filter p xs = [x | x  xs, p x]
Alternatively, it can be defined using recursion:
filter p []
= []
filter p (x:xs)
| p x
= x : filter p xs
| otherwise
= filter p xs
6
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  f xs
f maps the empty list to some value v, and
any non-empty list to some function 
applied to its head and f of its tail.
7
For example:
sum []
= 0
sum (x:xs) = x + sum xs
v=0
=+
product []
= 1
product (x:xs) = x * product xs
and []
= True
and (x:xs) = x && and xs
v=1
=*
v = True
 = &&
8
The higher-order library function foldr (fold right)
encapsulates this simple pattern of recursion, with
the function  and the value v as arguments.
For example:
sum
= foldr (+) 0
product = foldr (*) 1
or
= foldr (||) False
and
= foldr (&&) True
9
Foldr itself can be defined using recursion:
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 non-recursively,
as simultaneously replacing each (:) in a list by a
given function, and [] by a given value.
10
For example:
=
=
=
sum [1,2,3]
foldr (+) 0 [1,2,3]
foldr (+) 0 (1:(2:(3:[])))
1+(2+(3+0))
=
6
Replace each (:)
by (+) and [] by 0.
11
For example:
=
=
=
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.
12
Other Foldr Examples
Even though foldr encapsulates a simple pattern
of recursion, it can be used to define many more
functions than might first be expected.
Recall the length function:
length
length []
:: [a]  Int
= 0
length (_:xs) = 1 + length xs
13
For example:
=
=
=
length [1,2,3]
length (1:(2:(3:[])))
1+(1+(1+0))
3
Hence, we have:
Replace each (:)
by _ n  1+n
and [] by 0.
length = foldr (_ n  1+n) 0
14
Now recall the reverse function:
reverse []
= []
reverse (x:xs) = reverse xs ++ [x]
For example:
=
=
=
reverse [1,2,3]
Replace each (:) by
x xs  xs ++ [x]
and [] by [].
reverse (1:(2:(3:[])))
(([] ++ [3]) ++ [2]) ++ [1]
[3,2,1]
15
Hence, we have:
reverse =
foldr (x xs  xs ++ [x]) []
Finally, we note that the append function (++) has a
particularly compact definition using foldr:
(++ ys) = foldr (:) ys
Replace each
(:) by (:) and
[] by ys.
16
Why Is Foldr Useful?
 Some recursive functions on lists, such as sum,
are simpler to define using foldr.
 Properties of functions defined using foldr can
be proved using algebraic properties of foldr,
such as fusion and the banana split rule.
 Advanced program optimisations can be simpler
if foldr is used in place of explicit recursion.
17
Other Library Functions
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)
For example:
odd :: Int  Bool
odd = not . even
18
The library function all decides if every element of
a list satisfies a given predicate.
all
:: (a  Bool)  [a]  Bool
all p xs = and [p x | x  xs]
For example:
> all even [2,4,6,8,10]
True
19
Dually, the library function any decides if at least
one element of a list satisfies a predicate.
any
:: (a  Bool)  [a]  Bool
any p xs = or [p x | x  xs]
For example:
> any isSpace "abc def"
True
20
The library function takeWhile selects elements from
a list while a predicate holds of all the elements.
takeWhile :: (a 
takeWhile p []
takeWhile p (x:xs)
| p x
| otherwise
Bool)  [a]  [a]
= []
= x : takeWhile p xs
= []
For example:
> takeWhile isAlpha "abc def"
"abc"
21
Dually, the function dropWhile removes elements
while a predicate holds of all the elements.
dropWhile :: (a 
dropWhile p []
dropWhile p (x:xs)
| p x
| otherwise
Bool)  [a]  [a]
= []
= dropWhile p xs
= x:xs
For example:
> dropWhile isSpace "
abc"
"abc"
22
Exercises
(1) What are higher-order functions that return
functions as results better known as?
(2) Express the comprehension [f x | x  xs, p x]
using the functions map and filter.
(3) Redefine map f and filter p using foldr.
23
What is a Parser?
A parser is a program that analyses a piece of text
to determine its syntactic structure.
+
23+4
means

2
4
23
24
Where Are They Used?
Almost every real life program uses some form of
parser to pre-process its input.
Haskell programs
Hugs
Unix
Explorer
parses
Shell scripts
HTML documents
25
The Parser Type
In a functional language such as Haskell, parsers
can naturally be viewed as functions.
type Parser = String  Tree
A parser is a function that takes a string
and returns some form of tree.
26
However, a parser might not require all of its input
string, so we also return any unused input:
type Parser = String  (Tree,String)
A string might be parsable in many ways, including
none, so we generalize to a list of results:
type Parser = String  [(Tree,String)]
27
Finally, a parser might not always produce a tree,
so we generalize to a value of any type:
type Parser a = String  [(a,String)]
Note:
 For simplicity, we will only consider parsers that
either fail and return the empty list of results, or
succeed and return a singleton list.
28
Basic Parsers
 The parser item fails if the input is empty, and
consumes the first character otherwise:
item :: Parser Char
item
= inp  case inp of
[]
 []
(x:xs)  [(x,xs)]
29
 The parser failure always fails:
failure :: Parser a
failure
= inp  []
 The parser return v always succeeds, returning
the value v without consuming any input:
return
:: a  Parser a
return v = inp  [(v,inp)]
30
 The parser p +++ q behaves as the parser p if it
succeeds, and as the parser q otherwise:
(+++)
:: Parser a  Parser a  Parser a
p +++ q = inp  case p inp of
[]
 parse q inp
[(v,out)]  [(v,out)]
 The function parse applies a parser to a string:
parse :: Parser a  String  [(a,String)]
parse p inp = p inp
31
Examples
The behavior of the five parsing primitives can be
illustrated with some simple examples:
% hugs Parsing
> parse item ""
[]
> parse item "abc"
[('a',"bc")]
32
> parse failure "abc"
[]
> parse (return 1) "abc"
[(1,"abc")]
> parse (item +++ return 'd') "abc"
[('a',"bc")]
> parse (failure +++ return 'd') "abc"
[('d',"abc")]
33
Note:
 The library file Parsing is available on the web
from the Programming in Haskell home page.
 For technical reasons, the first failure example
actually gives an error concerning types, but this
does not occur in non-trivial examples.
 The Parser type is a monad, a mathematical
structure that has proved useful for modeling
many different kinds of computations.
34
Sequencing
A sequence of parsers can be combined as a single
composite parser using the keyword do.
For example:
p :: Parser (Char,Char)
p
= do x  item
item
y  item
return (x,y)
35
Note:
 Each parser must begin in precisely the same
column. That is, the layout rule applies.
 The values returned by intermediate parsers
are discarded by default, but if required can
be named using the  operator.
 The value returned by the last parser is the
value returned by the sequence as a whole.
36
 If any parser in a sequence of parsers fails, then
the sequence as a whole fails. For example:
> parse p "abcdef"
[((’a’,’c’),"def")]
> parse p "ab"
[]
 The do notation is not specific to the Parser type,
but can be used with any monadic type.
37
Derived Primitives
 Parsing a character that satisfies a predicate:
sat :: (Char  Bool)  Parser Char
sat p = do x  item
if p x then
return x
else
failure
38
 Parsing a digit and specific characters:
digit :: Parser Char
digit
char
= sat isDigit
:: Char  Parser Char
char x = sat (x ==)
 Applying a parser zero or more times:
many
:: Parser a  Parser [a]
many p = many1 p +++ return []
39
 Applying a parser one or more times:
many1 :: Parser a -> Parser [a]
many1 p = do v  p
vs  many p
return (v:vs)
 Parsing a specific string of characters:
string
:: String  Parser String
string []
= return []
string (x:xs) = do char x
string xs
return (x:xs)
40
Example
We can now define a parser that consumes a list of
one or more digits from a string:
p :: Parser String
p = do char '['
d  digit
ds  many (do char ','
digit)
char ']'
return (d:ds)
41
For example:
> parse p "[1,2,3,4]"
[("1234","")]
> parse p "[1,2,3,4"
[]
Note:
 More sophisticated parsing libraries can indicate
and/or recover from errors in the input string.
42
Arithmetic Expressions
Consider a simple form of expressions built up from
single digits using the operations of addition + and
multiplication *, together with parentheses.
We also assume that:
 * and + associate to the right;
 * has higher priority than +.
43
Formally, the syntax of such expressions is defined
by the following context free grammar:
expr
 term '+' expr  term
term
 factor '*' term  factor
factor  digit  '(' expr ')‘
digit
 '0'  '1'    '9'
44
However, for reasons of efficiency, it is important to
factorise the rules for expr and term:
expr  term ('+' expr  )
term  factor ('*' term  )
Note:
 The symbol  denotes the empty string.
45
It is now easy to translate the grammar into a parser
that evaluates expressions, by simply rewriting the
grammar rules using the parsing primitives.
That is, we have:
expr :: Parser Int
expr = do t  term
do char '+'
e  expr
return (t + e)
+++ return t
46
term :: Parser Int
term = do f  factor
do char '*'
t  term
return (f * t)
+++ return f
factor :: Parser Int
factor = do d  digit
return (digitToInt d)
+++ do char '('
e  expr
char ')'
return e
47
Finally, if we define
eval
:: String  Int
eval xs = fst (head (parse expr xs))
then we try out some examples:
> eval "2*3+4"
10
> eval "2*(3+4)"
14
48
Exercises
(1) Why does factorising the expression grammar
make the resulting parser more efficient?
(2) Extend the expression parser to allow the use
of subtraction and division, based upon the
following extensions to the grammar:
expr  term ('+' expr  '-' expr  )
term  factor ('*' term  '/' term  )
49