Transient collections for Scala?

Question

Clojure has a very nice concept of transient collections. Is there a library providing those for Scala (or F#)?

Answer 1

I don't know of any library for this in F# (nothing in the standard library, and I don't recall seeing anyone blog anything like this, though there are a number of libraries for simple persistent/immutable structures). It would be great for some third-party to create such a library. Rich Hickey is the man these days when it comes to these awesome practical (mostly-)functional data structures, I love reading about that stuff.

Answer 2

This sounds like a really great concept for language like F#, thanks for an interesting link!

When programming with arrays, F# programmers use exactly the same pattern. For example, create a mutable array, initialize it imperatively, return it and then work with it using functions that treat it as immutable such as Array.map (even though the array can actually be mutated as there is no transient array).

Using seq<'a> type: One way to do something similar is to convert the data structure to a generic sequence (seq<'a>) which is an immutable data type and so you cannot (directly) modify the original data structure via seq<'a>. For example:

let test () = 
  let arr = Array.create 10 0
  for i in 0 .. (arr.Length - 1) do
    arr.[i] <- // some calculation
  Array.toSeq arr

The good thing is that the conversion is usually O(1) (arrays/lists/.. implement seq<'a> as an interface, so this is just cast). However, seq<'a> doesn't preserve properties of the source collection (such as efficiency, etc) and you can process it only using generic functions for working with sequences (from the Seq module). However, I think this is relatively close to the transient collections pattern.

Similar .NET type is also ReadOnlyCollection<'a> which wraps a collection type (somewhat more powerful than seq<'a>) into an immutable wrapper whose operations for modifying collection throw exception.

Related types: For more complicated types of collections, F#/.NET usually have both mutable and immutable implementation (the immutable one coming from F# libraries). The types are usually quite different, but sometimes share a common interface. This makes it possible to use one type when you use mutation and convert it to the other type when you know that you won't need it anymore. However, here you need copy data between different structures, so the conversion definitely isn't O(1). It may be something between O(n) and O(n*log n).

Examples of similar collections are mutable Dictionary<'Key, 'Value> with immutable Map<'Key, 'Value> and mutable HashSet<'T> or SortedSet<'T> with immutable set<'T> (from F# libraries).

Answer 3

Please have a look at the following post by Daniel Spiewak:
http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala

He also ported the algorithm by Rich Hickey to Scala. In the article IntMap is also mentioned which is almost as fast the Clojure implementation.