// Code from Hansen and Rischel: Functional Programming using F# 16/12 2012 // Chapter 9: Efficiency // From Section 9.2: Memory management let rec bigList n = if n=0 then [] else 1::bigList(n-1);; let rec bigListA n xs = if n=0 then xs else bigListA (n-1) (1::xs);; // From Section 9.3: Two problems let rec fact = function | 0 -> 1 | n -> n * fact(n-1);; let rec naiveRev = function | [] -> [] | x::xs -> naiveRev xs @ [x];; // From Section 9.4: Solutions using accumulating parameters let rec factA = function | (0,m) -> m | (n,m) -> factA(n-1,n*m);; let xs16 = List.init 1000000 (fun i -> 16);; #time;; for i in xs16 do let _ = fact i in ();; for i in xs16 do let _ = factA(i,1) in ();; for i in xs16 do let _ = () in ();; let rec revA = function | ([], ys) -> ys | (x::xs, ys) -> revA(xs, x::ys);; let xs20000 = [1 .. 20000];; naiveRev xs20000;; revA(xs20000,[]);; // From Section 9.5: Iterative function declarations let rec fold f e = function | x::xs -> fold f (f e x) xs | [] -> e;; let revA1(xs,ys) = fold (fun e x -> x::e) ys xs;; let factW n = let ni = ref n let r = ref 1 while !ni>0 do r := !r * !ni ; ni := !ni-1 !r;; for i in 1 .. 1000000 do let _ = factA(16,1) in ();; for i in 1 .. 1000000 do let _ = factW 16 in ();; // From Section 9.6: Tail recursion obtained using continuations let rec bigListC n c = if n=0 then c [] else bigListC (n-1) (fun res -> c(1::res));; bigListC 3 id;; // SKAL RETTES PÅ SIDE 213 bigListA 12000000 [];; bigListC 12000000 id;; bigListC 16000000 id;; bigListC 17000000 id;; type BinTree<'a> = | Leaf | Node of BinTree<'a> * 'a * BinTree<'a>;; let rec count = function | Leaf -> 0 | Node(tl,n,tr) -> count tl + count tr + 1;; let rec countC t c = match t with | Leaf -> c 0 | Node(tl,n,tr) -> countC tl (fun vl -> countC tr (fun vr -> c(vl+vr+1)));; countC (Node(Node(Leaf,1,Leaf),2,Node(Leaf,3,Leaf))) id;; let rec genTree xs = match xs with | [| |] -> Leaf | [| x |] -> Node(Leaf,x,Leaf) | _ -> let m = xs.Length / 2 let xsl = xs.[0..m-1] let xm = xs.[m] let xsr = xs.[m+1 ..] Node(genTree xsl, xm, genTree xsr);; let t n = genTree [| 1..n |];; let t20000000 = t 20000000;; count t20000000;; countC t20000000 id;;