digitalmars.D - Clojure vs. D in creating immutable lists that are almost the same.
- Brother Bill (9/9) Feb 27 2016 Clojure supports immutable lists that allow adding and removing
- w0rp (17/26) Feb 27 2016 I think this is a property of linked lists which could possibly
- John Colvin (4/34) Feb 28 2016 Often people use a lot more advanced structures than linked lists
- Abdulhaq (6/9) Feb 28 2016 Clojure uses bit-partitioned hash tries.
- Chris Wright (15/27) Feb 28 2016 It's pretty straightforward for arrays:
- QAston (21/30) Feb 28 2016 As a user of Clojure i can tell that "excellent" is an
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
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 youI 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
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:Often people use a lot more advanced structures than linked lists for immutable data structures. http://www.infoq.com/presentations/Functional-Data-Structures-in-ScalaClojure 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 youI 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 28 2016
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
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 youIt'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
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 youAs 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