It's worth mentioning that when replacing a single element from a complex
immutable datastructure, it's not usually necessary to copy *all* of the
rest of the data -- the new data can reuse parts it has in common with the
old. For example, if you had a set represented as a balanced binary tree,
you will be able to represent that set with one element added -- alongside
the original set, even -- with no more than log-size-of-set copying /
additional space.

On 18 March 2015 at 06:10, Gabriel Scherer <gabriel.scherer@gmail.com>
wrote:

> I think the effect you may be thinking of is to notice that the immutable
> structure for which a field update is performed is uniquely owned /
> linearly used (the old version before-update is never used again), and to
> perform the mutation in place in this case. OCaml does not perform this
> optimization. It's not immediate that this could be done at all, because
> mutation has a tricky interaction with the GC invariants.
>
> On Wed, Mar 18, 2015 at 4:16 AM, Kenneth Adam Miller <
> kennethadammiller@gmail.com> wrote:
>
>> So, OCaml uses a lot of immutable data structures by default, and there's
>> a way in OCaml to express how to replace everything else in a type with the
>> same edition, with the exception of a single variable being updated.
>>
>>
>> But does that mean that the compiler is sufficiently capable to conclude
>> side effects that are more efficient rather than just the nieve
>> explanation, which is a *copy* of the entire data structure with only the
>> specified changed variable updated? Can OCaml conclude that it can update
>> only one variable for efficiency, and know that the rest of the data
>> structure is safe?
>>
>> For example, in tail recursion, it's provably equivalent to produce code
>> that doesn't blow the stack and is faster, and that's exactly what the
>> compiler does. So are side effects a "conclusion"?
>>
>
>