Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Florian Hars <florian@hars.de>]

Brian Hurt wrote:
> Consider the following Ocaml code:
> 
>     let dup_list lst =
>         let rec reverse_list l accum =
>             match l with
>                 [] -> accum
>                 | head :: tail -> reverse_list tail (head :: accum)
>         in
>             reverse_list (reverse_list lst)

This should probably be reverse_list (reverse_list lst []) []

>     ;;
[...]
> So why not reuse the cells from l to form the accum?  

To optimize reverse_list in the way you propose, the compiler would have to be 
smart enough to see that reverse_list is only ever called twice, so as to 
return (a list that is equivalent to) the original list. (If reverse_list were 
called in any other context, the optimazition would be illegal, since it 
destroys the original list). But then the compiler would know enough to perform 
the correct optimization of your code to

let dup_list lst = lst

and then eliminate all calls to dup_list entirely. But since the same effect 
can be had by not introducing the function in the first place, it would be a 
royal waste of ressources to make the compiler detect this case.

> Yes, I know this violates the immutability of l.  But it seems to me that, 
> with the exception of garbage creation rates, the two are identical.

Yes, of course. Your dup_list is one of the most expensive no-ops you can 
perform on a list.

The point is: unlike in languages of the Fortran heritage (C, Java...), 
variables in functional languges designate values and are not names for 
physical storage locations. To add to the confusion, ocaml blurs this by 
supporting both physical (==, !=) and value (=, <>) comparisions:

$ ledit ocaml
         Objective Caml version 3.06

# let dup_list lst =
   let rec reverse_list l accum =
     match l with
           [] -> accum
       | head :: tail -> reverse_list tail (head :: accum)
     in
     reverse_list (reverse_list lst []) []
     ;;
val dup_list : 'a list -> 'a list = <fun>
# let l = [1; 2; 3];;
val l : int list = [1; 2; 3]
# let l' = dup_list l;;
val l' : int list = [1; 2; 3]
# l = l';;
- : bool = true
# l == l';;
- : bool = false

This last inequality is the *only* difference between using

let l' = dup_list l

and using

let l' = l

and it would disappear if your optimazation were performed (since then dup_list 
would just return its argument restored to its original state). So there is no 
reason not to use the second, simpler and more efficient version.

Even with your dup_list, the contents of the two list are physically the same:

# let m = [ref 1; ref 2; ref 3];;
val m : int ref list = [{contents = 1}; {contents = 2}; {contents = 3}]
# let m' = dup_list m;;
val m' : int ref list = [{contents = 1}; {contents = 2}; {contents = 3}]
# m == m';;
- : bool = false
# List.hd m == List.hd m';;
- : bool = true
# List.hd m := 42;;
- : unit = ()
# m';;
- : int ref list = [{contents = 42}; {contents = 2}; {contents = 3}]

Yours, Florian.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners