Higher-Order Functions

From Textbook: Higher Order Programming

Introduction¶

• higher-order: functions as values, you can pass functions as arguments into other functions, functions at the same level as other variables
• lower-order: languages like C, functions as something higher than other variables

Pipeline is a higher-order function.

let pipeline x f = f x
let (|>) = pipeline
let x = 5 |> double  (* 10 *)

Map (Transforms Elements)¶

it maps each element of the list through a function

(* [map f [x1; x2; ...; xn]] is [f x1; f x2; ...; f xn] *)
let rec map f = function
  | [] -> []
  | h::t -> (f h)::(map f t)

let add1 = map (fun x-> x+1);
let add1' = map ((+)1);

let concat3110 = map (fun x -> x^"3110")

Filter (Eliminates Elements)¶

List.filter <predicate> <list>it picks all elements which meet predicate p to form a new list.

(* [filter p l] is the list of elements of [l] that satisfy the predicate [p]. 
 * The order of the elements in the input list is preserved. *)
let rec filter f = function
  | [] -> []
  | h::t -> if f h then h::(filter f t) else filter f t

Fold (Combines Elements)¶

Fold Right¶

Can we abstract the following two functions as a single function?

let rec sum = function
  | [] -> 0
  | h::t -> h + (sum t)

let rec concat = function
  | [] -> ""
  | h::t -> h ^ (concat t)

First, we abstract the initial value

let rec sum' init = function
  | [] -> init
  | h::t -> h + sum' init t

let sum = sum' 0

let rec concat' init = function
  | [] -> init
  | h::t -> h ^ concat' init t

let concat = concat' ""

We find out the only thing these two functions have in difference is the operator. So the next step, we factor out the operator.

let rec combine init op = function
| [] -> init
| h::t -> op h (combine init op t);;

The intuition for why this function is called fold_right is that the way it works is to “fold in” elements of the list from the right to the left, combining each new element using the operator. For example, fold_right (+) [a;b;c] 0 results in evaluation of the expression a+(b+(c+0)). The parentheses associate from the right-most subexpression to the left.

One way to think of fold_right would be that the [] value in the list gets replaced by init, and each :: constructor gets replaced by op. For example, [a;b;c] is just syntactic sugar for a::(b::(c::[])). So if we replace [] with 0 and :: with (+), we get a+(b+(c+0)).

Fold Left¶

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

The idea is that fold_left (+) 0 [a;b;c] results in evaluation of ((0+a)+b)+c. The parentheses associate from the left-most subexpression to the right. So fold_left is “folding in” elements of the list from the left to the right, combining each new element using the operator.

Fold Left vs. Fold Right¶

Why is there a difference of the order the operand takes in arguments (op acc h; op: 'a -> 'b -> 'a as in fold_left; op h (combine init op t); op: 'a -> 'b -> 'b as in fold_right)? And why is there a difference of the order these two functions take in argument (fold_left op acc lst; fold_right op lst init)?

fold_left f init [v1; v2;...; vn] is f (... (f (f init v1) v2)...) vn whereas fold_right f [v1; v2;...; vn] init is f v1 (f v2 (...(f vn init)...)) (-- Nate Foster)

• order of evaluation:

  • fold_left evaluates from left to right
  • fold_right evaluates from right to left

• tail-recursive:

  because of the way these two functions evaluate

  • fold_left is tail-recursive. We can add that value to acc, the group of elements completed evaluation, after evaluating the current element.
  • fold_right is not recursive. Because it cannot evaluate the nth element before evaluating the (n+1)th element. And the evaluation of nth element depends on (n+1)th element. This pattern violates the definition of tail-recursive

  Then is there a tail-recursive version of fold_right? You can first reverse the list and then fold_left.

Fold Application¶

let length l = List.fold_left (fun a _ -> a+1) 0 l
let rev l = List.fold_left (fun a x -> x::a) [] l
let map f l = List.fold_right (fun x a -> (f x)::a) l []
let filter f l = List.fold_right (fun x a -> if f x then x::a else a) l []

(*test whether a list is full of true*)
let lst_and_fold =
    List.fold_left (fun acc elt -> acc && elt) true

Generalized Fold¶

let rec foldtree init op = function
  | Leaf -> init
  | Node (v,l,r) -> op v (foldtree init op l) (foldtree init op r)
  
let size t = foldtree 0 (fun _ l r -> 1 + l + r) t
let depth t = foldtree 0 (fun _ l r -> 1 + max l r) t
let preorder t = foldtree [] (fun x l r -> [x] @ l @ r) t