immutable half-edge data structure

[strattonbrazil]

I realize there are many advantages to immutable data structures and
scala provides many different classes with immutable functionality
like the List.  However, I can't seem to wrap my head around some more
complex data structures that are interconnected at so many instances.
One in particular is with polygonal models using the half-edge data
structure.

http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml

I've implemented this several times before, but working with these
structures with immutable classes seems incredibly complex especially
if they're referenced by index instead of class reference.

For a polygonal mesh,
a vertex has an <x,y,z> coordinate and a reference to one of the edges
it touches
a face and a reference to one of it's edges
a edge has a reference to the next edge on the same face, the edge on
the adjacent face, the first vertex of the edge, and a reference to
the the face itself that it lies on

If each one of these references is stored as an integer keyed to a
hashmap, each would probably need a reference to the mesh holding the
hashmaps of vertices, faces, and edges as well.  That seems to make
sense, but it makes manipulating the geometry extremely tedious.  As a
simple example, one might need to extrude a face on the top of a cube.
 So, four new vertices would need to be created, but since no edges
are made yet, they're just dummy vertices classes I'll have to
recreate later when I have references to the edges and faces and vice
versa.

I assume this kind of thing is handled already in functional
programming when doing anything graph related, but I'd appreciate some
advice or references to good reading material on handling these kind
of problems in a functional way.  This is more of a general functional
programming question, but I'm trying to implement it specifically in
scala.

Josh

[Ben Hutchison-3]

On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <strattonbrazil@...> wrote:
> I realize there are many advantages to immutable data structures and
> scala provides many different classes with immutable functionality
> like the List.

Immutability is good, but its not appropriate everywhere. This nicely
summarizes much of my design aesthetic: http://clojure.org/state

 However, I can't seem to wrap my head around some more
> complex data structures that are interconnected at so many instances.
> One in particular is with polygonal models using the half-edge data
> structure. [snip] ...

Is the essence of your problem Cyclic References?

I think its logically impossible to ever create a cycle solely with
wholly immutable objects.

One approach I favor is to use mutability locally in a creation method
with an "unpublished" object. Mutate it into the state you want to
outside world to see, then publish (ie reveal) it only through types
that hide the mutation operations.

-Ben

[Ishaaq Chandy]

If Scala had write-once vals - I think that would solve the problem with constructing immutable data with cyclical references.

Using write-once vals you could construct the data graph and once all references have stabilised to their final states you can then expose it to the world and take advantage of all the benefits that immutability gives you.

Note that "lazy vals" don't fill this hole.

Ishaaq

2009/11/2 Ben Hutchison <brhutchison@...>

On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <strattonbrazil@...> wrote:
> I realize there are many advantages to immutable data structures and
> scala provides many different classes with immutable functionality
> like the List.

Immutability is good, but its not appropriate everywhere. This nicely
summarizes much of my design aesthetic: http://clojure.org/state

 However, I can't seem to wrap my head around some more
> complex data structures that are interconnected at so many instances.
> One in particular is with polygonal models using the half-edge data

> structure. [snip] ...

Is the essence of your problem Cyclic References?

I think its logically impossible to ever create a cycle solely with
wholly immutable objects.

One approach I favor is to use mutability locally in a creation method
with an "unpublished" object. Mutate it into the state you want to
outside world to see, then publish (ie reveal) it only through types
that hide the mutation operations.

-Ben

[Daniel Sobral]

It is perfectly possible to create cycles with lazy structures.

On Mon, Nov 2, 2009 at 3:01 AM, Ben Hutchison <brhutchison@...> wrote:

On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <strattonbrazil@...> wrote:
> I realize there are many advantages to immutable data structures and
> scala provides many different classes with immutable functionality
> like the List.

Immutability is good, but its not appropriate everywhere. This nicely
summarizes much of my design aesthetic: http://clojure.org/state

 However, I can't seem to wrap my head around some more
> complex data structures that are interconnected at so many instances.
> One in particular is with polygonal models using the half-edge data

> structure. [snip] ...

Is the essence of your problem Cyclic References?

I think its logically impossible to ever create a cycle solely with
wholly immutable objects.

One approach I favor is to use mutability locally in a creation method
with an "unpublished" object. Mutate it into the state you want to
outside world to see, then publish (ie reveal) it only through types
that hide the mutation operations.

