21 A Study Tip

Challenge! Could you re-develop the bodies of map, fold_right, fold_left, and filter from types? Here are the types:

List.map;;
List.fold_right;;
List.fold_left;;
List.filter;;

- : ('a -> 'b) -> 'a list -> 'b list = <fun>

- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

- : ('a -> bool) -> 'a list -> 'a list = <fun>

---

Map

val map : ('a -> 'b) -> 'a list -> 'b list

List.map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f. Not tail-recursive.

let rec map f = function
	| [] -> []
	| h :: t -> f h :: map f t;;

val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

map string_of_int [1; 2; 3];;
List.map string_of_int [1; 2; 3];;

- : string list = ["1"; "2"; "3"]

- : string list = ["1"; "2"; "3"]

---

Fold Right

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...)). Not tail-recursive.

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

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

fold_right ( - ) [1; 2; 3] 0;;
List.fold_right ( - ) [1; 2; 3] 0;;

- : int = 2

- : int = 2

---

Fold Left

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn.

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

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

fold_left ( - ) 0 [1; 2; 3];;
List.fold_left ( - ) 0 [1; 2; 3];;

- : int = -6

- : int = -6

---

Filter

val filter : ('a -> bool) -> 'a list -> 'a list

filter p l returns all the elements of the list l that satisfy the predicate p. The order of the elements in the input list is preserved.

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

val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

filter (fun x -> x mod 2 == 0) [1; 2; 3; 4; 5];;
List.filter (fun x -> x mod 2 == 0) [1; 2; 3; 4; 5];;

- : int list = [2; 4]

- : int list = [2; 4]

---

🎉 yay