05-FP-Higher-Order Functions

Map

let rec map f lst =
	match lst with 
	| [] -> []
	| h::t -> f h :: map f t;;

Function type: ${(}^{\prime }a{\to }^{\prime }b){\to }^{\prime }alst{\to }^{\prime }blst$

This general function is a function of functions. It is on the higher-order.

map can even be partially applied. map twice is a function of type

int list $\to$ int list

Map applied in different ways

(*anonymous function*)
let rec map2 f = fun x -> 
	match  x with 
	| [] -> []
	| h::t -> f h :: map2 f t;;

(*anonymous function with pattern matching*)
let rec map3 f = function 
	| [] -> []
	| h::t -> f h :: map3 f t;;

(*using scopes*)
let rec map4 f = function 
	| [] -> []
	| h::t -> let h' = f h in h' :: map4 f t;;

Head Recursions and Tail Recursion

Recursion are of different types

• head: the recursive call is the firstly performed operator.
• tail: the recursive call is the lastly performed operator.
• Some recursions can be neither head nor tail.

The output must be put on the interface.

• return (recursion on input)with output

with is the last operation.

• return recursion on (input with output)

recursion is the last operation.

Tail Map

The output for tail recursion has to be accumulated. Initially, the accumulated output is empty.

The recursion stops if the input is empty.

let rec map_t_aux f acc = function 
	|	[]->acc
	| h::t -> map_t_aux f (acc@ [f h])t;; 
let rec map_tail f l = map_t_aux f [] l;;

But this implementation is not efficient.

• @ takes O(n) time, while :: only takes O(1) time.
• Then, map is $O(n)$, but map_tail is $O(n^2)$.

let rec rev_map_aux f acc = function 
	| []->acc
	| h::t  -> rev_map_aux f(f h:: acc) t;; 

let rev_map f l = rev_map_aux f [] l;;

To reverse the order of a list, we only need to call rev_map_aux but let f be the identity function.

let id a = a ;;
let map_tail f l = rev_map_aux id [] (rev_map f l);;

• map_tail is $O(n)$ now.
• List.rev is also works.

Filter

• Another famous higher-order function is filter.
  • filter takes a logical test and a list as input, and
  • returns the list of elements who pass the test.

let rec filter p = function 
 | [] -> []
 | h::t ->(if p h then [h] else [])@ filter p t;

Fold

fold combines a list of items as one. For example, summation, concatenation, etc. Different from map and filter , programmers need to define an initial value for fold when the list is empty.

let rec fold f ini  = function 
	| [] -> ini
	| h::t -> f h (fold f ini t);;

Fold Right and Fold Left

Fold Right

let rec fold_right f lst acc =
	match lst with 
	| [] -> acc
	| h::t -> f h (fold_right f t acc);;

Now, fold_right is exactly same as the system library List.fold_right.

fold_right is for the function which is right associative.

Fold Left

In each iteration of fold_left

• the accumulation acc carries the result of folding first n elements from previous iterations;
• the combine function f is applied on acc and n + 1-th element;
• the result of combine is passed to the next iteration as the new acc, together with the tail as the new list.

let rec fold_left f acc = function 
	| [] -> acc
	| h :: t -> fold_left f (f acc h) t;;