The simplest way, but which essentially dodged the question, is to utilize a language with uniqueness types. Where the data structure may only exist in a single place and there can be no aliasing. Then any operation on the data structure occurs and can be done ‘in place’ returning the new unique data structure. This is similar (but not identical) to linear and affine type systems, of which Idris is the only language I know of that actually implements such a type system.
Also, along the same lines, it is certainly possible to craft types in some FP languages which allow for this same logic to be captured, mostly via some monad construct.
This reply is late, so if you don’t see it or care I don’t blame you.
To start, I am aware of Rust and left it out of the above comment purposefully. While Rust does indeed make many ‘functional programming’ idioms available and, some would say, is basically an impure, eager functional language, I don’t tend to view Rust as a language featuring persistent, immutable data structures. I certainly don’t think that is a negative characterization, just how I see things. I find that one of the defining features of the functional programming ‘persistent’ data structure is the structural sharing that is all too frequent in most of the mainline FP languages (Haskell, ML, Clojure, etc.). Rudy’s focus on low level/systems level programming is much more likely to use standard imperative data structures without the sharing and deep pointer chasing style seemingly inherent in FP implementations.
I have had a few spirited web-discussions with people about the claim that Rust has an affine type system. I don’t think that stance is accurate, from a type theoretic stance. I subscribe to the theoretical standpoint that Rust has a standard non-substructural type systems with constraints placed on types that meet a mutability predicate. I think that those constraints are better described as a uniqueness constraint per instance of a type. But the sequent calculus presentations for Rust (especially concerning mutable data) would look very similar and act very similar as well. So really it’s much ado about nothing, just fun to talk about.
Sorry for the wall of text, and rambling about type theory. Stay safe.
Comments
The simplest way, but which essentially dodged the question, is to utilize a language with uniqueness types. Where the data structure may only exist in a single place and there can be no aliasing. Then any operation on the data structure occurs and can be done ‘in place’ returning the new unique data structure. This is similar (but not identical) to linear and affine type systems, of which Idris is the only language I know of that actually implements such a type system.
Also, along the same lines, it is certainly possible to craft types in some FP languages which allow for this same logic to be captured, mostly via some monad construct.
Rust has an affine type system, and https://docs.rs/im/14.3.0/im/ implements this https://docs.rs/im/14.3.0/im/#in-place-mutation
This reply is late, so if you don’t see it or care I don’t blame you.
To start, I am aware of Rust and left it out of the above comment purposefully. While Rust does indeed make many ‘functional programming’ idioms available and, some would say, is basically an impure, eager functional language, I don’t tend to view Rust as a language featuring persistent, immutable data structures. I certainly don’t think that is a negative characterization, just how I see things. I find that one of the defining features of the functional programming ‘persistent’ data structure is the structural sharing that is all too frequent in most of the mainline FP languages (Haskell, ML, Clojure, etc.). Rudy’s focus on low level/systems level programming is much more likely to use standard imperative data structures without the sharing and deep pointer chasing style seemingly inherent in FP implementations.
I have had a few spirited web-discussions with people about the claim that Rust has an affine type system. I don’t think that stance is accurate, from a type theoretic stance. I subscribe to the theoretical standpoint that Rust has a standard non-substructural type systems with constraints placed on types that meet a mutability predicate. I think that those constraints are better described as a uniqueness constraint per instance of a type. But the sequent calculus presentations for Rust (especially concerning mutable data) would look very similar and act very similar as well. So really it’s much ado about nothing, just fun to talk about.
Sorry for the wall of text, and rambling about type theory. Stay safe.