hof

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

— |
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)