(* Examples of fold and tail recursion *) open Core.Std let make_list n = List.init n ~f:(fun x -> x) let make_random_list n = List.init n ~f:(fun x -> Random.int 100) let rec sum (l : int list) : int = match l with [] -> 0 | x :: xs -> x + (sum xs) (* # make_list 10;; # sum (make_list 10);; # sum (make_list 10_000_000);; *) let rec sum' (acc : int) (l : int list) : int = match l with [] -> acc | x :: xs -> sum' (acc + x) xs (* # sum' 0 (make_list 10);; # sum' 0 (make_list 10_000_000);; *) let rec concat (l : string list) : string = match l with [] -> "" | x :: xs -> x ^ (concat xs) let rec concat' (acc : string) (l : string list) : string = match l with [] -> acc | x :: xs -> concat' (acc ^ x) xs let rec fold_left (f : 'a -> 'b ->'a) (acc : 'a) (l : 'b list): 'a = match l with [] -> acc | x :: xs -> fold_left f (f acc x) xs let rec fold_right (f : 'a -> 'b -> 'b) (l : 'a list) (acc : 'b) : 'b = match l with [] -> acc | x :: xs -> f x (fold_right f xs acc) (* Common functions using fold *) let sum = List.fold_left ~init:0 ~f:(+) let concat = List.fold_left ~f:(^) ~init:"" let length = List.fold_left ~f:(fun a _ -> a + 1) ~init:0 let rev = List.fold_left ~f:(fun a x -> x :: a) ~init:[] let map f = List.fold_right ~f:(fun x a -> (f x) :: a) ~init:[] let filter f = List.fold_right ~f:(fun x a -> if f x then x :: a else a) ~init:[] (* Insertion sort using fold *) let rec insert l e = match l with | [] -> [e] | h :: t -> if e > h then h :: insert t e else e :: l let insertion_sort = List.fold_left ~f:insert ~init:[] (* # let l = make_random_list 100;; # insertion_sort l;; *)