Filter
Top Products
40 CHAPTER 4. EFFECTIVE CAML
#let rev =
let rec reverse acc =
fun [] -> acc
| (h::t) -> reverse (h::acc) t in
reverse [];;
Moreover, the recursive core reverse is tail recursive, so we also save stack
space, and win twice over.
For another typical situation where we can avoid appending by judicious use of
accumulators, consider the problem of returning the fringe of a binary tree, i.e. a
list of the leaves in left-to-right order. If we define the type of binary trees as:
#type btree = Leaf of string
| Branch of btree * btree;;
then a simple coding is the following
#let rec fringe =
fun (Leaf s) -> [s]
| (Branch(l,r)) -> append (fringe l) (fringe r);;
However the following more refined version performs fewer conses:
#let fringe =
let rec fr t acc =
match t with
(Leaf s) -> s::acc
| (Branch(l,r)) -> fr l (fr r acc) in
fun t -> fr t [];;
Note that we have written the accumulator as the second argument, so that the
recursive call has a more natural left-to-right reading. Here is a simple example of
how either version of fringe may be used:
#fringe (Branch(Branch(Leaf "a",Leaf "b"),
Branch(Leaf "c",Leaf "d")));;
it : string list = ["a"; "b"; "c"; "d"]
The first version creates 6 cons cells, the second only 4. On larger trees the
effect can be more dramatic. Another situation where gratuitous consing can crop
up is in pattern matching. For example, consider the code fragment:
fun [] -> []
| (h::t) -> if h < 0 then t else h::t;;
The ‘else’ arm creates a cons cell even though what it constructs was in fact
the argument to the function. That is, it is taking the argument apart and then
rebuilding it. One simple way of avoiding this is to recode the function as:
fun l ->
match l with
[] -> []
| (h::t) -> if h < 0 then t else l;;
However CAML offers a more flexible alternative: using the as keyword, a name
may be identified with certain components of the pattern, so that it never needs to
be rebuilt. For example:
fun [] -> []
| (h::t as l) -> if h < 0 then t else l;;