3 ms·

> Immediately, I discovered that tree structures are more complicated in languages like Clojure that have immutable state. This is because changing a node requi

> Immediately, I discovered that tree structures are more complicated in languages like Clojure that have immutable state. This is because changing a node requires rebuilding large parts of the tree. This must have implications for implementing a Merkle tree as an immutable data structure. Anyone know how a bitcoin client in clojure might deal with this?

Volundr 12y ago
You'd use mutable state, either in the form of java collections, or atoms and family. Even Haskell, where the State monad itself is actually immutable, provides an escape hatch into mutable state for when it's really, truly required. Just if you do use it when it's not, great shame shall be visited on you and your kin. By which I mean someone in #haskell will very politely point out how you could have done it purely.
- kylebrown 12y ago
  Right, using a mutable structure is the easy way. But is there a way that would maintain the advantages of immutability? (eg memory-efficient and easy undo)
  - taeric 12y ago
    Are those truly the advantages of immutability? Easy undo can be achieved just as easily by reversing operations, in many cases. No need to keep two copies of a potentially large structure when you could just keep the diff and reverse apply it. Oddly, I think typically you would do both. Keep a few large snapshots with small diffs between stages. That is digressing, though. As for memory-efficiency... not sure how keeping many potentially large copies is more efficient than just modifying a single copy. Now, I can agree that in many cases it is nice that it prevents you from worrying about race conditions across threads. Though, I'm also not convinced that immutable things are any better than traditional locking strategies. Is that race truly won?
    - dbaupp 12y ago
      One doesn't need to keep large copies, since immutability allows common substructures to be shared. (That said, it still seems rather unlikely that an immutable implementation will use less memory.)
      - Rapzid 12y ago
        That's not a property of immutability. That's a property of certain specialized data structures, see "Purely Functional Data Structures" for a start, implemented in clojure.
        chowells 12y ago
        Well, it's a property of basically everything except arrays. So it's more than just "certain specialized data structures".
        taeric 12y ago
        To be fair, many folks learn immutable data structures with the so called "persistent" data structures. Which are cool, to be sure. They are far from new, however. So, I'll be a little surprised if it turns out they are a panacea.
surrealize 12y ago
At first blush it seems fine to me; updating a purely-functional tree requires work that's O(depth of tree), and updating a Merkle tree also requires work that's O(depth of tree). I think that means that using a purely-functional structure to implement a Merkle tree requires at most a constant factor of extra time/space over using a mutable tree.

Volundr 12y ago

You'd use mutable state, either in the form of java collections, or atoms and family. Even Haskell, where the State monad itself is actually immutable, provides an escape hatch into mutable state for when it's really, truly required. Just if you do use it when it's not, great shame shall be visited on you and your kin. By which I mean someone in #haskell will very politely point out how you could have done it purely.

kylebrown 12y ago
Right, using a mutable structure is the easy way. But is there a way that would maintain the advantages of immutability? (eg memory-efficient and easy undo)
- taeric 12y ago
  Are those truly the advantages of immutability? Easy undo can be achieved just as easily by reversing operations, in many cases. No need to keep two copies of a potentially large structure when you could just keep the diff and reverse apply it. Oddly, I think typically you would do both. Keep a few large snapshots with small diffs between stages. That is digressing, though. As for memory-efficiency... not sure how keeping many potentially large copies is more efficient than just modifying a single copy. Now, I can agree that in many cases it is nice that it prevents you from worrying about race conditions across threads. Though, I'm also not convinced that immutable things are any better than traditional locking strategies. Is that race truly won?
  - dbaupp 12y ago
    One doesn't need to keep large copies, since immutability allows common substructures to be shared. (That said, it still seems rather unlikely that an immutable implementation will use less memory.)
    - Rapzid 12y ago
      That's not a property of immutability. That's a property of certain specialized data structures, see "Purely Functional Data Structures" for a start, implemented in clojure.
      - chowells 12y ago
        Well, it's a property of basically everything except arrays. So it's more than just "certain specialized data structures".
        taeric 12y ago
        To be fair, many folks learn immutable data structures with the so called "persistent" data structures. Which are cool, to be sure. They are far from new, however. So, I'll be a little surprised if it turns out they are a panacea.

surrealize 12y ago

At first blush it seems fine to me; updating a purely-functional tree requires work that's O(depth of tree), and updating a Merkle tree also requires work that's O(depth of tree). I think that means that using a purely-functional structure to implement a Merkle tree requires at most a constant factor of extra time/space over using a mutable tree.