Object hierarchies consisting of immutable objects?

[Kandilaki]

Hello,

I'm a Java programmer who studied the Programming in Scala book. I'd
like to practise Scala and functional programming by creating a little
Scala Swing application which helps the user to create project plans.
At the moment I struggle a bit with how to design the model objects.

A Project consists of Workpackages. Workpackages contain Tasks. And
finally Tasks contain Deliverables. Of course each of those entities
has properties like a name, an id, a start date and so on. Those
properties can change over time. May question is how to model these
state changes.
The most imperative approach would be to implement those properties as
vars. To be more functional one would have to model those properties
as vals. For each property change a new object has to be created
substituting the old one.
Given that immutable Lists are also vals (e.g. val tasks: List[Task]
= ...), a modification of a deliverable's name would eventually cause
the whole object tree to be copied. This looks quite strange to me. In
my humble opinion the problem at hand is more suitable for the
imperative style.

How would you design this project - workpackage - task - deliverable
hierarchy? Is it feasible to use immutable objects only? How would you
approach the problem in a more functional way?

Cheers,
K.

[Miguel Negrão]

I have a quite similar question same question, but dealing with collections. How to deal with immutable collections inside collections, i.e. a list inside a map inside a list, for instance. Any change in the innermost item would cause the whole structure to have to be recreated, but I don't understand what is the syntax to do this...

best

Miguel Negrão

[Brian Maso]

If its immutable, you wouldn't "change" it -- you would replace it's value in the containing collection.

Scala's immutable collections are written to be efficient under replaced contents. Take, for example, a List (which is a classic cons list): Replacing the value at the head of the list actually only replaces the node object at the head of the list. The entire tail is preserved. Replacing the tail-most item, however, would cause the entire List to have to be recreated, because either directly or indirectly every other node holds a reference to the tail-most item.

Maps and other structures similarly attempt to preserve as must of the data structure as possible during value replacement. The concept is called "persistent data structures" (not 'persistent' in the persistent-DB sense on the word, but rather in the sense that as much of the data structure is re-used as possible). Check out the wikipedia article, which is a good summary of the concept: http://en.wikipedia.org/wiki/Persistent_data_structure.


--
Best regards,
Brian Maso
(949) 395-8551
Follow me: @bmaso
br...@blumenfeld-maso.com

[Kevin Wright]

I recommend that you start with Daniel Speiwak's talk from #nescala, here: http://vimeo.com/20262239

It should make everything much clearer...

--
Kevin Wright

gtalk / msn : kev.lee...@gmail.com

mail: kevin....@scalatechnology.com

vibe / skype: kev.lee.wright

quora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

[Rick Mugridge]

I mostly use immutable objects (ie, 98% of the time). But I find that there are some circumstances where localised mutability is worth the downsides.

Eg, I have a system (32KLOC) that manages FitNesse wiki pages in a hierarchy defined by the underlying file system. The user is able to edit wiki pages, add new ones, etc. My tool looks for duplication across tests/tables and proposes abstractions with parameters, so it needs to look across pages quickly, using actors. It maintains a SoftReference to the AST of each page, for caching. A page within the larger hierarchy is complex in its own right, and has several aspects that are each represented by an object (such as managing persistence, tree structure, undo/redo on editing the text, display of html and wiki, and etc). So some parts of Page are mutable (as is undo/redo, configuration). Much of the sub-structure is immutable (eg, the AST). It would be painful to treat pages in a hierarchy as an immutable structure and manage changes (and thus inter-dependencies) across the whole (I've done simpler versions of that in the past with Haskell). The downside is that I have to take extra special care with concurrent access to those mutable structures, so I try to isolate that as much as possible.

Cheers, Rick

PS, I have considered making each Page an actor, but that would have a big impact on the design. I may try that one day...

[Miguel Negrão]

On Tuesday, May 10, 2011 1:01:02 AM UTC+2, Brian Maso wrote:

If its immutable, you wouldn't "change" it -- you would replace it's value in the containing collection.

Scala's immutable collections are written to be efficient under replaced contents. Take, for example, a List (which is a classic cons list): Replacing the value at the head of the list actually only replaces the node object at the head of the list. The entire tail is preserved. Replacing the tail-most item, however, would cause the entire List to have to be recreated, because either directly or indirectly every other node holds a reference to the tail-most item.

Maps and other structures similarly attempt to preserve as must of the data structure as possible during value replacement. The concept is called "persistent data structures" (not 'persistent' in the persistent-DB sense on the word, but rather in the sense that as much of the data structure is re-used as possible). Check out the wikipedia article, which is a good summary of the concept: http://en.wikipedia.org/wiki/Persistent_data_structure.

Yes, I understand that when I "change" an immutable collection a new one gets created, but in order to put in the same location where the old one was in the parent collection I have to also create a new parent collection, and if that one is inside another one I also have to create a new one, and so forth...

For instance, let's say I have

var x = List(List(List(1,2,3)))

and I want to change the 1 to a 7. The only I know how to do this is

x updated (0, x(0) updated (0, x(0)(0) updated ( 0, 7) ) )

is there a better way to do it ?

best,

Miguel Negrão

[Kevin Wright]

In that particular case, with a List, the easiest (and fastest, and most memory efficient) way is:

    7 :: x.tail

 

best,

Miguel Negrão

[Dennis Haupt]

that's a problem you have with immutable data structures. some things are simply not possible:

class a(val b:B)
class b(val a:A)

;)

