Programming Language Concepts/Higher Order Functions
Programming Language Concepts/Higher Order
Functions
Onur Tolga Şehitoğlu
Computer Engineering
13 April 2009
Programming Language Concepts/Higher Order Functions
Outline
1 Lambda Calculus
2 Introduction
3 Functions
Curry
Map
Filter
Reduce
Fold Left
Iterate
Value Iteration (for)
4 Higher Order Functions in C
5 Some examples
Fibonacci
Sorting
List Reverse
Programming Language Concepts/Higher Order Functions
Lambda Calculus
Lambda Calculus
1930’s by Alonso Church and Stephen Cole Kleene
Mathematical foundation for computatibility and recursion
Simplest functional paradigm language
λvar .expr
defines an anonymous function. Also called lambda
abstraction
expr can be any expression with other lambda abstractions
and applications. Applications are one at a time.
(λx.λy .x + y ) 3 4
Programming Language Concepts/Higher Order Functions
Lambda Calculus
In ‘λvar .expr ’ all free occurences of var is bound by the λvar .
Free variables of expression FV (expr )
FV (name) = {name} if name is a variable
FV (λname.expr ) = FV (expr ) − {name}
FV (M N) = FV (M) ∪ FV (N)
α conversion: expressions with all bound names changed to
another name are equivalent:
λf .f x ≡α λy .y x ≡α λz.z x
λx.x + (λx.x + y ) ≡α λt.t + (λx.x + y ) ≡α λt.t + (λu.u + y )
λx.x + (λx.x + y ) 6≡α λx.x + (λx.x + t)
Programming Language Concepts/Higher Order Functions
Lambda Calculus
β Reduction
Basic computation step, function application in λ-calculus
Based on substitution. All bound occurences of λ variable
parameter is substituted by the actual parameter
(λx.M)N 7→β M[x/N] (all x’s once bound by lambda are
substituted with N).
(λx.(λy .y + (λx.x + 1) y )(x + 2)) 5
If no further β reduction is possible, it is called a normal form.
There can be different reduction strategies but should reduce
to same normal form. (Church Rosser property)
Programming Language Concepts/Higher Order Functions
Lambda Calculus
All possible reductions of a λ-expression. All reduce to the same
normal form.
λx.(λy .y + (λx.x + 1 y ) (x + 2)) 5
λy .y + (λx.x + 1 y ) (5 + 2) λx.(λy .y + y + 1 (x + 2)) 5
5 + 2 + (λx.x + 1 (5 + 2)) λx.x + 2 + (λx.x + 1 (x + 2)) 5
5 + 2 + (λx.x + 1 (5 + 2)) λx.x + 2 + x + 2 + 1 5 λy .y + y + 1 (5 + 2)
λy .y + y + 1 (5 + 2) λx.x + 2 + x + 2 + 1 5
5+2+5+2+1
Programming Language Concepts/Higher Order Functions
Introduction
Introduction
Mathematics:
(f ◦ g )(x) = f (g (x)) , (g ◦ f )(x) = g (f (x))
“◦” : Gets two unary functions and composes a new function.
A function getting two functions and returning a new function.
in Haskell:
f x = x+x
g x = x*x
compose f u n c 1 f u n c 2 x = f u n c 1 ( f u n c 2 x )
t = compose f g
u = compose g f
t 3 = (3*3)+(3*3) = 18
u 3 = (3+3)*(3+3) = 36
compose: (β → γ) → (α → β) → α → γ
Programming Language Concepts/Higher Order Functions
Introduction
“compose” function is a function getting two functions as
parameters and returning a new function.
Functions getting one or more functions as parameters are
called Higher Order Functions.
Many operations on functional languages are repetition of a
basic task on data structures.
Functions are first order values → new general purpose
functions that uses other functions are possible.
Programming Language Concepts/Higher Order Functions
Functions
Curry
Functions/Curry
Cartesian form vs curried form:
α × β → γ vs α → β → γ
Curry function gets a
binary function in cartesian form and converts it to curried form.
curry f x y = f (x ,y)
add ( x , y ) = x+y
increment = curry add 1
-- -
increment 5
6
curry: (α × β → γ) → α → β → γ
Haskell library includes it as curry.
Programming Language Concepts/Higher Order Functions
Functions
Map
Functions/Map
square x = x*x
day no = case no of 1 -> " mon " ; 2 -> " tue " ; 3 -> " wed " ;
4 -> " thu " ; 5 -> " fri " ; 6 -> " sat " ; 7 -> " sun "
map f u n c [] = []
map f u n c ( e l : r e s t ) = ( f u n c e l ):( map f u n c r e s t )
-- --
map s q u a r e [1 ,3 ,4 ,6]
[1 ,9 ,6 ,36]
map day [1 ,3 ,4 ,6]
[ " mon " ," wed " ," thu " ," sat " ]
map:(α → β) → [α] → [β]
Gets a function and a list. Applies the function to all elements
and returns a new list of results.
Haskell library includes it as map.
Programming Language Concepts/Higher Order Functions
Functions
Filter
Functions/Filter
i s e v e n x = if mod x 2 == 0 then True else False
i s g r e a t e r x = x >5
filter f u n c [] = []
filter f u n c ( e l : r e s t ) = if f u n c e l then
e l :( filter f u n c r e s t )
else ( filter f u n c r e s t )
-- --
filter i s e v e n [1 ,2 ,3 ,4 ,5 ,6 ,7]
[2 ,4 ,6]
filter i s g r e a t e r [1 ,2 ,3 ,4 ,5 ,6 ,7]
[6 ,7]
filter:(α → Bool) → [α] → [α]
Gets a boolean function and a list. Returns a list with only
members evaluated to True by the boolean function.
Haskell library includes it as filter.
Programming Language Concepts/Higher Order Functions
Functions
Reduce
Functions/Reduce (Fold Right)
sum x y = x + y
product x y = x * y
reduce f u n c s [] = s
reduce func s ( e l : r e s t ) = func e l ( reduce func s r e s t )
-- --
reduce sum 0 [1 ,2 ,3 ,4]
10 // 1+2+3+4+0
reduce product 1 [1 ,2 ,3 ,4]
24 // 1*2*3*4*1
reduce:(α → β → β) → β → [α] → β
Gets a binary function, a list and a seed element. Applies
function to all elements right to left with a single value.
reduce f s [a1 , a2 , ..., an ] = f a1 (f a2 (.... (f an s)))
Haskell library includes it as foldr.
Programming Language Concepts/Higher Order Functions
Functions
Reduce
Sum of a numbers in a list:
listsum = reduce sum 0
Product of a numbers in a list:
listproduct = reduce product 1
Sum of squares of a list:
squaresum x = reduce sum 0 (map square x)
Programming Language Concepts/Higher Order Functions
Functions
Fold Left
Functions/Fold Left
subtract x y = x - y
foldl f u n c s [] = s
foldl f u n c s ( e l : r e s t ) =
foldl f u n c ( f u n c s e l ) r e s t
-- --
r e d u c e subtract 0 [1 ,2 ,3 ,4]
-2 // 1 -(2 -(3 -(4 -0)))
foldl subtract 0 [1 ,2 ,3 ,4]
-10 // ((((0 -1) -2) -3) -4)
foldl:(α → β → α) → α → [β] → α
Reduce operation, left associative.:
reduce f s [a1 , a2 , ..., an ] = f (f (f ...(f s a1 ) a2 ...)) an
Haskell library includes it as foldl.
Programming Language Concepts/Higher Order Functions
Functions
Iterate
Functions/Iterate
t w i c e x = 2* x
iterate func s 0 = s
iterate f u n c s n = f u n c ( iterate f u n c s (n -1))
-- --
iterate twice 1 4
16 // t w i c e ( t w i c e ( t w i c e ( t w i c e 1))
iterate square 3 3
6561 // s q u a r e ( s q u a r e ( s q u a r e 3))
iterate:(α → α) → α → int → α
Applies same function for given number of times, starting with
the initial seed value. iterate f s n = f n s = f (f (f ...(f s))
| {z }
n
Programming Language Concepts/Higher Order Functions
Functions
Value Iteration (for)
Functions/Value Iteration (for)
f o r func s m n =
if m>n then s
else f o r f u n c ( f u n c s m) (m+1) n
-- --
f o r sum 0 1 4
10 // sum ( sum ( sum ( sum 0 1) 2) 3) 4
f o r product 1 1 4
24 // product ( product ( product ( product 1 1) 2) 3) 4
for:(α → int → α) → α → int → int → α
Applies a binary integer function to a range of integers in
order.
for f s m n = f (f (f (f (f s m) (m + 1)) (m + 2)) ...) n
Programming Language Concepts/Higher Order Functions
Functions
Value Iteration (for)
multiply (with summation):
multiply x = iterate (sum x) x
integer power operation (Haskell ’^’):
power x = iterate (product x) x
sum of values in range 1 to n:
seriessum = for sum 0 1
Factorial operation:
factorial = for product 1 1
Programming Language Concepts/Higher Order Functions
Higher Order Functions in C
Higher Order Functions in C
C allows similar definitions based on function pointers. Example:
bsearch() and qsort() funtions in C library.
typedef struct P e r s o n { char name [30]; int no ;} p e r s o n ;
int cmpnmbs( void *a , void *b) {
p e r s o n * ka =( p e r s o n *) a ; p e r s o n * kb =( p e r s o n *) b;
return ka - > no - kb - > no ;
}
int cmpnames( void *a , void *b) {
p e r s o n * ka =( p e r s o n *) a ; p e r s o n * kb =( p e r s o n *) b;
return s t r n c m p ( ka - >name , kb - >name ,30);
}
int main () { int i ;
p e r s o n l i s t []={{ " veli " ,4} ,{ " ali " ,12} ,{ " ayse " ,8} ,
{ " osman " ,6} ,{ " fatma " ,1} ,{ " mehmet " ,3}};
q s o r t ( l i s t ,6 , sizeof ( p e r s o n ) ,cmpnmbs);
...
q s o r t ( l i s t ,6 , sizeof ( p e r s o n ) , cmpnames );
...
}
Programming Language Concepts/Higher Order Functions
Some examples
Fibonacci
Fibonacci
Fibonacci series: 1 1 2 3 5 8 13 21 ..
fib(0) = 1 ; fib(1) = 1 ; fib(n) = fib(n − 1) + fib(n − 2)
f i b n = let f ( x , y ) = ( y , x + y )
(a ,b) = iterate f (0 ,1) n
in b
-- --
fib 5 // f ( f ( f ( f (0 ,1))))
8 //(0 ,1) - >(1 ,1) - >(1 ,2) - >(2 ,3) - >(3 ,5) - >(5 ,8)
Programming Language Concepts/Higher Order Functions
Some examples
Sorting
Sorting
Quicksort:
1 First element of the list is x and rest is xs
2 select smaller elements of xs from x, sort them and put
before x.
3 select greater elements of xs from x, sort them and put after
x.
n o t f u n c f x y = not ( f x y )
sort [] = []
sort f u n c ( x : x s ) = ( sort f u n c ( filter ( f u n c x ) x s )) ++
( x : ( sort f u n c ( filter (( n o t f u n c f u n c ) x ) x s )))
-- -
sort ( >) [5 ,3 ,7 ,8 ,9 ,3 ,2 ,6 ,1]
[1 ,2 ,3 ,3 ,5 ,6 ,7 ,8 ,9]
sort ( <) [5 ,3 ,7 ,8 ,9 ,3 ,2 ,6 ,1]
[9 ,8 ,7 ,6 ,5 ,3 ,3 ,2 ,1]
Programming Language Concepts/Higher Order Functions
Some examples
List Reverse
List Reverse
Taking the reverse
First element is x rest is xs
Reverse the xs, append x at the end
Loose time for appending x at the end at each step (N times append of size N).
Fast version, extra parameter (initially empty list) added:
Take the first element, insert at the beginning of the extra parameter.
Recurse rest of the list with the new extra parameter.
When recursion at the deepest, return the extra parameter.
Inserts to the beginning of the list at each step. Faster (N times insertion)
r e v e r s e 1 [] = []
r e v e r s e 1 ( x : x s ) = ( r e v e r s e 1 x s ) ++ [ x ]
r e v e r s e 2 x = r e v e r s e 2 ’ x [] where
r e v e r s e 2 ’ [] x = x
reverse2 ’ (x: xs ) y = reverse2 ’ xs (x:y)
-- -
r e v e r s e 1 [1..10000] // s l o w
r e v e r s e 2 [1..10000] // f a s t
