Recursive values?

[tolmasky]

I've been going through and trying to replace my mutable structures with immutable ones, the thing I've run into though is recursive structures. As a simple example:

x = { }
x.x = x;

How would I do something similar with I.Map? x.set("a", x) doesn't work because it stores the old one. (I'm converting a JS value, and as such fromJS doesn't work, but I can handle the conversion myself as long as I can figure out some way of getting a self reference to begin with)

[tolmasky]

From what I can tell, it seems that other languages solve this with lazy values (see: http://stackoverflow.com/questions/8374010/scala-circular-references-in-immutable-data-types ). immutable could do something like this:

function Lazy(aFunction)
{
    this.get = memoize(aFunction);
}

Then, in Map/List/etc's .get():

get = function(key)
{
    value = /*current*/get(x);
    if (value.constructor === Lazy)
         return value.get();
    return value;
}

Now, we can do the following:

var recursive = I.Map().set("x", Lazy(() => recursive));
console.log(recursive === recursive.get("x")) // prints true

//We can also use it to make doubly linked lists:

var node0 = I.Map({ prev: null, next: Lazy(() => node1) })
var node1 = I.Map({ prev:  Lazy(() => node0), next: Lazy(() => node2) })
var node2 = I.Map({ prev: Lazy(() => node1), next: Lazy(() => node3) })
var node3 = I.Map({ prev: Lazy(() => node2), next: null })

[leebyron]

There is no way (intentionally) for immutable persistent data structures to contain circular references. Immutable structures can contain circular references, but in order to be persistent and take advantage of structural sharing, they need to be acyclic. The stack-overflow you link to illustrates this well - showing how a double-linked list needs to make a complete copy in order to perform an append operation.

There are some other problems that emerge from circular references in values, such as deep equality checking and hash-value computation.

Languages based on immutable structures handle this in different ways:

Scala has lazy var which is pretty much what you wrote up here. A deferred memoized function.

Clojure has atom which is a bit different (and easier to understand IMHO). Atom is an atomically locked mutable wrapper. Since JavaScript is single threaded, no locks are necessary so it's only a mutable wrapper. In other words: { value: "foobar" }.

For equality and hashing, Atoms are treated as Objects not as Values. So { value: "A" } !== { value: "A" }.

So you might treat this like:

var node0 = I.Map({ prev: null, next: {} })
var node1 = I.Map({ prev:  {value: node0}, next: {} })
node0.get('next').value = node1;
var node2 = I.Map({ prev: {value: node1}, next: {} })
node1.get('next').value = node2;
var node3 = I.Map({ prev: {value: node2}, next: null })
node2.get('next').value = node3;

---

However, both approaches: lazy function or atom object are totally fine! This data structure library has no opinion on either, you just need to be aware of their use so you can treat them appropriately:

// Lazy function
node3.get('prev').get();
// Atom object
node3.get('prev').value;

[leebyron]

For those looking for an implementation of Lazy evaluated variables, try this:

function lazy(fn) {
  var didRun;
  var result;
  return { get: () => didRun ? result : (didRun = true, result = fn()) };
}

Usage example

var lazyFoo = lazy(() => "foo");
console.log(lazyFoo.get());

[leebyron]

I'm currently not sure baking this concept into the library, and changing the get definition to evaluate the lazy function is the right thing to do, as it would have pretty serious implications and possibly introduce bugs or at the very least confusion on equality checking and hash computation.

At this point I think it's reasonable to assume if you're using lazy values to determine for yourself when the lazy function should be evaluated.

[tolmasky]

Yeah I suppose the hope is to have some sort of built in support for
either, since if not it will never work with other people's code (they
can't know that some internal value is an atom or lazy, whereas with the
lazy example I gave they don't need to know). Similarly in my own code I'd
have to check for .value/lazy everywhere I make an access, and thus
effectively break getin/etc. For example, if someone had implemented
oneMore(object, keypath) { return object.getIn(keyPath) + 1; }, this will
break with my circular structure : x= Map { a: 1, b: self }, oneMore(x,
[“b”,”b”,”b”,”b”,”a’]), but would work with built in support for lazies.

On Monday, December 22, 2014, Lee Byron [email protected] wrote:

There is no way (intentionally) for immutable persistent data structures
to contain circular references. Immutable structures can contain circular
references, but in order to be persistent and take advantage of structural
sharing, they need to be acyclic. The stack-overflow you link to
illustrates this well - showing how a double-linked list needs to make a
complete copy in order to perform an append operation.

There are some other problems that emerge from circular references in
values, such as deep equality checking and hash-value computation.

Languages based on immutable structures handle this in different ways:

Scala has lazy var which is pretty much what you wrote up here. A
deferred memoized function.

Clojure has atom which is a bit different (and easier to understand
IMHO). Atom is an atomically locked mutable wrapper. Since JavaScript is
single threaded, no locks are necessary so it's only a mutable wrapper. In
other words: { value: "foobar" }.

For equality and hashing, Atoms are treated as Objects not as Values. So {
value: "A" } !== { value: "A" }.

So you might treat this like:

var node0 = I.Map({ prev: null, next: {} })var node1 = I.Map({ prev: {value: node0}, next: {} })
node0.get('next').value = node1;var node2 = I.Map({ prev: {value: node1}, next: {} })
node1.get('next').value = node2;var node3 = I.Map({ prev: {value: node2}, next: null })
node2.get('next').value = node3;

---

However, both approaches: lazy function or atom object are totally fine!
This data structure library has no opinion on either, you just need to be
aware of their use so you can treat them appropriately:

// Lazy function
node3.get('prev').get();// Atom object
node3.get('prev').value;

—
Reply to this email directly or view it on GitHub
#259 (comment)
.

[leebyron]

I'll definitely considering adding true support for lazy values in the future, but I would prefer to see such a thing used outside the library first to better understand the implications before baking it in.

If you end up patching Immutable to add this functionality, I would be really interested in hearing about the unexpected issues and opportunities you run into.

[tolmasky]

So, interestingly enough, I was able to accomplish this using withMutations: https://gist.github.com/tolmasky/8a91af5ac1e0a949b423

Now the only issue is that toString borks and toJS bork (these are much easier to fix). Would you be opposed to having an implementation of toString and toJS that account for circular references (just like log you'd see something like Map { a: [Circular] }). I'm happy to just have them in my code of course, but given that this is "possible", I figured you might want it in mainline as well.

[tolmasky]

I've filed this related issue which deals with the same reference in objects (not necessarily circular): #305

[leebyron]

Circular references break a lot of promises that immutable data provides, so I don't think I plan on accounting for them.

You can read a more lengthy explanation of the issues with circular references via manual mutation written up in the "transients" section of the clojure documentation.

[leebyron]

Closing this for now - I think this is going to be really hard to do without language features.