3

I've been experimenting with Scala for some time, and have often encountered the advice to favor immutable data structures.

But when you have a data structure like e.g. a 3D scene graph, a large neural network, or anything with quite a few objects that need frequent updates (animating the objects in the scene, training the neural net, ...), this seems to be

  1. horribly inefficient at runtime since you need to constantly recreate the whole object graph, and

  2. difficult to program since when you have a reference to some objects that need to be updated, you can't just call setters on them but you need copy the object graph and replace the old objects with the updated ones.

How are such things dealt with in idiomatic Scala?

herman
  • 11,740
  • 5
  • 47
  • 58
  • 1. The immutable data structures usually allow updating without copying the whole data. 2. Have you heard of lenses? (Probably related: http://stackoverflow.com/questions/3900307/cleaner-way-to-update-nested-structures) – Gábor Bakos Mar 07 '14 at 10:49
  • 1
    @GáborBakos 1. actually, such structures are subset of immutable data structures and are named [persistent](https://en.wikipedia.org/wiki/Persistent_data_structure) and some built-in scala collections are persistent (e.g. List) 2. Even if lenses were a magic wand, without proper spell *use lenses* is kinda useless tip – om-nom-nom Mar 07 '14 at 10:55
  • @om-nom-nom Thanks for the comment. I was hoping the stack overflow link provided ideas how to use lenses. I was honestly curious that the lenses were not working for her/him or was just unknown. I hope my comment was not formulated offensively, in that case I apologize. – Gábor Bakos Mar 07 '14 at 11:00
  • No offence taken, no offence given, just noticing that lenses is a **easier** way to update nested structures, but in case of graphs, there still *may* be a lot of cruft – om-nom-nom Mar 07 '14 at 11:05
  • @GáborBakos I had heard of lensens, but was 1) hoping that such a fairly common situation wouldn't require a (rather complex) solution that also relies on macros 2) thinking that for graph structures they wouldn't help much with the second problem and 3) thinking that they wouldn't help at all with the first problem. Also, of course I know a complete deep copy is not necessary with immutable data structures, but at least you need to create new objects for the ones you want to update, and also for each one that references one of these, and so on. Otherwise they wouldn't really be immutable. – herman Mar 07 '14 at 12:13

1 Answers1

4

Scala is multi-paradigm: OO and functional, mutable and immutable.

Complex graphs are one example of a data structure that, as you have identified, may be easier to work with in a mutable context. If so, make the data structure mutable.

Idiomatic Scala is to use the right paradigm to solve your problem.

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
  • The question is then how to find the right paradigm. Is it really as simple as "immutability seems to make things too difficult, I'll just fall back to a mutable data structure"? I just found http://stackoverflow.com/questions/9891522, which has an answer that mentions the idea that graph structures don't necessarily need to be directly represented as object graphs (where the connections are represented by the references between the objects). Indeed, if an edge is just an object in a `Set` with a reference to the 2 nodes, updating it just means to replace that object in the `Set`. – herman Mar 07 '14 at 21:43
  • @herman - Any difficult-to-update immutable object can be replaced by a cloud of independent objects with unique IDs and all the actual pointers stored in an immutable set. Sometimes this is helpful. Sometimes it is a big headache with no additional benefit. Which it is really depends on the details. It is not _merely_ that if immutability is too difficult (or slow) you should fall back to mutability, but it's a valid reason to do so, especially if you don't need the advantages that immutability can provide (except for the baseline "harder to shoot yourself in the foot" advantage). – Rex Kerr Mar 07 '14 at 21:59