-------- Original-Nachricht --------
> Datum: Tue, 10 May 2011 14:12:14 +0100
> Von: Kevin Wright <kev.lee...@gmail.com>
> An: scala...@googlegroups.com
> Betreff: Re: [scala-user] Re: Object hierarchies consisting of immutable objects?

[Seth Tisue]

>>>>> "Dennis" == Dennis Haupt <h-s...@gmx.de> writes:

Dennis> that's a problem you have with immutable data structures. some
Dennis> things are simply not possible: class a(val b:B) class b(val
Dennis> a:A)

Not impossible!

Miles Sabin on how to make an immutable one-object cycle:

http://scala-programming-language.1934581.n4.nabble.com/immutable-object-graphs-in-Scala-td1947031.html#a1947032

The same technique with two classes:

scala> :paste
class A private (_b: B) {
val b = if(_b == null) new B(this) else _b
def this() = this(null)
}

class B(val a: A)
^D
defined class A
defined class B

scala> new A
res0: A = A@39c931fb

scala> res0.b
res1: B = B@6b79d47f

scala> res0.b.a
res2: A = A@39c931fb

How useful that is in practice, I don't know. But certainly the
following immutable cycle is useful:

scala> val ones: Stream[Int] = 1 #:: ones
ones: Stream[Int] = Stream(1, ?)

