Lecture 7: Higher-Order Functions

Jean-No el Monette

Functional Programming 1 September 25, 2012

Based on notes by Pierre Flener, Sven-Olof Nystr om

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

1 / 50

Today

Introductory Examples Higher-order functions on lists More Examples Example: Polymorphic Ordered Binary Tree Higher-Order Functions on Trees Lazy Evaluation

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

2 / 50

Introductory Examples

Table of Contents

Introductory Examples Higher-order functions on lists More Examples Example: Polymorphic Ordered Binary Tree Higher-Order Functions on Trees Lazy Evaluation

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

3 / 50

Introductory Examples

Reminder

An anonymous function: a function without a name. fun double x = 2x val double = fn x => 2x are equivalent. So are double 42 ( fn x => 2x) 42

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

4 / 50

Introductory Examples

Insertion Sort on Integers

fun insert x [] = [x] | insert x (y :: ys) = if x < y then x :: y :: ys else y :: ( insert x ys ); fun isort [] = [] | isort (x :: xs) = insert x ( isort xs ); How to sort in general (not only integer)?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

5 / 50

Introductory Examples

Insertion Sort on any type

fun insert order x [] = [x] | insert order x (y :: ys) = if order(x,y) then x :: y :: ys else y :: ( insert order x ys ); fun isort order [] = [] | isort order (x :: xs) = insert order x ( isort order xs ); What is the type of the dierent functions? Exercise (at home): redene the merge sort to be polymorphic.

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

6 / 50

Introductory Examples

Example (cont.)

