User Tools

Site Tools


hof

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

hof [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== Higher-order functions and polymorphism ======
  
 +
 +===== Higher-order functions =====
 +
 +Functions are the "​salt"​ of functional languages: ​
 +they can appear everywhere in expressions, ​
 +they can be applied, passed as parameters, ​
 +and returned back by other functions.
 +When a function may take as input another function, or 
 +can output a function, we say it is a [[wp>​Higher-order_function|higher-order]] function.
 +
 +You have already seen [[basics|here]] some examples of higher-order functions.
 +For instance:
 +<code ocaml>
 +# let sumc x y = x+y;;
 +val sumc : int -> int -> int = <fun>
 +</​code>​
 +
 +The type operator ''​->''​ associates to the right.
 +So, the correct parenthesization of the type ''​int -> int -> int''​ is ''​int -> (int -> int)''​.
 +Therefore, ''​sumc''​ is a function that, when applied to an integer x, evaluates to a function
 +that maps an integer y to the sum x+y.
 +
 +Higher-order functions can also take functions as arguments.
 +For instance, let ''​countzero''​ be a function
 +that computes the number of zeros (in a given range) of a function ​
 +''​f:​ int -> int''​ taken as input.
 +
 +<code ocaml>
 +# let rec countzero f a b = 
 +    if a>b then 0 
 +    else (if f a = 0 then 1 else 0) + (countzero f (a+1) b);;
 +
 +val countzero : (int -> int) -> int -> int -> int = <fun>
 +
 +# countzero (fun x -> x*x - 4) 0 5;;
 +- : int = 1
 +</​code>​
 +
 +The type of ''​countzero''​ can be read as follows: ​
 +when fed with a function with type ''​int -> int''​ (the parameter ''​f''​) ​
 +and two integers (the parameters ''​a''​ and ''​b''​), ​
 +it evaluates to an integer (the number of zeros of ''​f''​ in the range [a,b]).
 +
 +We now write an higher-order function that
 +takes as input a function ''​f:​ int -> int'',​ and evaluates to a function
 +which maps each input ''​y''​ to ''​f(y) + y''​.
 +
 +We can do this in several ways.
 +First, the "​official"​ definition:
 +<code ocaml>
 +# let h = fun f -> fun y -> (f y) + y ;;
 +val h : (int -> int) -> int -> int = <fun>
 +</​code>​
 +
 +As an example, let us apply ''​h''​ to the successor function, and then apply the resulting function to the integer 3:
 +<code ocaml>
 +# h (fun x -> x+1) 3;;
 +- : int = 7
 +</​code>​
 +
 +With the syntactic sugar defined [[basics#​functions|here]],​ we can rewrite ''​h''​ more shortly as follows:
 +<code ocaml>
 +# let h' f = fun y -> (f y) + y ;;
 +val h''​ : (int -> int) -> int -> int = <fun>
 +</​code>​
 +
 +Using the syntactic sugar twice, we obtain:
 +<code ocaml>
 +# let h''​ f y = (f y) + y;;
 +val h''​ : (int -> int) -> int -> int = <fun>
 +</​code>​
 +
 +All the three versions of ''​h''​ are equivalent. ​
 +None is better than the others: choose the one which you prefer.
 +
 +\\
 +
 +===== Polymorphism =====
 +
 +One of the simplest functions one can write is the identity:
 +
 +<code ocaml>
 +# let id = fun x -> x;;
 +val id : 'a -> 'a = <fun>
 +</​code>​
 +
 +Note that the type of ''​id''​ looks quite strange!
 +The type '''​a -> '​a''​ should be read as follows:
 +for all types ''​a'',​ the function ''​id''​ returns a value of type ''​a''​ when applied to a value of type ''​a''​.
 +In other words, the function ''​id''​ is //​polymorphic//:​ it can be applied to argument of many different types
 +(actually, of //any// type). ​  
 +
 +<code ocaml>
 +# id 3;;
 +- : int = 3
 +
 +# id "​pippo";;​
 +- : string = "​pippo"​
 +
 +# id (fun x -> x+1);;
 +- : int -> int = <fun>
 +</​code>​
 +
 +Other simple examples of polymorphic functions are the projection functions on pairs.
 +The function ''​fst''​ selects the first element of a pair, while ''​snd''​ selects the second element.
 +<code ocaml>
 +# let fst (x,y) = x;;
 +# let snd (x,y) = y;;
 +
 +val fst : 'a * 'b -> 'a = <fun>
 +val snd : 'a * 'b -> 'b = <fun>
 +</​code>​
 +
 +[[wp>​Type_polymorphism|Polymorphism]] plays a key role in functional programming languages, ​
 +since it allows a quite general way of defining and composing functions. ​
 +Consider, for instance, a function ''​abs''​ that takes as input a function ''​f''​ and computes its absolute value ''​|f|'':​
 +
 +<code ocaml>
 +# let abs f = fun x -> if f x < 0 then -(f x) else f x;;
 +val abs : ('a -> int) -> 'a -> int = <fun>
 +</​code>​
 +
 +The type of ''​abs''​ says that, for all types ''​a'',​ ''​abs'' ​
 +takes as input a function from ''​a''​ to ''​int''​ , and it returns a function from
 +''​a''​ to ''​int''​.
 +
 +Let us apply ''​abs''​ to the function that maps each x to x.
 +<code ocaml>
 +# let f' = abs (fun x -> x);;
 +val f' : int -> int = <fun>
 +
 +# f' (-3);;
 +- : int = 3
 +</​code>​
 +
 +The function ''​comp''​ takes as input two functions and returns their composition.
 +To compose ''​f''​ with ''​g'',​ the codomain of ''​g''​ must coincide with the domain of ''​f''​.
 +This is what the type of ''​comp''​ says: 
 +the type of ''​g''​ is '''​c -> '​a'',​ while the type of ''​f''​ is '''​a -> '​b''​.
 +Then, the type of the composition f ° g is '''​c -> '​b''​.
 +<code ocaml>
 +# let comp f g = fun x -> f (g x);;
 +val comp : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
 +</​code>​
 +
 +As an example, we exploit ''​comp''​ to give an alternative definition of ''​abs''​.
 +<code ocaml>
 +# let abs = comp (fun x -> if x<0 then -x else x);;
 +val abs : ('a -> int) -> 'a -> int = <fun>
 +</​code>​
 +
 +\\
 +
 +
 +===== Currying and uncurrying =====
 +
 +We have already discussed on [[basics#​curried_vs_uncurried_functions|curried vs. uncurried functions]].
 +We now explicitly define how to transform an uncurried function into curried form (//​currying//​),​
 +and, viceversa, how to transform a curried function into uncurried form (//​uncurrying//​).
 +
 +The functions ''​curry''​ below transforms a function of type '''​a * 'b -> '​c''​
 +into a function of type '''​a -> 'b -> '​c''​.
 +
 +That is, a function taking a pair of arguments (x,y) becomes an higher-order function with argument x, 
 +returning a function with argument y.
 +
 +<code ocaml>
 +# let curry f = fun x y -> f (x,y);;
 +val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
 +</​code>​
 +
 +<code ocaml>
 +# let addpair (x,y) = x+y;;
 +val addpair : int * int -> int = <fun>
 +
 +# let add = curry addpair;;
 +val add : int -> int -> int = <fun>
 +
 +# add 3 5;;
 +- : int = 8
 +</​code>​
 +
 +The function ''​uncurry''​ performs the reverse transformation.
 +It transforms a function of type '''​a -> 'b -> '​c''​
 +into a function of type '''​a * 'b -> '​c''​.
 +<code ocaml>
 +# let uncurry f = fun (x,y) -> f x y;;
 +val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>
 +</​code>​
 +
 +<code ocaml>
 +# let addpair = uncurry (+);;
 +val addpair : int * int -> int = <fun>
 +
 +# addpair (3,5);;
 +- : int = 8
 +</​code>​
 +
 +\\
 +
 +
 +===== Bounded iterators =====
 +
 +Now a more complex (and insightful) example. ​
 +We want to define a function ''​iter''​ that iterates any function ''​f''​ for n times.
 +For instance: ​
 +  * ''​(iter 0 f) x = x''​
 +  * ''​(iter 1 f) x = f x''​
 +  * ''​(iter 2 f) x = f (f x)''​
 +  * ...
 +
 +<code ocaml>
 +# let rec iter n f = fun x -> if n=0 then x else f (iter (n-1) f x);;
 +val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
 +</​code>​
 +
 +Here is an equivalent definition of ''​iter'',​ which avoids making the parameter ''​x''​ explicit.
 +For instance:
 +  * ''​iter 0 f = id''​ (where ''​id''​ is the identity function)
 +  * ''​iter 1 f = f''​
 +  * ''​iter 2 f = f ° f''​ (where ° denotes function composition)
 +  * ...
 +
 +<code ocaml>
 +# let rec iter n f = if n=0 then (fun x -> x) else comp f (iter (n-1) f);;
 +val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
 +</​code>​
 +
 +Let us exploit bounded iteration to define addition and multiplication,​ starting from the Peano axioms. ​
 +The idea is that x + y = succ succ ... succ y, where the successor function ''​succ''​ is iterated x times.
 +
 +<code ocaml>
 +# let succ = fun x -> x+1;;
 +val succ : int -> int = <fun>
 +
 +# let sum = fun x y -> (iter x succ) y;;
 +val sum : int -> int -> int = <fun>
 +
 +# sum 3 5;;
 + - : int = 8
 +</​code>​
 +
 +Multiplication is similar:
 +to compute the product of x by y, we need to iterate ''​sum''​ x times,
 +that is x * y = y + ... + y (x times). ​
 +
 +<code ocaml>
 +# let mul = fun x y -> (iter x  (sum y)) 0;;
 +val mul : int -> int -> int = <fun>
 +
 +# mul 3 5;;
 + - : int = 15
 +</​code>​
 +
 +\\
 +
 +
 +===== Unbounded iterators =====
 +
 +In the previous section we have defined a combinator
 +that allows for bounded iteration:
 +indeed, ''​iter n''​ performs exactly ''​n''​ iterarions.
 +
 +We now introduce a more general combinator, that allows
 +for performing a possibly unbounded number of iterations.
 +The exit condition is given by a boolean predicate ''​p'':​
 +we keep iterating until ''​p''​ becomes false.
 +
 +<code ocaml>
 +# let rec loop p f x = if p x then x else loop p f (f x);;
 +val loop : ('a -> bool) -> ('a -> 'a) -> 'a -> 'a = <fun>
 +</​code>​
 +
 +Let us exploit ''​loop''​ to define a function that computes ​
 +a fixed point (if it exists) of a function ''​f:​ float -> float''​.
 +A fixed point of ''​f''​ is a value ''​x''​ such that ''​f x = x''​.
 +Since we are working with floating point numbers, i
 +t would be unwise to use equality: actually, we just require
 +that ''​f x''​ and ''​x''​ do not differ more than some given epsilon.
 +
 +<code ocaml>
 +# let fixpoint f eps = loop (fun x -> f x -. eps <= x && x <= f x +. eps) f;;
 +val fixpoint : (float -> float) -> float -> float -> float = <fun>
 +
 +# fixpoint (fun x -> cos x) 1e-6 (-1.);;
 +- : float = 0.739084549575212635
 +</​code>​
 +
 +As mentioned above, the ''​loop''​ combinator is more general than ''​iter''​.
 +To show that, we shall now define ''​iter n''​ in terms of ''​loop''​.
 +The exit predicate becomes true when the number of iterations made by the loop equals to ''​n''​.
 +To do that, we massage the iterated function ''​f'' ​
 +in order to make it count the number of iterations.
 +
 +<code ocaml>
 +# let iter n f x = 
 +  fst (loop 
 +      (fun (x,k) -> k=n) 
 +      (fun (x,k) -> (f x,​k+1)) ​
 +      (x,0));;
 +
 +val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
 +</​code>​
 +
 +\\
 +
 +
 +===== Exercises =====
 +
 +[[ex-hof|LIP assignment #3]]
hof.txt · Last modified: 2015/10/08 15:20 (external edit)