scala> ones.take(10).force
res5: scala.collection.immutable.Stream[Int] = Stream(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Here the knot is tied using a call-by-name parameter rather than Miles's trick.

--
Seth Tisue | Northwestern University | http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/

[Dennis Haupt]

it's useful for easy navigation

-------- Original-Nachricht --------
> Datum: Tue, 10 May 2011 09:59:14 -0400
> Von: Seth Tisue <se...@tisue.net>

> An: scala...@googlegroups.com
> Betreff: Re: [scala-user] Re: Object hierarchies consisting of immutable objects?

> >>>>> "Dennis" == Dennis Haupt <h-s...@gmx.de> writes:

[Tommaso Galleri]

>> var x = List(List(List(1,2,3)))

 

> 7 :: x.tail

 

This will not work, x is List[List[List[Int]]] and not List[Int]

 

This should do the trick, but it’s not pretty:

 

x map { _ map { 7 :: _.tail } }

 

 

Tommaso

 

---

---

The information included in this email and any files transmitted with it may contain information that is confidential and it must not be used by, or its contents or attachments copied or disclosed, to persons other than the intended addressee. If you have received this email in error, please notify BJSS. In the absence of written agreement to the contrary BJSS' relevant standard terms of contract for any work to be undertaken will apply. Please carry out virus or such other checks as you consider appropriate in respect of this email. BJSS do not accept responsibility for any adverse effect upon your system or data in relation to this email or any files transmitted with it. BJSS Limited, a company registered in England and Wales (Company Number 2777575), VAT Registration Number 613295452, Registered Office Address, First Floor, Coronet House, Queen Street, Leeds, LS1 2TW

[Dennis Haupt]

such nested collections are never pretty. composite structures are better for this

-------- Original-Nachricht --------
> Datum: Tue, 10 May 2011 15:37:38 +0100
> Von: "Tommaso Galleri" <Tommaso...@bjss.com>
> An: "Kevin Wright" <kev.lee...@gmail.com>, scala...@googlegroups.com
> Betreff: RE: [scala-user] Re: Object hierarchies consisting of immutable objects?

> <mailto:kev.lee...@gmail.com> mail: kevin....@scalatechnology.com

>
> vibe / skype: kev.lee.wright
>
> quora: http://www.quora.com/Kevin-Wright
> twitter: @thecoda
>
>
>
> "My point today is that, if we wish to count lines of code, we should not
> regard them as "lines produced" but as "lines spent": the current
> conventional wisdom is so foolish as to book that count on the wrong side of the
> ledger" ~ Dijkstra
>
>
>
>
>

[Dennis Haupt]

trees for example. or tale a look at scala.vector

-------- Original-Nachricht --------
> Datum: Tue, 10 May 2011 17:10:39 +0200
> Von: "Dennis Haupt" <h-s...@gmx.de>
> An: "Tommaso Galleri" <Tommaso...@bjss.com>, scala...@googlegroups.com, kev.lee...@gmail.com
> Betreff: Re: RE: [scala-user] Re: Object hierarchies consisting of immutable objects?

[Kandilaki]

Thank you all for your posts so far.

I've done a little desktop research in the meantime and I've stumbled across a few hints and resources. One way of achieving a more functional domain model would be to implement event sourcing. It is described in a series of blog posts: http://blog.zilverline.com/2011/02/01/towards-an-immutable-domain-model-introduction-part-1/. Besides, I now know that 'Immutable domain model' would have been a better subject for my original post.

Unfortunately I still don't know how to design my project planning application.

Could someone point me to a open source Scala project which serves as a good code reading source? Odersky's book encourages to do things functional. It says that Unit return type and vars indicate imperative style. While I totally understand that in some situations I just don't grok how to accomplish this. In my opinion at least in Odersky's book there is too less guidance of how to tackle real world applications in a functional style. I guess that could be a problem of Scala in general as it allows to just code the Java way in Scala. Maybe it would be a better learning path to master a purely functional language in order to be a good Scala developer.

May someone know a posterchild Scala project to learn from or some other resources dealing with that topic explicitly.

Cheers,
K.

[Miguel Negrão]

On Tuesday, May 10, 2011 4:37:38 PM UTC+2, Tommaso Galleri wrote:

>> var x = List(List(List(1,2,3)))

 

> 7 :: x.tail

 

This will not work, x is List[List[List[Int]]] and not List[Int]

 

This should do the trick, but it’s not pretty:

 

x map { _ map { 7 :: _.tail } }

What about :

 x = List(List( (1 to 1000) )) 

change element number 756 of the inner list to 0 ?

such nested collections are never pretty. composite structures are better for this

What are composite structures ? Where can I read about them ?

best,

Miguel Negrão

[Miguel Negrão]

On Tuesday, May 10, 2011 5:21:19 PM UTC+2, Dennis Haupt wrote:

trees for example. or tale a look at scala.vector

Scala vector help advises to use updated which was what I first posted...

best,

Miguel Negrão 

[Kevin Wright]

On 11 May 2011 00:00, "Miguel Negrão" <miguel.ne...@friendlyvirus.org> wrote:
>
>
>
> On Tuesday, May 10, 2011 4:37:38 PM UTC+2, Tommaso Galleri wrote:
>>
>> >> var x = List(List(List(1,2,3)))
>>
>>  
>>
>> > 7 :: x.tail
>>
>>  
>>
>> This will not work, x is List[List[List[Int]]] and not List[Int]
>>
>>  
>>
>> This should do the trick, but it’s not pretty:
>>
>>  
>>
>> x map { _ map { 7 :: _.tail } }
>
>
> What about :
>
>  x = List(List( (1 to 1000) )) 
>
> change element number 756 of the inner list to 0 ?
>

I wouldn't do this. List is optimised for working with successive elements starting at the first.  If you need random access, use Vectors.

Having said that...

    def zeroElem[T](xs: List[T]) = (xs take 755) ::: ( 0 :: (xs drop 756) )
    x map { _ map { zeroElem _ } }

Though `updated` would be clearer here.

[Dennis Haupt]

http://en.wikipedia.org/wiki/Composite_pattern

basically, you have a nested structure of nodes. but since every element is a node and knows its children, you can solve your problems recursively.

-------- Original-Nachricht --------
> Datum: Tue, 10 May 2011 16:07:02 -0700 (PDT)
> Von: "Miguel Negrão" <miguel.ne...@friendlyvirus.org>
> An: scala...@googlegroups.com
> CC: Dennis Haupt <h-s...@gmx.de>, kev.lee...@gmail.com, Tommaso...@bjss.com

> Betreff: Re: RE: [scala-user] Re: Object hierarchies consisting of immutable objects?

>
>

[Tommaso Galleri]

> What about :

>  x = List(List( (1 to 1000) )) 

> change element number 756 of the inner list to 0 ?

 

You would not want to use a List (singly linked list), it’s not efficient to change an element in the middle of the list (a singly linked list is just efficient at one end).

 

Tommaso

 

 

---

[Matthew Pocock]

Hi Kandilaki,

I feel your pain over these nested collections. I've run into similar problems as I've been learning to use scala as more than a better Java syntax. One of the things I've had to re-learn is how I approach introducing types. In Java, adding a type is expensive. It involves a lot of code, and you often have to juggle multiple files. In scala, types are almost free (in coding effort). So where in Java I would use ints and strings, in scala I would use case classes/objects. Where in Java I would use ints for the four players sat around a card table, in scala I would create a sealed hierarchy with leftOf and rightOf defs and so on. Basically, because the types are almost free,  model your domain with types directly rather than storing it in primitives and collections.

So, when I see your list of list of lists of elements, I see something that looks like Java, and wonder what it is you where actually trying to model. Is it something that is fixed 3 levels deep or can it be any depth? What are the ints representing? Do you have a genuine need to update an element of the most nested list directly, or would every edit of a 'leaf' be initiated by a (recursive?) operation from the base of your data-structure?

My experience is that when you answer these kinds of questions, and stick in the extra (previously implicit) types, that most of the ugly goes away and a load of hidden bugs are unmasked or get fixed in the process.

Matthew

Cheers,
K.

--

Matthew Pocock

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

(0191) 2566550

[Miguel Negrão]

Hi Tommaso, Kevin,

  My question is not really about the type of collection used or it's performance (sorry, I wasn't very clear in my question). My question is about what is the easiest syntax to update an element deep inside a  immutable collection hierarchy.  It seems to me that the only way to do this for an item that is in any position of  vector is to use updated, but it's a bit boring that you have to first get the collection you want to update, i.e., x(0)(0), then get an updated version of that one, then get the parent, i.e. x(0), then get an updated version of that one and so forth... That's why I was wondering if there was a special syntax for it. I guess if there isn't such a syntax it's because, like it was mentioned, collection hierarchies are not the way to go in functional programming...