> isort ( op <) [6,3,0,1,7,8,5,9,2,4]; val it = [0,1,2,3,4,5,6,7,8,9]: int list > isort ( op >) [6,3,0,1,7,8,5,9,2,4]; val it = [9,8,7,6,5,4,3,2,1,0]: int list > isort String.< [one,two,three,four, ve , six ,seven ]; val it = [ ve ,four,one,seven, six ,three,two]: string list > isort ( op <); val it = fn: int list > int list > isort String.< ; val it = fn: string list > string list > isort ( fn (( ,s1 ),( ,s2)) => String.<(s1,s2)) [(1, one ),(2, two),(3,three ),(4, four ),(5, ve ),(6, six ),(7, sev val it = [(5, ve ),(4, four ),(1, one ),(7, seven ),(6, six ),(3, thre (2,two)]: ( int string ) list
Jean-No el Monette (UU) Lecture 7: Higher-Order Functions 7 / 50

Introductory Examples

Higher-order functions

A higher-order function: a function that either takes functions as arguments or returns functions as result. Remarks This is hard to do in an imperative programming language This is a very powerful mechanism

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

8 / 50

Introductory Examples

Reection on the denition of sum

fun sum [] = 0 | sum (x:: l ) = x + sum l; There are only two places in the function denition that are specic for computing a sum: +, combining data 0, result for empty list

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

9 / 50

Introductory Examples

A generalization

Lets dene a function reduce so that reduce + 0 is equal to sum fun reduce f z [] = z | reduce f z (x :: l ) = f(x,reduce f z l ); fun reduce f z = (fn [] => z | (x :: l ) => f(x,reduce f z l )); Note the similarity between reduce and sum.

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

10 / 50

Introductory Examples

Generalization (cont.)

Now, sum can be dened as fun sum xs = reduce (op +) 0 xs; val sum = reduce (op +) 0;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

11 / 50

Introductory Examples

Other uses of reduce

What will the following compute? reduce ( op ) 1 [1,2,3,4]; reduce Int .max 0 [1,2,3,44,5,6]; reduce ( fn (x,y) => x::y) [] [1,2,3,4]; reduce ( fn (x,y) => x::y) [5,6,7] reduce ( fn (x,y) => x::x::y) [] reduce ( op @) [] [1,2,3,4]; [1,2,3,4];

[[1,2],[34],[5,6,7,89]];

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

12 / 50

Introductory Examples

Function composition
A function that takes two functions and returns a function! fun o ( f ,g) x = f(g(x )); inx o; o is predened. No need to dene it. fun add1 x = x + 1; (add1 o add1) 42;

Exercise: Find values id1 and id2 so that (id1 o f ) x = f x ( for all f , x ) ( f o id2) x = f x ( for all f , x )
Jean-No el Monette (UU) Lecture 7: Higher-Order Functions 13 / 50

Introductory Examples

Pair
Another way of building functions: > fun pair ( f ,g) x = (f x, g x ); val pair = fn: ( a > b) (a > c) > a > b c > pair(add1,add1 o add1); val it = fn: int > int int > it 42; val it = (43,44): int int > pair( pair (add1,add1 o add1), add1); val it = fn: int > (int int ) int > it 42; val it = ((43,44),43): ( int int ) int

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

14 / 50

Higher-order functions on lists

Table of Contents

Introductory Examples Higher-order functions on lists More Examples Example: Polymorphic Ordered Binary Tree Higher-Order Functions on Trees Lazy Evaluation

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

15 / 50

Higher-order functions on lists

Higher-order functions on lists

Several functions are very useful to dene operations on lists. > map; val it = fn: > foldr ; val it = fn: > foldl ; val it = fn: > List . lter val it = fn: ( a > b) > a list > b list ( a b > b) > b > a list > b ( a b > b) > b > a list > b ; ( a > bool) > a list > a list

Those functions are predened in ML, but we will see the details.

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

16 / 50

Higher-order functions on lists

The map function

Apply the same operation on all the elements of a list. ( PRE: (none) POST: [f(a 1), f (a 2 ), ..., f (a n )], if L = [a 1,a 2, ..., a n] ) > fun map f [ ] = [ ] | map f (x :: xs) = f x :: map f xs; val map = fn: (a > b) > a list > b list > fun square x = xx; val square = fn: int > int > map square [1,2,3,4]; val it = [1,4,9,16]: int list > map (fn(x)=> if x < 3 then 0 else x) [1,2,3,4]; val it = [0,0,3,4]: int list

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

17 / 50

Higher-order functions on lists

The map function (cont.)

> map square; val it = fn: int list > int list > map (map square); val it = fn: int list list > int list list > map (map square) [[1,2,34],[5]]; val it = [[1,4,1156],[25]]: int list list > map String.<; val it = fn: ( string string ) list > bool list > map String.< [(a,ab), ( hello , bye )]; val it = [true , false ]: bool list

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

18 / 50

Higher-order functions on lists

Foldr and foldl

fun foldr f b [] = b | foldr f b (x :: xs) = f(x, foldr f b xs ); fun foldl f b [] = b | foldl f b (x :: xs) = foldl f ( f (x, b)) xs ; Do they remind you of any function you have seen before? Which one is tail-recursive?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

19 / 50

Higher-order functions on lists

Examples

Sum the elements of the list. foldr ( op +) 0 [0,2,21,4,6]; foldl ( op +) 0 [0,2,21,4,6]; Are they equivalent? Which one would you use? Why?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

20 / 50

Higher-order functions on lists

Examples (cont.)

Check that all elements of a list are even foldr ( fn (x,y) => y andalso x mod 2 = 0) true [0,2,21,4,6]; foldl ( fn (x,y) => y andalso x mod 2 = 0) true [0,2,21,4,6]; Are they equivalent? Which one would you use? Why?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

21 / 50

Higher-order functions on lists

Examples (cont.)

Compare foldr ( op ::) []; foldl ( op ::) []; Are they equivalent? Which one would you use? Why?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

22 / 50

Higher-order functions on lists

Examples (cont.)

What does this function compute? fun rstEven (x,NONE) = if x mod 2 = 0 then SOME x else NONE | rstEven ( , SOME y) = SOME y; Compare foldl rstEven NONE; foldr rstEven NONE; Are they equivalent? Which one would you use for what?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

23 / 50

Higher-order functions on lists

More examples

Try foldl ( fn (x,n) => n+1) 0 foldr ( fn (x,n) => n+1) 0 foldr ( fn (x,n) => x) 0 foldl ( fn (x,n) => x) 0 fun mystery f = foldr ( fn (x,n) => f x :: n) [];

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

24 / 50

Higher-order functions on lists

Filter
( PRE: (none) POST: the list of elements of the list for which p is true ) fun lter p [] = [] | lter p (x :: xs) = if p x then x :: lter p xs else lter p xs ; Examples: lter ( fn (x) => x<6); lter ( fn (x) => x<6) [6,3,0,1,8,5,9,3];

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

25 / 50

More Examples

Table of Contents

Introductory Examples Higher-order functions on lists More Examples Example: Polymorphic Ordered Binary Tree Higher-Order Functions on Trees Lazy Evaluation

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

26 / 50

More Examples

Folding over integers

Fold over integers (really natural numbers) gives us a general way to recurse over natural numbers fun foldint | foldint foldint ( op foldint ( op foldint ( fn f b0 =b f b n = foldint f ( f (b,n)) (n1); + ) 0 5; ) 1 5; ((a,b), ) => (a+b, a)) (1,1) 10;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

27 / 50

More Examples

Folding over integers (cont.)

fun td a = foldint ( fn (b,n) => b andalso (n <= 1 orelse a mod n <> 0)) true (a1); fun primes n = foldint ( fn ( l , n) => if td n then n:: l else l ) [] n;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

28 / 50

More Examples

twice and ntimes

We can dene a function that tells us how to do something twice: fun twice f = f o f ; fun add1 x = x+1; twice add1 56; Or more generally, do something n times: fun ntimes 0 f x = x | ntimes n f x = ntimes (n1) f (f x ); ntimes 42 twice ;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

29 / 50

Example: Polymorphic Ordered Binary Tree

Table of Contents

Introductory Examples Higher-order functions on lists More Examples Example: Polymorphic Ordered Binary Tree Higher-Order Functions on Trees Lazy Evaluation

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

30 / 50

Example: Polymorphic Ordered Binary Tree

Binary search trees

A Binary search tree is a binary tree which is ordered, i.e.

All values in the left subtree are smaller than the value of the root. All values in the right subtree are larger than the value of the root.

The order can be dened for any type. We will consider the values to be pairs:
The rst element is the key. The second is the value that we want to associate with the key.

i.e. we dene a dictionary.

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

31 / 50

Example: Polymorphic Ordered Binary Tree

Binary search trees

datatype (a , b) bsTree = Void | Bst of ( a , b) bsTree ( a b) ( a , b) bsTree; Note: We want the key to be of some equality type. The order is not part of the datatype. It is possible to build a bsTree that is not ordered.

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

32 / 50

Example: Polymorphic Ordered Binary Tree

Retrieving an element

( PRE: the tree is ordered . POST: if the tree contains the key, return the corresponding value embedded in SOME. NONE otherwise ) fun retrieve lessThan k Void = NONE | retrieve lessThan key (Bst ( left ,( k,v ), right )) = if key = k then SOME v else if lessThan (key,k) then retrieve lessThan key left else retrieve lessThan key right ;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

33 / 50

Example: Polymorphic Ordered Binary Tree

Retrieving an element (cont.)

We may use the datatype order instead: fun retrieve compare k Void = NONE | retrieve compare key (Bst ( left ,( k,v ), right )) = case compare (key,k) of EQUAL => SOME v | LESS => retrieve compare key left | GREATER => retrieve compare key right;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

34 / 50

Example: Polymorphic Ordered Binary Tree

Inserting an element

( PRE: The tree is ordered . POST: If the tree contains the key, a tree with the value replaced . Otherwise, a tree with the (key, value) pair inserted such that the tree is ordered . ) fun insert compare (key,value) Void = Bst(Void,(key,value ), Void) | insert compare (key,value) (Bst ( left ,( k,v ), right )) = case compare (key,k) of EQUAL => Bst (left,(k,value),right ) | LESS => Bst(insert compare (key,value) left , (k,v ), right ) | GREATER => Bst(left,(k,v),insert compare (key,value) right ); Exercise: Specify and realise the exists and delete functions. (Delete is a bit more dicult.)

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

35 / 50

Example: Polymorphic Ordered Binary Tree

Functional Datatype
Consider again the previous denition of bsTree: The functional argument compare must be passed at each call The compare order is not global to the binary search tree Lets introduce the order in a new datatype: datatype (a , b) bsTree = Void | Bst of ( a , b) bsTree ( a b) ( a , b) bsTree; type a ordering = a a > order; datatype (a, b) obsTree = OrdBsTree of a ordering ( a , b) bsTree;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

36 / 50

Example: Polymorphic Ordered Binary Tree

Inserting an element

fun emptyTree compare = OrdBsTree (compare, Void); fun insert (key, value) OrdBsTree (compare, tree) = let fun insert Void = (key,value) | insert (Bst ( left ,( k,v ), right )) = case compare (key,k) of EQUAL => Bst (left,(k,value),right ) | LESS => Bst(insert left , (k,v ), right ) | GREATER => Bst(left,(k,v),insert right ) in OrdBstTree (compare, insert tree ) end;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

37 / 50

Higher-Order Functions on Trees

Table of Contents

Introductory Examples Higher-order functions on lists More Examples Example: Polymorphic Ordered Binary Tree Higher-Order Functions on Trees Lazy Evaluation

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

38 / 50

Higher-Order Functions on Trees

Higher-Order Functions on Trees

Like for lists, it is possible to dene generic functions on trees. mapbt applies some function on all elements of the tree. Dierent folding functions can be dened. We cover here binary trees, but the same might be done for other types of trees.

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

39 / 50

Higher-Order Functions on Trees

Mapping and reducing a binary tree

datatype (a) btree = Vd | Bt of a a btree a btree ; fun mapbt f Vd = Vd | mapbt f (Bt(v, l , r )) = Bt(f v, mapbt f l , mapbt f r ); fun reducebt f z Vd = z | reducebt f z (Bt(v, l , r )) = f (v,reducebt f z l ,reducebt f z r ); mapbt abs; reducebt ( fn reducebt ( fn reducebt ( fn reducebt ( fn

(v, l , r) (v, l , r) (v, l , r) (v, l , r)

=> => => =>

1 + l + r) 0; 1 + Int.max(l,r)) 0; l @ [v] @ r) []; Bt(v,r,l)) Vd;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

40 / 50

Higher-Order Functions on Trees

Exercises

Use reducebt to compute if a btree is ordered (according to some given order). Use reducebt to transform a btree into a bsTree. Dene a function map on trees (as in assignment 2).

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

41 / 50

Lazy Evaluation

Table of Contents

Introductory Examples Higher-order functions on lists More Examples Example: Polymorphic Ordered Binary Tree Higher-Order Functions on Trees Lazy Evaluation

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

42 / 50

Lazy Evaluation

Lazy evaluation

Idea: Do not evaluate the arguments of a function call before we know that they will be needed. Similarly, when computing a datastructure or a list, dont compute the components before we know that they are needed. In a functional programming language with lazy evaluation, it is meaningful to write a function that creates (for example) a list of all integers or a list of all prime numbers. A second function might call the rst and print the rst 100. fun ints n = n :: ints (n+1); does not terminate in SML.

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

43 / 50

Lazy Evaluation

Simulating lazy evaluation

In SML (or any other programming language with eager evaluation and higher-order functions) we can simulate a value computed by lazy evaluation by a function. Indeed, in the following code, the addition is only perfomed in the second line: val lazyFive = (fn () => 3 + 2); val ve = lazyFive ();

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

44 / 50

Lazy Evaluation

Example: lazy mult

fun mult x y = if x = 0 then 0 else x y; fun lazyMult x y = if x() = 0 then 0 else x() y (); What are the types of the functions?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

45 / 50

Lazy Evaluation

Example: lazy mult

mult (11) (3 div 0); ( fn x => fn y => if x=0 then 0 else xy) (11) (3 div 0); ( fn x => fn y => if x=0 then 0 else xy) 0 (3 div 0); ( fn y => if 0=0 then 0 else 0y) (3 div 0); ( fn y => if 0=0 then 0 else 0y) ( raise Div); raise Div; lazyMult ( fn () => 11) (fn() => 3 div 0); ( fn x => fn y => if x()=0 then 0 else x()y()) ( fn () => 11) (fn() => 3 div 0); ( fn y => if (fn () => 11)()=0 then 0 else (fn() => 11)()y()) (fn() => 3 div 0); if ( fn () => 11)()=0 then 0 else (fn() => 11)()(fn() => 3 div 0)(); if 0=0 then 0 else (fn () => 11)()(fn() => 3 div 0)(); if true then 0 else ( fn () => 11)()(fn() => 3 div 0)(); 0;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

46 / 50

Lazy Evaluation

Simulating innite sequences

Innite sequences can either be represented: as a function f i = xi where xi is the ith element or as a pair datatype composed of
the rst value, and a function that gives us the next pair.

Question: how would you dene basic list operations such as hd, tl, map for these representations?

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

47 / 50

Lazy Evaluation

First approach

fun ints i = i; fun zeroes i = 0; fun fToList n f = let fun aux m = if m>=n then [] else f m :: aux (m+1); in aux 0 end; fToList 7 ints ;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

48 / 50

Lazy Evaluation

Second approach

datatype (a) seq = Pair of a ( unit > a seq); fun ints n = Pair(n,( fn () => ints (n+1))); fun sToList 0 f = [] | sToList n f = let val Pair(v,next) = f() in v :: sToList (n1) next end; sToList 7 ( fn () => ints 0);

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

49 / 50

Lazy Evaluation

End Note

A good implementation of a lazy languages must make sure that the value of a subexpression is never computed more than once. The solutions presented here do not have that property. val val val val lazyFive = (fn () => 3 + 2); six = lazyFive() + 1; seven = lazyFive() + 2; height = lazyFive() + 3;

Jean-No el Monette (UU)

Lecture 7: Higher-Order Functions

50 / 50