How do I create a cyclic graph of immutable objects in Perl and Moose?

Question

This could seem like an obviously hopeless case, but is there a trick to create a cyclic graph of immutable objects in Perl? Something like this:

package Node;
use Moose;
has [qw/parent child/] => (is => 'ro', isa => 'Node');

package main;
my $a = Node->new;
my $b = Node->new(parent => $a);

Now if I wanted $a->child to point to $b, what can I do?

Answer 1

I'm still very new to Moose, but would a trigger work?

use Modern::Perl;

package Node;
use Moose;
has 'parent' => (
    is => 'ro',
    isa => 'Node',
    trigger => sub{
        my ($self, $parent) = @_;
        $parent->{child} = $self unless defined $parent->child;
    }
);

has 'child' => (
    is => 'ro',
    isa => 'Node',
    trigger => sub{
        my ($self, $child) = @_;
        $child->{parent} = $self unless defined $child->parent;
    }
);

package main;
my $p = Node->new;
my $c = Node->new(parent => $p);

say $p, ' == ', $c->parent;
say $c, ' == ', $p->child;

Answer 2

You could play games with lazy initialization:

package Node;
use Moose;

has parent => (
  is => 'ro',
  isa => 'Node',
  lazy => 1,
  init_arg => undef,
  builder => '_build_parent',
);

has _parent => (
  is => 'ro',
  init_arg => 'parent',
);

has child => (
  is => 'ro',
  isa => 'Node',
  lazy => 1,
  init_arg => undef,
  builder => '_build_child',
);

has _child => (
  is => 'ro',
  init_arg => 'child',
  predicate => undef,
);

has name => is => 'ro', isa => 'Str';

Generate the builders and predicates on the fly:

BEGIN {
  for (qw/ parent child /) {
    no strict 'refs';

    my $squirreled = "_" . $_;

    *{"_build" . $squirreled} = sub {
      my($self) = @_;
      my $proto = $self->$squirreled;
      ref $proto eq "REF" ? $$proto : $proto;
    };

    *{"has" . $squirreled} = sub {
      my($self) = @_;
      defined $self->$squirreled;
    };
  }
}

This allows

my $a = Node->new(parent => \my $b, name => "A");
   $b = Node->new(child  =>     $a, name => "B");

for ($a, $b) {
  print $_->name, ":\n";
  if ($_->has_parent) {
    print "  - parent: ", $_->parent->name, "\n";
  }
  elsif ($_->has_child) {
    print "  - child: ", $_->child->name, "\n";
  }
}

Its output is

A:
  - parent: B
B:
  - child: A

The code could be more elegant with η-conversion‎, but Moose won't pass parameters to builder methods.

Answer 3

I had to go and look at how really immutable languages do something like this, and I think the following is probably a reasonable attempt.

use 5.10.0;
{

    package Node;
    use Moose;
    has [qw(parent child)] => ( isa => 'Node', is => 'ro' );

    sub BUILD {
        my ( $self, $p ) = @_;
        return unless exists $p->{_child};
        my $child = Node->new( parent => $self, %{ delete $p->{_child} }, );
        $self->meta->get_attribute('child')->set_value( $self, $child );
    }
}

say Node->new( _child => {} )->dump

Basically instead of trying to build the objects separately, you have the parent auto-vivify the child based on passing in it's arguments. The output for this is, which is I believe the structure you were wanting.

$VAR1 = bless( {
                 'child' => bless( {
                                     'parent' => $VAR1
                                   }, 'Node' )
               }, 'Node' );