// 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;;