-Ben

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

[Ishaaq Chandy]

Ok, your post prompted me to search on google and I found this:

http://www.haskell.org/haskellwiki/Tying_the_Knot

However, my haskell-foo isn't quite there yet - can someone please translate?

Ishaaq

2009/11/3 Daniel Sobral <dcsobral@...>

It is perfectly possible to create cycles with lazy structures.

On Mon, Nov 2, 2009 at 3:01 AM, Ben Hutchison <brhutchison@...> wrote:

On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <strattonbrazil@...> wrote:
> I realize there are many advantages to immutable data structures and
> scala provides many different classes with immutable functionality
> like the List.

Immutability is good, but its not appropriate everywhere. This nicely
summarizes much of my design aesthetic: http://clojure.org/state

 However, I can't seem to wrap my head around some more
> complex data structures that are interconnected at so many instances.
> One in particular is with polygonal models using the half-edge data

> structure. [snip] ...

Is the essence of your problem Cyclic References?

I think its logically impossible to ever create a cycle solely with
wholly immutable objects.

One approach I favor is to use mutability locally in a creation method
with an "unpublished" object. Mutate it into the state you want to
outside world to see, then publish (ie reveal) it only through types
that hide the mutation operations.

-Ben

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

[Aaron Harnly-2]

On Nov 2, 2009, at 7:40 PM, Ishaaq Chandy wrote:

http://www.haskell.org/haskellwiki/Tying_the_Knot

However, my haskell-foo isn't quite there yet - can someone please translate?

I’m sure someone can write a tidier example, but off the cuff, something like the below. Note how the geta “thunk” is, crucially, in the same scope as the value ‘a’ that it returns.

object Example {

  case class A(val b: B)

  case class B(_a: () => A) {

    def a = _a()

  }

  

  val geta: () => A = () => a

  val b = new B(geta)

  val a = new A(b) 

  println(b)

  println(a)

  println(a.b)

  println(b.a)

}

[Miles Sabin]

On Tue, Nov 3, 2009 at 3:07 AM, Aaron Harnly
<scala-user@...> wrote:
> I’m sure someone can write a tidier example, but off the cuff, something
> like the below. Note how the geta “thunk” is, crucially, in the same scope
> as the value ‘a’ that it returns.

The principle is the same, but here no explicit thunk is needed,

scala> trait A { val b : B } ; trait B { val a : A }
defined trait A
defined trait B

scala> val a = new A { thisA => val b = new B { val a = thisA } }
a: $anon forSome { type $anon <: java.lang.Object with A{def b:
java.lang.Object with B{def a: $anon}} } = $anon$1@266b44

scala> a.b
res0: java.lang.Object with B{def a: $anon} = $anon$1$$anon$2@6743e2

scala> a.b.a
res1: $anon = $anon$1@266b44

scala> a.b.a.b
res2: java.lang.Object with B{def a: $anon} = $anon$1$$anon$2@6743e2

Cheers,


Miles

--
Miles Sabin
tel: [phone]
skype:  milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

[Burkhard Ludwig]

I agree with Ben, immutability is not appropriate everywhere.

2009/11/2 Ben Hutchison <brhutchison@...>

[snip]

Is the essence of your problem Cyclic References?

 

Yes, i think this is the essence, and if I'm not mistaken, the biggest problem whith them is that there is no data sharing at all in a immutable variant of a circular data structure.  E.g.

Here is a list

   scala> val a = List(1,2,3)

   a: List[Int] = List(1, 2, 3)

Update the first element

   scala> val b = 0 :: a.tail

   b: List[Int] = List(0, 2, 3)

Most of the data is still represented with the same objects

   scala> a.tail eq b.tail

   res3: Boolean = true

      

But this wouldn't be the case for e.g. circular lists: every cons-cell of a and b would be different objects. This carries over to the half-edge data structure where you can reach every element (face, half edge, vertex) from each other by pointer chasing. (Ouups, pointer, my C-heritage leaked through). So, e.g. when coloring the top of a white box black you end up in two separate sets of interconnected objects and, worse, when you build up such a graph one at a time you end up with a quadratic algorithm, at least in time. (The GC can rescue you from quadratic space consumption, I hope)

In other words, translating that haskell-magic into scala wouldn't help much.

Well as I said, if I am not mistaken.

Greetings,

Burkhard.