Hacker News new | past | comments | ask | show | jobs | submit login




I see. So, let's say I have a tree with arbitrary number of nodes branching into further nodes and so on. (My 'state')

Can I now make a single call to some API-function that gives me an almost identical (immutable) tree as a result except that some leaf somewhere has a modified value, or where some node has been deleted?

And, would this internally happen without much copying?


The answer to all your questions is all "yes" technically, but the way you've worded them makes me think just saying "yes" will be a bit misleading to you. So let's take a real-world example. I'll use pseudo-Scala syntax since that's fairly similar to a lot of imperative languages.

Let's construct a tree data structure from scratch and see how to update it.

  abstract class BinaryTreeOfInts
  final class Leaf(final value: Int) extends BinaryTreeOfInts
  final class Node(final value: Int, final left: BinaryTreeOfInts, final right: BinaryTreeOfInts) extends BinaryTreeOfInts
All fields here are by reference.

So because everything is final here, we've constructed an immutable tree. You cannot update any of these values once it's been constructed.

Let's see how you might construct the following binary tree

    5
   / \
  6   1
     / \
    2   3

  myTree = Node(
    5,
    Leaf(6)
    Node(
      1,
      Leaf(2),
      Leaf(3)
  )
I want to modify 5 now to be 10

   newTree = Node(10, myTree.left, myTree.right)
Done. This is effectively one operation. newTree and myTree are both still immutable, but there's a ton of sharing going on. Now this is the best case scenario. Modifying a leaf is the worst case scenario, but even there only requires as many operations as there are levels in your tree, which, as long as you have a fairly balanced tree, only grows logarithmically in the number of elements you have.

To illustrate let's make another change, this time changing 3 to 30.

  anotherTree = Node(
    newTree.value,
    newTree.left,
    Node(
      newTree.right.value,
      newTree.right.left,
      Leaf(30)
    )
  )
Note I've had to instantiate a new Node for each level of the tree, and I've made a new Leaf, but otherwise everything else is shared. Now this is the low-level way of performing these changes. There are various APIs and tricks to make this look a lot cleaner in code so writing this out isn't as tedious, but I figured I'd present the low-level way to make things less magical.

BTW, the logarithmic time factor to update a leaf is why you will often see logarithmic factors in time complexities of various operations on immutable data structures.


> BTW, the logarithmic time factor to update a leaf is why you will often see logarithmic factors in time complexities of various operations on immutable data structures.

A mutable tree requires the same logarithmic time factor to update a leaf, because it also requires logarithmic time to access the leaf. It seems like the real difference between the mutable and the immutable structure is that the mutable structure requires O(1) space to do the update, while the immutable one requires O(log n) space in addition to the common requirement of O(log n) time.


Sort of. Structural sharing generally actually results in amortized constant space operations if you don't need the copies. In this case, if you aren't actually using the other tree, the nodes could be GC-ed. In the most ideal case they could be GC-ed as you're constructing the new nodes, though I imagine this essentially never happens (hence amortized). But regardless you're right that the thing to focus on is space rather than time when looking at how it would be different in an immutable vs mutable context.

Also my comment was incomplete. What I should've added is that most immutable data structures are trees under the hood in some form or another, hence many operations have a logarithmic factor. Mutable data structures provide more options when you want constant time access.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: