I am not sure this subject has already been discussed, but I am wondering about immutable types in FreePascal. Basically the idea is that except locally, variables are constant. For a list, it means that a function that change an item in fact would return a copy. To avoid using much memory, a tree structure is used, and only the branches that change are reallocated to make the copy, and reference counters are used to indicate that a branch is used in multiple trees.
I found this hashmap there:
https://github.com/benibela/hamtThat looks promising. Though I am looking for something simple like a list. Also it seems to me that allocating takes time, and that it would be more efficient to have pre-allocating memory and to use "sectors" for each leaf or branch. For example I was thinking of something like blocks of either 32 pointers or otherwise raw data of the corresponding size (32x8 = 256 bytes on a 64 bit processor). So for example a list of 200 kilobytes could be stored in 200x1024/256 = 800 blocks of raw data.
Of course ideally, the tree depth would be limited. There are more technical questions like how to store the number of elements, what if an element is bigger than the block size, etc. Also is there a way to have reference counting like strings, without having to call some function when a variable gets out of scope? It can be done with interface type but that would be an class instance, and I am trying to avoid allocating on the heap. I would rather have a record with some magic.
I find this topic interesting because it could help solve some complex errors that we can get when unexpected changes happen to an object. And of course avoiding to duplicate data when passing it to a function or an object or to have to handle ownership to know who is supposed to free the memory.