182 lines
2.9 KiB
OCaml
182 lines
2.9 KiB
OCaml
(* Some functions used in S4.3 Improving Performance
|
|
|
|
Some of this material comes from section 9.4 of Chris Reade's book
|
|
``Elements of Functional Programming''. This is in the `Resources`
|
|
directory of the public class repository.
|
|
|
|
Some were written by Charlie Harper.
|
|
|
|
*)
|
|
|
|
|
|
let rec listof n =
|
|
match n with
|
|
| 0 -> []
|
|
| _ -> n :: listof (n-1)
|
|
|
|
let rec append l1 l2 =
|
|
match l1 with
|
|
| [] -> l2
|
|
| x::xs -> x :: (append xs l2)
|
|
|
|
|
|
|
|
(* Problem 1: what is wrong with this function? *)
|
|
let rec rev lst =
|
|
match lst with
|
|
| [] -> []
|
|
| x::xs -> append (rev xs) [x]
|
|
|
|
|
|
|
|
|
|
(* Problem 2: how can these be improved? *)
|
|
let rec length lst = match lst with
|
|
| [] -> 0
|
|
| _::xs -> 1 + length xs
|
|
|
|
let rec sumlist lst = match lst with
|
|
| [] -> 0
|
|
| x::xs -> x + sumlist xs
|
|
|
|
|
|
(*- stacking up the additions
|
|
|
|
Evaluation - if delay additions a bit
|
|
sumlist 1::2::3::[]
|
|
1 + (sumlist 2::3::[])
|
|
1 + (2 + (sumlist 3::[])
|
|
1 + (2 + (3 + sumlist [])
|
|
1 + (2 + (3 + 0))
|
|
|
|
|
|
*)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(* Some solutions
|
|
--------------
|
|
*)
|
|
|
|
(* Use an accumulating parameter to convert reverse from
|
|
quadradic to linear time. *)
|
|
let rev_a lst =
|
|
let rec revaccum lst accum =
|
|
match lst with
|
|
| [] -> accum
|
|
| x::xs -> revaccum xs (x::accum)
|
|
in
|
|
revaccum lst []
|
|
|
|
(* Does the above function remind us of imperative programming?
|
|
|
|
accum = [] ;
|
|
while lst <> [] do
|
|
x::xs = lst
|
|
|
|
lst = xs
|
|
accum = x::accum
|
|
|
|
*)
|
|
|
|
|
|
let length_tr lst =
|
|
let rec ltr lst accum =
|
|
match lst with
|
|
| [] -> accum
|
|
| x::xs -> ltr xs (accum + 1)
|
|
in
|
|
ltr lst 0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(* We can also avoid stacking up the additions by using
|
|
an accumulating parameter. *)
|
|
let sumlist_a lst =
|
|
let rec accsum lst n =
|
|
match lst with
|
|
| [] -> n
|
|
| x::xs -> accsum xs (n+x)
|
|
in
|
|
accsum lst 0
|
|
|
|
|
|
(*
|
|
We delayed the additions - so not really call by value
|
|
sumlist_a [1;2;3]
|
|
accsum [1;2;3] 0
|
|
accsum [2;3] (0+1)
|
|
accsum [3] ((0+1)+2)
|
|
accsum [] (((0+1)+2)+3)
|
|
(((0+1)+2)+3)
|
|
|
|
|
|
|
|
*)
|
|
|
|
|
|
|
|
|
|
(* Exercise: what is the tail recurive version of length? *)
|
|
|
|
|
|
|
|
(* Fibonacci numbers *)
|
|
let rec fib n = match n with
|
|
| 0 -> 0
|
|
| 1 -> 1
|
|
| n -> fib (n-1) + fib (n-2)
|
|
(* What is the tail recursive version of the fib function
|
|
that uses accumulators to avoid all the recomputation?
|
|
*)
|
|
|
|
let fib_tr n =
|
|
let rec fib_acc a b n = match n with
|
|
| 0 -> a
|
|
| n -> fib_acc b (a+b) (n-1)
|
|
in
|
|
fib_acc 0 1 n
|
|
|
|
|
|
(* Another exercise: how does this relate to the imperative
|
|
version? *)
|
|
|
|
|
|
(* Let's recall sumlist and sumlist_tr.
|
|
|
|
Haven't we seen this before? *)
|
|
|
|
|
|
let rec foldl f v l =
|
|
match l with
|
|
| [] -> v
|
|
| x::xs -> foldl f (f v x) xs
|
|
|
|
let sum_f xs = foldl (+) 0 xs
|
|
|
|
(*-
|
|
foldl (+) 0 (1::2::3::[])
|
|
foldl (+) (0+1) (2::3::[])
|
|
foldl (+) 1 (2::3::[])
|
|
foldl (+) (1+2) (3::[])
|
|
foldl (+) 3 (3::[])
|
|
foldl (+) (3+3) []
|
|
foldl (+) 6 []
|
|
6
|
|
|
|
Or without evaluating + so early
|
|
foldl (+) 0 (1::2::3::[])
|
|
foldl (+) (0+1) (2::3::[])
|
|
foldl (+) ((0+1)+2) (3::[])
|
|
foldl (+) (((0+1)+2)+3) []
|
|
(((0+1)+2)+3)
|
|
6
|
|
*)
|
|
|
|
|