www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Clojure vs. D in creating immutable lists that are almost the same.

reply Brother Bill <foo bar.com> writes:
Clojure supports immutable lists that allow adding and removing 
elements, and yet still have excellent performance.

For D language, what are the recommended techniques to use 
functional programming, without massive copying of data and 
garbage collection, so that it remains immutable.

That is, how to create one-off changes to an immutable data 
structure, while keeping the original immutable, as well as the 
one-off change, and maintain good performance.

Thank you
Feb 27 2016
next sibling parent reply w0rp <devw0rp gmail.com> writes:
On Saturday, 27 February 2016 at 22:31:28 UTC, Brother Bill wrote:
 Clojure supports immutable lists that allow adding and removing 
 elements, and yet still have excellent performance.

 For D language, what are the recommended techniques to use 
 functional programming, without massive copying of data and 
 garbage collection, so that it remains immutable.

 That is, how to create one-off changes to an immutable data 
 structure, while keeping the original immutable, as well as the 
 one-off change, and maintain good performance.

 Thank you
I think this is a property of linked lists which could possibly be advantageous. However, I would keep in mind that memory layout is very important when it comes to execution speed, and that slices of memory are unbeatable in that regard. That's worth stating first. I think for linked lists, you can always create a new node which points to another node. So you start with element a as immutable, then you take a head element b and point to a, so you get b : a, then c : b : a, etc. So you can create larger and large immutable linked lists because you never actually change a list, you just produce a new list with an element pointing the head of a previous list. I'm not sure if Phobos has something suitable for this, but you could always implement your own singly linked list in such a manner pretty easily. I would be tempted just to use slices instead, though. Linked lists are rarely better.
Feb 27 2016
parent John Colvin <john.loughran.colvin gmail.com> writes:
On Saturday, 27 February 2016 at 23:19:51 UTC, w0rp wrote:
 On Saturday, 27 February 2016 at 22:31:28 UTC, Brother Bill 
 wrote:
 Clojure supports immutable lists that allow adding and 
 removing elements, and yet still have excellent performance.

 For D language, what are the recommended techniques to use 
 functional programming, without massive copying of data and 
 garbage collection, so that it remains immutable.

 That is, how to create one-off changes to an immutable data 
 structure, while keeping the original immutable, as well as 
 the one-off change, and maintain good performance.

 Thank you
I think this is a property of linked lists which could possibly be advantageous. However, I would keep in mind that memory layout is very important when it comes to execution speed, and that slices of memory are unbeatable in that regard. That's worth stating first. I think for linked lists, you can always create a new node which points to another node. So you start with element a as immutable, then you take a head element b and point to a, so you get b : a, then c : b : a, etc. So you can create larger and large immutable linked lists because you never actually change a list, you just produce a new list with an element pointing the head of a previous list. I'm not sure if Phobos has something suitable for this, but you could always implement your own singly linked list in such a manner pretty easily. I would be tempted just to use slices instead, though. Linked lists are rarely better.
Often people use a lot more advanced structures than linked lists for immutable data structures. http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala
Feb 28 2016
prev sibling next sibling parent Abdulhaq <alynch4047 gmail.com> writes:
On Saturday, 27 February 2016 at 22:31:28 UTC, Brother Bill wrote:

 That is, how to create one-off changes to an immutable data 
 structure, while keeping the original immutable, as well as the 
 one-off change, and maintain good performance.
Clojure uses bit-partitioned hash tries. I recommend this video (Clojure Concurrency) https://www.youtube.com/watch?v=dGVqrGmwOAw slides here: https://github.com/dimhold/clojure-concurrency-rich-hickey/blob/master/ClojureConcurrency alk.pdf?raw=true´╗┐ (slide 21 about bit-partitioned hash tries)
Feb 28 2016
prev sibling next sibling parent Chris Wright <dhasenan gmail.com> writes:
On Sat, 27 Feb 2016 22:31:28 +0000, Brother Bill wrote:

 Clojure supports immutable lists that allow adding and removing
 elements, and yet still have excellent performance.
 
 For D language, what are the recommended techniques to use functional
 programming, without massive copying of data and garbage collection, so
 that it remains immutable.
 
 That is, how to create one-off changes to an immutable data structure,
 while keeping the original immutable, as well as the one-off change, and
 maintain good performance.
 
 Thank you
It's pretty straightforward for arrays: immutable(T[]) array = ...; auto inserted = chain(array[0..5], [new T], array[5..$]); auto dropped = chain(array[0..5], array[6..$]); auto appended = chain(array, [new T, new T]); After K mutations, you have a tree of chain!(...).Result structs; this tree is of height K and contains O(2**K) Result structs (if you're removing or inserting items in the middle of the array). That's not too bad if you're rarely mutating the array. Maybe choose a period; after that many mutations, you copy the data into a new collection. But there's a bigger problem. In the above example, there are four variables, and each has a different type. That's fine if you're declaring new variables. If you are dealing with aggregate fields, it's trouble.
Feb 28 2016
prev sibling parent QAston <qaston gmail.com> writes:
On Saturday, 27 February 2016 at 22:31:28 UTC, Brother Bill wrote:
 Clojure supports immutable lists that allow adding and removing 
 elements, and yet still have excellent performance.

 For D language, what are the recommended techniques to use 
 functional programming, without massive copying of data and 
 garbage collection, so that it remains immutable.

 That is, how to create one-off changes to an immutable data 
 structure, while keeping the original immutable, as well as the 
 one-off change, and maintain good performance.

 Thank you
As a user of Clojure i can tell that "excellent" is an overstatement. Still persistent data structures are much better than naive copy (unless you really, REALLY need all data in cache) and copy on write (unless you only very rarely modify an object). That said, I've seen nobody programming with all-immutable objects in D. People mostly use immutable objects only for objects never modified, and use const as an immutable view of a modifiable object. No clojure-style applying method calls with reduce. With some metaprogramming you could probably write update-in function which would work with nested class objects. With that and having your classes return new object instead of modifying existing one you could have a somewhat clojurish experience. For cool stuff like records clojure uses persistent maps, which would be much less convenient to use because of static typing. I know no implementation of persistent data structures (hell, phobos lacks even some regular data structures). I'm implementing transducers for D though, which could be useful if someone implemented the datastructures.
Feb 28 2016