best,

Miguel Negrão

[Rex Kerr]

If you need to update elements in the middle of a collection, you want to use some sort of tree data structure.  Vector is a very broad tree, but you can do things like

  val v1 = Vector(Vector(1,2,3),Vector(4,5,6),Vector(7,8,9))
  val v2 = v1.updated(1, v1(1).updated(1, 0))

to go from
  1 2 3
  4 5 6
  7 8 9
to
  1 2 3
  4 0 6
  7 8 9

It is true that this is more awkward than with the same thing with a mutable collection:

    val a = Array(Array(1,2,3), Array(4,5,6), Array(7,8,9))
    a(1)(1) = 0

but you are accomplishing different things; in the immutable case, you still have your old v1 collection, while in the mutable case, the old one is gone.

If you are sure you don't need the old collection, then using mutable data structures gives better performance and greater convenience.  If you only thought you were sure, but forgot you were relying upon the old values, then you'll have a bug, and to fix it with a mutable collection you may have to make a copy of the whole structure which, typically, is not what mutable collections are designed to do efficiently (at least for large collections).

So it's really a matter of convenience and performance vs. safety.

The convenience isn't really an issue because all you have to do is

  def change[A](vv: Vector[Vector[A]], i: Int, j: Int, a: A) = vv.updated(i, vv(i).updated(j,a))

and then you can

  val v2 = change(v1, 1, 1, 0)

which is almost as nice as the original, or you can

  class ChangeVV[A](vv: Vector[Vector[A]]) {
    def change(i: Int, j: Int)(a: A) = vv.updated(i, vv(i).updated(j,a))
  }
  implicit def vectorvector_can_change[A](vv: Vector[Vector[A]]) = new ChangeVV[A](vv)

and then you can

  val v2 = v1.change(1,1)(0)

which is arguably at least as clear as a(1)(1) = 0.

So, after a little bit of work to make your code look nicer, it really comes down to performance vs. safety.

  --Rex

[Miguel Negrão]

Hi Rex,

In my case, I don't have performance critical stuff, so I think I prefer to have the safety. The functions you mentioned do make it a bit easier to use.

thanks for the help !

best,

Miguel Negrão

[Alex Cruise]

FWIW and IIUC zippers are designed for exactly this kind of problem.  

See http://stackoverflow.com/questions/3900307/cleaner-way-to-update-nested-structures

-0xe1a

[Brian Maso]

I was just playing with the zippers in anti-xml earlier this week. They are very cool. Really clever, and easy to use.

--
Best regards,
Brian Maso
(949) 395-8551
Follow me: @bmaso
br...@blumenfeld-maso.com