[Haskell-cafe] efficient operations on immutable structures

[Bardur Arantsson]

On 07/14/2016 08:07 AM, Christopher Howard wrote:
> Hi again all. From some online research, I understand that operations on
> complex immutable structures (for example, a "setter" function a ->
> (Int, Int) -> Matrix -> Matrix which alters one element in the Matrix)
> is not necessarily inefficient in Haskell, because the (compiler?
> runtime?) has some means of sharing unchanged values between the input
> and output structure. What I am not clear on, however, is how this
> works, and how you ensure that this happens. Could someone perhaps
> elaborate, or point me to a really good read on the subject?
> 

https://en.wikipedia.org/wiki/Persistent_data_structure

See in particular the section "Trees". (It basically works the same  for
records; just imagine that a record is a 2-level tree, where each
field/label in the record is an edge from the "field label" to the
"field value". Multiple levels of records work essentially work the same
as multi-level trees do.)