- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
How to create an immutable copy of a collection?
Mon, 2009-02-02, 17:51
As a first Scala project I'm implementing Bloom filters, a set-like data structure. The actual algorithm is trivial in Scala (both the 'add' and 'contains' operations are one-liners: woot!) but packaging it up in the same manner as the built-in collection classes was challenging.
You can see my code here: <http://gist.github.com/56785> (comments/corrections welcomed)
The main thing I'm still confused about is how to convert between mutable and immutable instances of a collection type (in my case, BitSet.) In Scala (like Java?) the clone method preserves mutability — cloning an immutable object returns an immutable object, cloning a mutable one returns a new mutable one.
So my question: Given a collection of the abstract base type, how do I get an immutable version of that object? For example, my BloomFilter class, which is immutable, takes a BitSet in its constructor. But that BitSet might be mutable or immutable. If it's mutable, then its original owner might mutate it behind my back, causing the BloomFilter object to mutate. So I need to create an immutable copy of that set to assign as an instance variable. How?
(Note that calling clone on the BitSet isn't sufficient, because it might create a new mutable object. Yes, it will prevent changes to the original BitSet from altering my state; but since I have a public accessor that returns my BitSet, if that object is mutable then a caller could cast it to the mutable subtype and change it that way.)
The behavior I'm looking for is something like Cocoa's -copy and -mutableCopy methods: Their semantics on collections are that -copy always creates an immutable copy, while -mutableCopy creates a mutable one. The idiom then is that, to freeze a collection that you want to use as immutable state, you just call -copy on it. This is often very cheap, as the -copy implementation for all immutable collections is simply a no-op that returns self.
—Jens
PS: GitHub's language selector for gists doesn't include Scala, even though it has every other language under the sun. Someone needs to rectify this!
You can see my code here: <http://gist.github.com/56785> (comments/corrections welcomed)
The main thing I'm still confused about is how to convert between mutable and immutable instances of a collection type (in my case, BitSet.) In Scala (like Java?) the clone method preserves mutability — cloning an immutable object returns an immutable object, cloning a mutable one returns a new mutable one.
So my question: Given a collection of the abstract base type, how do I get an immutable version of that object? For example, my BloomFilter class, which is immutable, takes a BitSet in its constructor. But that BitSet might be mutable or immutable. If it's mutable, then its original owner might mutate it behind my back, causing the BloomFilter object to mutate. So I need to create an immutable copy of that set to assign as an instance variable. How?
(Note that calling clone on the BitSet isn't sufficient, because it might create a new mutable object. Yes, it will prevent changes to the original BitSet from altering my state; but since I have a public accessor that returns my BitSet, if that object is mutable then a caller could cast it to the mutable subtype and change it that way.)
The behavior I'm looking for is something like Cocoa's -copy and -mutableCopy methods: Their semantics on collections are that -copy always creates an immutable copy, while -mutableCopy creates a mutable one. The idiom then is that, to freeze a collection that you want to use as immutable state, you just call -copy on it. This is often very cheap, as the -copy implementation for all immutable collections is simply a no-op that returns self.
—Jens
PS: GitHub's language selector for gists doesn't include Scala, even though it has every other language under the sun. Someone needs to rectify this!
Tue, 2009-02-03, 12:37
#2
Re: How to create an immutable copy of a collection?
Hi Petr, Jens,
Petr Gladkikh wrote:
> You may construct one of collections from scala.collection.immutable.*
> or just use methods like "toArray"
Methods like toArray, but not toArray, because arrays are mutable. ;-)
E.g. toList.
I think the problem is a bit more complicated than this. If you have a
HashSet[HashSet[Foo]], calling .toList on it won't give you a completely
immutable data structure; you'll end up with a List[HashSet[Foo]]. If
you have a reference to such a list, you'll always get exactly the same
hashset objects, but those hashsets won't necessarily have exactly the
same contents.
It's a bit of a cop-out answer, but my best suggestion would be to just
make sure you understand what is mutable and what is immutable and don't
try to abstract away the difference. Immutable data is preferable in
many ways, but there's a place for mutable data structures.
Cheers,
Jon
Tue, 2009-02-03, 13:17
#3
Re: How to create an immutable copy of a collection?
Jens Alfke wrote:
> PS: GitHub's language selector for gists doesn't include Scala, even
> though it has every other language under the sun. Someone needs to
> rectify this!
Well, I emailed the site to politely ask them to add it. Let's see what
happens.
Cheers,
Jon
Tue, 2009-02-03, 15:27
#4
Re: How to create an immutable copy of a collection?
On Tue, Feb 3, 2009 at 4:06 AM, Jon Pretty <jon.pretty@sygneca.com> wrote:
Jens Alfke wrote:
> PS: GitHub's language selector for gists doesn't include Scala, even
> though it has every other language under the sun. Someone needs to
> rectify this!
Well, I emailed the site to politely ask them to add it. Let's see what
happens.
When the GitHub folks recruited me to move Lift to GitHub, they did offer to be Scala-friendly. If they don't respond positively to you, let me know and I'll ping them.
Cheers,
Jon
--
Jon Pretty | Sygneca Ltd.
--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Git some: http://github.com/dpp
Tue, 2009-02-03, 15:47
#5
Re: How to create an immutable copy of a collection?
I found the #github IRC channel quite helpful.
2009/2/3 David Pollak <feeder.of.the.bears@gmail.com>
2009/2/3 David Pollak <feeder.of.the.bears@gmail.com>
On Tue, Feb 3, 2009 at 4:06 AM, Jon Pretty <jon.pretty@sygneca.com> wrote:Jens Alfke wrote:
> PS: GitHub's language selector for gists doesn't include Scala, even
> though it has every other language under the sun. Someone needs to
> rectify this!
Well, I emailed the site to politely ask them to add it. Let's see what
happens.
When the GitHub folks recruited me to move Lift to GitHub, they did offer to be Scala-friendly. If they don't respond positively to you, let me know and I'll ping them.
Cheers,
Jon
--
Jon Pretty | Sygneca Ltd.
--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Git some: http://github.com/dpp
On Mon, Feb 2, 2009 at 10:45 PM, Jens Alfke wrote:
> So my question: Given a collection of the abstract base type, how do I get
> an immutable version of that object? For example, my BloomFilter class,
> which is immutable, takes a BitSet in its constructor. But that BitSet might
> be mutable or immutable. If it's mutable, then its original owner might
> mutate it behind my back, causing the BloomFilter object to mutate. So I
> need to create an immutable copy of that set to assign as an instance
> variable. How?
Since no one else answered I'd try :)
You may construct one of collections from scala.collection.immutable.*
or just use methods like "toArray"
val mu = scala.collection.mutable.HashSet[Int](1, 2, 3)
val immu = scala.collection.immutable.HashSet(mu.toArray:_*)
val immu2 = mu.toArray
immu foreach print; println
mu -= 2
immu foreach print; println