Higher-Order Functions

CS3110

 2020/02/06 

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.

1
2
3

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?
1
2
3
4
5
6
7
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
1
2
3
4
5
6
7
8
9
10
11
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.

1
2
3

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

1
2
3

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

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2020-02-06-Higher-Order-Functions/

Publish date：February 6th 2020, 12:00:00 am

Update date：June 9th 2022, 3:27:40 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

Next Post

Modules
Previous Post

Advanced Data Types

CATALOG

1. Introduction
2. Map (Transforms Elements)
3. Filter (Eliminates Elements)
4. Fold (Combines Elements)