Re: Ant: Re: Ant: Re: Ant: Re: [Caml-list] Avoiding shared data

[Jon Harrop <jon@ffconsultancy.com>]

On Monday 03 October 2005 21:03, Martin Chabr wrote:
> what I am especially concerned about is the stack
> overflow for non-tail-recursive programs. Speed is of
> less importance.

Yes. Many useful algorithms are non-tail recursive and do not cause stack 
overflows, e.g. those that recurse O(log n) times.

> By the way, we are diverting from the subject of this
> thread and from the main cause of my concern:
>
> Avoiding shared data. Why is it done that way? Who
> wants to have an array or list of identical records or
> sub-arrays or other sub-structures which are all
> updated at the same time in the same way? In other 
> words, who wants to have an array or a list of
> pointers which are pointing to the same thing?

If you mean this:

# let a = Array.make 3 (ref 0) in (a.(0) := 3; a);;
- : int ref array = [|{contents = 3}; {contents = 3}; {contents = 3}|]

I don't want arrays of elements referencing the same value. So I don't create 
them.

> Does it ever happen in OCaml if programming is done in
> a purely functional way?

If you mean "is referential transparency useful?" then the answer is 
definitely yes. I use data structures that share data all the time but not in 
the form of an array or list of the same repeated value.

For example, computing set unions, differences and intersections using the Set 
module reuses branches of old tree when possible. This reduces the asymptotic 
algorithmic complexity of these operations so they can run asymptotically 
faster than imperative implementations.

> Does it happen in Haskell? 

You'll get a suboptimal answer to such questions on this list.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists