Transcript Functional Programming, an introduction

Functional Programming, an
introduction
Program looks like function 
The contents here are from
Miranda book and haskell.org
Why use functional programming
• Substantially increased programmer productivity
(Ericsson measured an improvement factor of
between 9 and 25 in one set of experiments on
telephony software).
• Shorter, clearer, and more maintainable code.
• Fewer errors, higher reliability.
• A smaller "semantic gap" between the
programmer and the language.
• Shorter lead times.
• Functional languages are superb for
writing specifications which can actually be
executed (and hence tested and
debugged).
What is functional
programming?
• A functional program is a single
expression, which is executed by
evaluating the expression.
• The focus is on what is to be computed,
not how it should be computed. For
example:
Some example Haskell
square x = x*x
area = square side
min x y =
| x<=y = x
|otherwise = y
• We can run it using “min 3 4”
• The result is 3
The point is expression evaluation
• Square (3+4) square 7  7*7 49
Reduce by our definition
Can’t reduce any more.
We call this a normal form, or
Canonical form
Quicksort
concat
qsort [] = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort
elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
elts_lt_x is the list of all y's such that y
is drawn from the list xs, and y is less than x
Our Quicksort has polymorphism
• It can compare anything that < or > can
compare
When C is better
• In applications where performance is
required at any cost, or when the goal is
detailed tuning of a low-level algorithm, an
imperative language like C would probably
be a better choice than Haskell, exactly
because it provides more intimate control
over the exact way in which the
computation is carried out.
Haskell types
• Basic: Int, Double and String
• Lists
–
–
–
–
Lists is a standard data type in Haskell
The nil list, or the "empty list", is written [].
[1,2,3,4] = 1:2:3:4:[]. : is called “cons”
A list can be constructed from any type (even
functions or user defined types), but all elements
must be of the same type.
– list from 1 to 10 we write [1..10]
– [1,3..100], the first two elements give the "step" of
the sequence.
• Tuples
– We can group types together into tuples.
– For instance (2,4) is the tuple of the Ints 2 and 4.
– Maybe you want to return two values from a function
, in Haskell you just return a tuple of two data types)
– Tuples aren't restricted to just two elements, (1,2,3)
is the 3-tuple of the Ints 1,2 and 3.
– Any data type can be put inside a tuple, even the
ones you define yourself.
– Contents of the tuple can be of differing types:
("Haskell", [1,2,3], 4.5).
– Note that a list is also considered a type and can thus
be put inside a tuple - this works the other way as
well, you can have a list of tuples.
function
• What is a function
– A function takes a set of inputs, and returns a set of
output.
– A program in Haskell is just a single function.
– A function in Haskell is also a value.
– You can pass a function as a parameter to another
function, for instance.
– A function can also be returned by another function.
You can even put a function in a list, or any other
data construct.
f a b c = a+b+c
• function name, f,
• and then the parameters a, b and c.
• On the right hand side of the equation
comes the expression which the function
will evaluate
• To call a function
g=f123
• g a function with zero parameters that
returns the expression on the right hand
side.
• no paranthesis in function calls
• Parenthesis is used for grouping only.
h = f (1+2) (2+3) (3+4)
Partial application
• f above is a function with three parameters, but that's not the whole
truth. Consider this function, which we define in terms of f
jab=f5ab
• The function j takes two parameters which are added together with
the integer 5.
Now we will take a look at an alternate definition of this function.
i=f5
• This function is completely equivalent with the function j above. So
how can that be?
• We state that the function i is equal to the function f passed only a
single parameter, 5.
• But f was supposed to take three parameters, surely this must be a
programming error?
• This is completely valid Haskell syntax.
• What this means is that you apply 5 to f, the result of
this is a function that takes the two remaining
parameters.
• You can think of it as f "waiting" for the rest of the
parameters. Thus i will be a function of two parameters,
the two parameters that f is "waiting" for.
• A nice way to think of this is that all functions are really
just a function of zero or a single parameter.
• The function f a b c is the function that takes one
parameter, a, and returns a function that takes the
remaining two parameters, b and c.
• This function is in turn a function that also takes a single
parameter, b, and returns a function that takes the last
parameter, c.
• This takes a single parameter, c, and returns the
function of zero parameters that returns the value of
a+b+c.
mul a b = a*b
• All this function does is multiply its two parameters. We
can now use this in conjunction with partial application to
define this function
double = mul 2
• We pass 2 to the function mul.
• Now 2 is bound to the variable a.
• This means that mul is "waiting" for the value of b. In
other words; the result of mul 2 is a function taking the
second parameter and multiplying it with two.
• So since the value of the right hand side is a function of
one parameter, double must also be a function of one
parameter. We can write this explicitly if we wish:
double x = mul 2 x
Type signatures
• Notice that we have not written out any type signatures on any of
the functions above.
• This isn't needed, Haskell will infer it automatically
mul :: Int -> Int -> Int
mul a b = a*b
A function from Int to Int to Int
(Note that this definition of mul will only work on ints, whereas the
version where we omitted the type signature will work for any type
which as the * operator defined.)
• Normally you consider the last part of the type
signature to denote the type of the output.
• But if you take partial application into account
you could just as well consider the function mul
to be "a function that goes from an Int to a
function that goes from Int to Int".
– In other words the output of the function is another
function ("from Int to Int").
mul :: Int -> (Int -> Int)
mul a b = a*b
• The type signature of a "variable" (or a
function with zero parameters) is just
a :: String
a = "Hello"
We just say that a is of type String (no
arrows, unlike function).
Higher Order Functions
• functions that take another function as a parameter
• it is the whole point of Haskell
• twice :: (Int -> Int) -> Int -> Int
twice f value = f (f value)
• As we can see from the type signature this function will
take a function of type "Int to Int" as a parameter, and
then a value of type Int, then it will return a value of type
Int.
We can see from the definition that it will apply the
function (which we assign the name f ), and then apply
the function to the result.
• f ( g x)
• function composition
• We can redefine twice like:
twice :: (Int -> Int) -> Int -> Int
twice f = f . f
• The . operater will apply the right most
function to the parameter, and then the left
most function to the result.
• We can use our “twice” for any function
• quadruple :: Int -> Int
quadruple = twice double
Pattern Matching and Recursion
• Let's define a recursive factorial function in
Haskell:
fac :: Int -> Int
fac 0 = 1
fac n = fac (n-1) * n
Haskell will
continue down to
try to find a pattern
that matches (top
first).
Matching Higher Order Function
map :: (Int -> Int) -> [Int] -> [Int]
map f [] = []
map f (x:xs) = f x : map f xs
• apply a function to all elements of a list
• Try …. map double [1,2]
• Summing elements in the list
sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs
• We can parameterize the function which is used
on the list to combine the elements of the list.
• So we'll need to pass
– the function (which was +, in the case of sum)
– and the base case (which was 0 in the case of sum).
• foldr :: (Int -> Int -> Int) -> Int -> [Int] -> Int
foldr func base [] = base
foldr func base (x:xs) = x `func` (foldr func base xs)
"fold right".
• It take some function, func, and apply it to each element
and the rest of the list ("folding it", into the list), exactly like
we use + in the sum function.
• The base value is the identity value of the function, for the
sum function this was 0. It's the value which is returned
for the empty list.
• There's a bit of new syntax here. By enclosing a function
of two parameters like so `func` we can actually make
that function an infix operator (like + and *). The reverse is
also possible, to transform an infix operator you enclose it
in paranthesis (for example you could write (+) 4 3, to add
3 and 4, just as well as 4 + 3).
• Now let's redefine the sum function using our
new foldr function.
sum :: [Int] -> Int
sum = foldr (+) 0
• Let's define another function, product,
using foldr
product :: [Int] -> Int
product = foldr (*) 1
Lambda Functions
• construct a function on the fly.
\a b c -> expr
• The starting backslash is meant to look like a lambda symbol.
• The a b, and c are the parameters, then there's an arrow and after that
the expression.
• The advantage of this notation is that you can create unnamed
functions which can come in handy when you wish to map some
operation on a list, for instance:
func xs b = map (\a -> 2*a-b) xs
• Here we create a function on the fly and send it off to the map function.
So for small functions this can be very convenient.
The where notation
• What if we have a function definition that won't fit on a
single line?
• We can use the where-notation to rewrite the map function
above.
map :: (Int -> Int) -> [Int] -> [Int]
map f [] = []
map f (x:xs) = f x : mapped
where mapped = map f xs
• Basically you can put a where clause underneath a
function and make definitions there which can be used in
the function itself.
• These definitions are in the same scope as the function
itself and as such it has access to the parameters of the
function.