If you are happy to amend your delta to fit its structure then Struct::Diff offers a solution.

use strict;
use Test::More tests => 2;
use Storable qw(dclone);
use Struct::Diff qw/diff patch/;

my $orig =
  { a =>
    { b =>
      [ 'c', 'd' ],
      e =>
      [
       [ 'f' ]
      ]
    }
  };

my $new = dclone($orig);

my $delta = {
    D => {
        a => {
            D => {
                e => {
                    D => [
                        {   D => [
                                {   O => 'f',
                                    N => 'g'
                                }
                            ]
                        }
                    ]
                }
            }
        }
    }
};

patch ( $new, $delta );

my $augmented =
  { a =>
    { b =>
      [ 'c', 'd' ],
      e =>
      [
       [ 'g' ]
      ]
    }
  };

is_deeply( $new, $augmented, "augment" );

my $diff = diff( $orig, $new, noU => 1 );
is_deeply( $diff, $delta, "reduce" );
[download]

Just because it looked like it might be fun...

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11131585
use warnings;

my $orig = { a => { b => ["c", "d"], e => [["f"]] } };
use Data::Dump 'dd'; dd 'orig', $orig;

my $augment = { a => { b => [ 'c', 'd' ], e => [ [ 'g' ] ] } };
use Data::Dump 'dd'; dd 'augment', $augment;

my $delta = reduce( $orig, $augment );
use Data::Dump 'dd'; dd 'delta', $delta;

sub reduce
  {
  my %augment = map { $_ => '' } buildstatements( pop );
  delete @augment{ buildstatements( shift ) };
  eval join '', %augment for my $delta; # HAHAHAHAHAHA
  return $delta;
  }

my @buildcode;
sub buildstatements
  {
  @buildcode = ();
  creators( '$_->', shift() );
  return @buildcode;
  }

sub creators
  {
  my ($have, $ref) = @_;
  if( 'HASH' eq ref $ref )
    {
    creators( $have . "{$_}", $ref->{$_} ) for keys %$ref;
    }
  elsif( 'ARRAY' eq ref $ref )
    {
    creators( $have . "[$_]", $ref->[$_] ) for 0 .. $#$ref;
    }
  else { push @buildcode, qq($have = "$ref";); }
  }
[download]

Outputs:

("orig", { a => { b => ["c", "d"], e => [["f"]] } })
("augment", { a => { b => ["c", "d"], e => [["g"]] } })
("delta", { a => { e => [["g"]] } })
[download]

Hey, it passes all the provided test cases :)

• walk the "delta" structure bottom-up and
• delete the corresponding entries in the "augmented" structure by rules
• Rule1: delete simple scalars
• Rule2: delete only empty containers (hashes&arrays)

For Rule2 it's crucial that you walked bottom up. If there are childrens left after deleting all delta-childrens you can't be allowed to delete a container.

The walking can be done with a recursive function which does the deleting after recursing just before returning.

Hence all childrens at the "bottom" have already been processed.

HTH! :)

edit

FWIW: for augmenting you can use the same walker for the delta, just top-down.

I.e. you "augment" new elements just before recursing.

(actually thanks to auto-vivification this can be done more easily by only adding the leaves of the tree, but not much wrong with a clean symmetric algorithm? :)

The devil is -like so often - in the details for edge cases:
• What if an element is a scalar on one side and a container on the other?
• What if an element is in the delta but not in the augmented data?

Ignore? Warning? Exception and/or Dieing?

The combination of all error cases will make it hard to find a ready to use module whose customization is easier than a new implementation.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

My question originates from a large software project that has a complex configuration structure.

Something similar to:

# cfg1
$config =
  { "common" =>
      { debug => 1,
        logfile => "/var/log/project.log",
        path => "/opt/projects/bin",
      },
    "project_1" =>
      { name => "Project 1",
        tasks =>
          [ { name => "Prepare",
              program => "p1prep",
              arguments => [ "--init", '--default' ],
              logfile => "/var/log/p1prep.log",
            },
            { name => "Work",
              program => "p1",
              arguments => [ "--collect" ],
              logfile => "/var/log/p1.log",
              env =>
                { DISPLAY => undef,
                },
            },
            { name => "Wrapup",
              program => "signal",
              arguments => [ "p1", "finished" ],
            },
          ]
      },
    "project_2" =>
      { "and" => [ "so", "on", "..." ],
      },
  };
[download]

A particular customer could supply her own config, e.g.

# cfg2
$config =
  { "common" =>
      { debug => 0,
        logfile => "/var/log/project.log",
        path => "/opt/projects/bin",
      },
    "project_1" =>
      { name => "Project 1",
        tasks =>
          [ { name => "Prepare",
              program => "p1prep",
              arguments => [ "--init", '--default' ],
              logfile => "/var/log/p1prep.log",
            },
            { name => "Work",
              program => "p1",
              arguments => [ "--collect", "--brief" ],
              logfile => "/var/log/p1.log",
              env =>
                { DISPLAY => undef,
                },
            },
            { name => "Wrapup",
              program => "signal",
              arguments => [ "p1", "finished" ],
            },
          ]
      },
    "project_2" =>
      { "and" => [ "so", "on", "..." ],
      },
  };
[download]

But instead of supplying a full config, it suffices to supply a smaller set of modifications:

# cfgaug
$config =
  { "common" => { debug => 0 },
    "project_1" =>
      { tasks =>
          [ { name => "Prepare" },
            { name => "Work",
              arguments => [ "--collect", "--brief" ],
            },
            { name => "Wrapup" },
          ]
      },
  };
[download]

Applying #cfgaug to #cfg1 will result in #cfg2.

Since several of these augmentations are possible, the need arises to produce a single 'delta' that augments the base configuration #cfg1 to the actual state.

Test: I didn't get a notification in my message inbox for the former post and am trying to reproduce the problem ...

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

And if you want to take advantage of existing algorithms you could try convert your hash to N-ary Tree or cyclic Graph if you have loops and see if there are already existing algorithms to search for specific chains/branches. It will be challenging how you map an array and a hash to a branch of a tree, given they are ordered and un-ordered data. Perhaps sorting the hashes first. (just thinking out loud)

Edit: I took "augment" to mean "add/incorporate" (which it does) but it seems you want to modify, unless you want both (but this is not obvious from your test case). So the above is probably irrelevant.

bw, bliako

For some reason this comment reminded me of zippers in functional languages. I've forgotten the minimal amount I knew of them but it vaguely tickled some recollection.

The cake is a lie.
The cake is a lie.
The cake is a lie.

Fletch, it took me reading several sources on zippers to think that I got an idea of what they are (this seemed OK btw: https://scienceblogs.com/goodmath/2010/01/13/zippers-making-functional-upda)! Thanks for mentioning them. Caveat: but I had a hard time navigating out of the usual comp-science hot-air atmosphere.

bw, bliako