Data and Structure

Good news: many common data structures are internal to Perl.
- sets, searching, and hashes.
- lists, stacks, queues.
Bad news: certain more esoteric data structures aren't internal.
- graphs and digraphs.
- relations.
Many classical algorithms require one to change data representation in order to quickly execute the algorithm.
Perl's internal search algorithms are optimized for random, uniformly-distributed data. If you know more about your data distribution, you might do better than Perl in searching it.

Recall

If
```
package Foo;
sub bar { 
   ...
}
```
and (in any package) we have a variable
```
bless $cat,"Foo"; 
```
blessed into package Foo, then
- $cat->bar(@args) means &Foo::bar($cat,@args)
- bar Foo(@args) means &Foo::bar('Foo',@args).

To make use work for a package Foo, you need to place its code into a file Foo.pm with the following declarations:

 
package Foo; 
require Exporter; 
BEGIN {
   @Foo::ISA = qw(Exporter); 
   @Foo::EXPORT = qw(); 
   @Foo::EXPORT_OK = qw(); 
} 
#... code for Foo
1;

qw(thing thing2) is a shorthand for ('thing', 'thing2') ('quote words').
delete $thing->{'whatever'} removes a given element from a particular hash structure. One must provide a path to the element to be deleted.
Using these rules, let's craft some of the most common data structures.

One utility module: DD

Consider the code:

contents of perl_data/DD.pm...
#! /var/local/couch/bin/perl 

package DD; 
require Exporter; 
use Data::Dumper; 

BEGIN { 
   @DD::ISA = qw(Exporter); 
   @DD::EXPORT = qw(DD); 
   @DD::EXPORT_OK = qw(); 
} 

sub DD { 
    my $d = new Data::Dumper([@_]);
    $d->Indent(1); $d->Dump();
} 

1; 
...end of perl_data/DD.pm

This pretty-prints complex data in a more compact form than the default Data::Dumper.

Sequence-based structures

Stacks.
Queues.

Stacks

Consider the Perl module:

contents of perl_data/Stack.pm...
#! /var/local/couch/bin/perl 

package Stack; 
require Exporter;
use strict; 

BEGIN { 
    @Stack::ISA = qw(Exporter); 
    @Stack::EXPORT = qw(); 
    @Stack::EXPORT_OK = qw(); 
} 

sub new { 
    my $package = shift; 
    return bless [@_], $package; 
} 

sub push { 
    my $self = shift; 
    die "first argument is not a Stack" if ref $self ne 'Stack'; 
    push(@$self,@_); 
} 

sub pop { 
    my $self = shift; 
    die "first argument is not a Stack" if ref $self ne 'Stack'; 
    return pop(@$self); 
} 

sub empty { scalar(@{$_[0]})==0 } 

sub count { 
    my $self = shift; 
    die "first argument is not a Stack" if ref $self ne 'Stack'; 
    return scalar(@$self); 
} 

1; # must return this so 'use' works. 
...end of perl_data/Stack.pm

Call this with:

contents of perl_data/stack1.pl...
#! /var/local/couch/bin/perl 

use DD; 
use Stack; 
my $s = new Stack; 
$s->push(1); $s->push(2); $s->push(3); $s->push(4); 
print DD($s); 
while ($val = $s->pop()) { print "$val "; } 
print "\n"; 
...end of perl_data/stack1.pl

This prints

contents of perl_data/stack1.pl.out...
$VAR1 = bless( [
  1,
  2,
  3,
  4
], 'Stack' );
4 3 2 1 
...end of perl_data/stack1.pl.out

Queues

Consider the Perl module:

contents of perl_data/Queue.pm...
#! /var/local/couch/bin/perl 

package Queue; 
require Exporter;
use strict; 

BEGIN { 
    @Queue::ISA = qw(Exporter); 
    @Queue::EXPORT = qw(); 
    @Queue::EXPORT_OK = qw(); 
} 

sub new { 
    my $package = shift; 
    return bless [reverse @_], $package; 
} 

sub enqueue { # put stuff at the beginning 
    my $self = shift; 
    die "first argument is not a Queue" if ref $self ne 'Queue'; 
    unshift(@$self,@_); 
} 

sub dequeue { # remove from the top
    my $self = shift; 
    die "first argument is not a Queue" if ref $self ne 'Queue'; 
    die "Queue already empty" if $self->empty; 
    return pop(@$self); 
} 

sub empty { scalar(@{$_[0]}) == 0 } 

sub count { 
    my $self = shift; 
    die "first argument is not a Queue" if ref $self ne 'Queue'; 
    return scalar(@$self); 
} 

1; # must return this so 'use' works. 
...end of perl_data/Queue.pm

Call this with:

contents of perl_data/queue1.pl...
#! /var/local/couch/bin/perl 

use DD; 
use Queue; 
my $s = new Queue; 
$s->enqueue(1); $s->enqueue(2); $s->enqueue(3); $s->enqueue(4); 
print DD($s); 
while (!$s->empty && ($val = $s->dequeue())) { print "dequeue=$val\n"; } 
print "\n"; 
...end of perl_data/queue1.pl

This prints

contents of perl_data/queue1.pl.out...
$VAR1 = bless( [
  4,
  3,
  2,
  1
], 'Queue' );
dequeue=1
dequeue=2
dequeue=3
dequeue=4

...end of perl_data/queue1.pl.out

Why encapsulate?

Strong runtime typing of subroutine arguments.

e.g.,

contents of perl_data/queue2.pl...
#! /var/local/couch/bin/perl 

use DD; 
use Queue; 
use Stack; 
my $q = new Queue; 
&Stack::push($q,1); 
...end of perl_data/queue2.pl

prints

contents of perl_data/queue2.pl.out...
first argument is not a Stack at Stack.pm line 20.
...end of perl_data/queue2.pl.out

Automatic method bindings via short names, e.g., $s->push instead of $s->Stack::push.
Avoids messy expressions in accomplishing common things.
Automatic type-checking in complex object expressions (see below).

Some Data Structure Caveats

All modules are generic containers unless you override this behavior:

contents of perl_data/stack2.pl...
#! /var/local/couch/bin/perl 

use DD; 
use Stack; 
my $s = new Stack; 
$s->push([1,2,3]); $s->push({'a'=>'b'}); $s->push(3); $s->push('yo!'); 
print DD($s); 
while ($val = $s->pop()) { print DD($val); } 
print "\n"; 
...end of perl_data/stack2.pl

This prints

contents of perl_data/stack2.pl.out...
$VAR1 = bless( [
  [
    1,
    2,
    3
  ],
  {
    'a' => 'b'
  },
  3,
  'yo!'
], 'Stack' );
$VAR1 = 'yo!';
$VAR1 = 3;
$VAR1 = {
  'a' => 'b'
};
$VAR1 = [
  1,
  2,
  3
];

...end of perl_data/stack2.pl.out

Module instances can easily contain module instances.

contents of perl_data/queue3.pl...
#! /var/local/couch/bin/perl 

use DD; 
use Stack; 
use Queue; 
my $q = new Queue(1,2,3,4); 
my $s = new Stack(5,6,7,8); 
$q->enqueue($s); 
print DD($q); 
while (!$q->empty && ($val = $q->dequeue())) { print "dequeue=" . DD($val); } 
print "\n"; 
...end of perl_data/queue3.pl

This prints

contents of perl_data/queue3.pl.out...
$VAR1 = bless( [
  bless( [
    5,
    6,
    7,
    8
  ], 'Stack' ),
  4,
  3,
  2,
  1
], 'Queue' );
dequeue=$VAR1 = 1;
dequeue=$VAR1 = 2;
dequeue=$VAR1 = 3;
dequeue=$VAR1 = 4;
dequeue=$VAR1 = bless( [
  5,
  6,
  7,
  8
], 'Stack' );

...end of perl_data/queue3.pl.out

Search-dependent structures

Sets
Relations
Maps
Trees
Graphs

Sets

A set is implemented as a hash of keys, all of whose values are 1.

Consider:

contents of perl_data/Set.pm...
#! /var/local/couch/bin/perl 

package Set; 
require Exporter;
use strict; 

BEGIN { 
    @Set::ISA = qw(Exporter); 
    @Set::EXPORT = qw(union intersection difference); 
    @Set::EXPORT_OK = qw(); 
} 

# construct a new set from an array of values 
sub new { 
    my $package = shift; 
    my @values = @_; 
    my $result = bless {}; 
    $result->add(@values); 
    return $result; 
} 

# return 1 if an item is a member of a set. 
sub member { 
    my $self = shift; 
    my $item = shift; 
    die "member: first argument is not a set" if ref($self) ne 'Set'; 
    die "member: too many arguments" if @_!=0; 
    return $self->{$item}; 
} 

# return the contents of a set
sub contents { 
    my $self = shift; 
    return keys %$self; 
} 

# add elements to a set
sub add { 
    my $self = shift; 
    my @members = @_;
    die "add: first argument is not a set" if ref($self) ne 'Set'; 
    foreach my $m (@members) { $self->{$m} = 1; } 
} 

# remove elements from a set
sub remove { 
    my $self = shift; 
    my @members = @_;
    die "remove: first argument is not a set" if ref($self) ne 'Set'; 
    foreach my $m (@members) { delete $self->{$m}; } 
} 

# make a union of two sets that's independent from the operands
sub union { 
    my $self = shift; 
    my @others = @_; 
    die "union: first argument is not a set" if ref($self) ne 'Set'; 
    my $result = $self->copy;
    foreach my $o (@others) { 
	die "union: one argument is not a set" if ref($o) ne 'Set'; 
	$result->add($o->contents) ; 
    } 
    return $result; 
} 

# compute the intersection of n sets
sub intersection { 
    my $self = shift; 
    my @others = @_; 
    die "intersection: first argument is not a set" if ref($self) ne 'Set'; 
    my $result =  bless {}; 
loop: 
    foreach my $k ($self->contents) { 
        foreach my $o (@others) { 
	    die "intersection: one argument is not a set" if ref($o) ne 'Set'; 
	    next loop if ! $o->member($k); 
        } 
	$result->add($k); 
    } 
    return $result; 
} 

# compute set difference of two sets 
sub difference { 
    my $self = shift; 
    my $other = shift; 
    die "difference: first argument is not a set" if ref($self) ne 'Set'; 
    die "difference: second argument is not a set" if ref($other) ne 'Set'; 
    die "difference: only two argments allowed" if @_!=0; 
    my $result = $self->copy; 
    my ($key,$value); 
    while (($key,$value) = each %$other) { $result->remove($key); } 
    return $result; 
} 

# whether one set contains another
# $set->contains($set2) is 1 if $set contains $set2
sub contains { 
    my $self = shift; 
    my $other = shift; 
    die "contains: first argument is not a set" if ref($self) ne 'Set'; 
    die "contains: second argument is not a set" if ref($other) ne 'Set'; 
    die "contains: only two argments allowed" if @_!=0; 
    my ($key,$value); 
    while (($key,$value) = each %$other) { 
	return undef if ! $self->member($key); 
    } 
    return 1; 
} 

# $set->subsetOf($set2) is 1 if $set is a subset of $set2
sub subsetOf { 
    my $self = shift; 
    my $other = shift; 
    die "subsetOf: first argument is not a set" if ref($self) ne 'Set'; 
    die "subsetOf: second argument is not a set" if ref($other) ne 'Set'; 
    die "subsetOf: only two argments allowed" if @_!=0; 
    my ($key,$value); 
    while (($key,$value) = each %$self) { 
	return undef if ! $other->member($key); 
    } 
    return 1; 
} 

# determine whether two sets are equal
sub equal { 
    my $self = shift; 
    my $other = shift; 
    die "equal: first argument is not a set" if ref($self) ne 'Set'; 
    die "equal: second argument is not a set" if ref($other) ne 'Set'; 
    die "equal: only two argments allowed" if @_!=0; 
    return ($self ->subsetOf($other) 
         && $other->subsetOf($self )); 
} 

# count distinct members of a set
sub count { 
    my $self = shift; 
    die "count: first argument is not a set" if ref($self) ne 'Set'; 
    return scalar(keys %$self); 
} 

# make an exact but independent copy of a set
sub copy { 
    my $self = shift; 
    die "copy: first argument is not a set" if ref($self) ne 'Set'; 
    return bless { %$self } ; 
} 

1; # must return this so 'use' works. 
...end of perl_data/Set.pm

And let's use this module:

contents of perl_data/set2.pl...
#! /var/local/couch/bin/perl 

use Set; 

my $set = new Set('jack','mimi','joe'); 
if ($set->member('jack')) { 
    print "jack is in the set\n"; 
} else { 
    print "jack is not in the set\n"; 
} 

if ($set->member('alice')) { 
    print "alice is in the set\n"; 
} else { 
    print "alice is not in the set\n"; 
} 
...end of perl_data/set2.pl

This prints:

contents of perl_data/set2.pl.out...
jack is in the set
alice is not in the set
...end of perl_data/set2.pl.out

Set operations:
- $s1 = new Set;
- $s1->union($s2); computes union of $s1 and $s2, does not change $s1 or $s2.
- $s1->intersection($s2); computes intersection of $s1 and $s2.
- $s1->subsetOf($s2); returns 1 if $s1 is a subset of $s2.
- $s1->contains($s2); returns 1 if $s1 contains $s2.
- $s1->member($m); returns 1 if $m is a member of $s1.
- $s1->add($m); adds a member to $s1.
- $s1->remove($m); removes a member from $s1.
- $s1->count returns a count of the distinct elements in $s1.

Weird: can make a set of references!

contents of perl_data/set3.pl...
#! /var/local/couch/bin/perl 

use Set; 
use DD; 

my $set = new Set('jack','mimi','joe'); 
$set->add({'a'=>'b'}); 
my $a = [1,2,3]; 
$set->add($a); 
print DD($set); 

# membership in the set means having the exact same pointer
# (reference) value...
if ($set->member($a)) { 
    print "a's value is in the set\n"; 
} else { 
    print "a's value is not in the set\n"; 
} 

# a different reference to an array with the same value
# is NOT in the set...
if ($set->member([1,2,3])) { 
    print "\[1,2,3\] is in the set\n"; 
} else { 
    print "\[1,2,3\] is not in the set\n"; 
} 
...end of perl_data/set3.pl

This prints:

contents of perl_data/set3.pl.out...
$VAR1 = bless( {
  'jack' => 1,
  'joe' => 1,
  'ARRAY(0x810b9f0)' => 1,
  'mimi' => 1,
  'HASH(0x810b9f0)' => 1
}, 'Set' );
a's value is in the set
[1,2,3] is not in the set
...end of perl_data/set3.pl.out

Warning: references are different unless they point to the exact same structure. This is the same thing as being eq in Lisp, e.g.

Relations

A relation is a set of ordered tuples of data.
Typical relation: is-before in topological sort.
Relations contain both ordered and unordered components.
- ordered: tuple element order.
- unordered: set of tuples themselves.

Relation membership

Combine ordered and unordered components.
Ordered component: the tuples themselves.
Unordered component: hash tables represent tuples.

Consider:

contents of perl_data/Tuples.pm...
#! /var/local/couch/bin/perl 

package Tuples; 

require Exporter; 
use Data::Dumper; 
use strict; 

BEGIN { 
    @Tuples::ISA=qw(Exporter); 
    @Tuples::EXPORT=qw(); 
    @Tuples::EXPORT_OK=qw(); 
} 

# create a new tuple space
sub new { 
    my $pack = shift; 
    my $tuples = shift; 
    my $self = bless {}; 
    foreach my $t (@$tuples) { $self->add($t); } 
    return $self; 
} 

# check for membership in the tuple space
sub member { 
    my $self = shift; 
    my $element = shift; 
    my $temp = $self; 
    foreach my $e (@$element) { 
	return undef if ! defined $temp->{$e}; 
	$temp=$temp->{$e}; 
    } 
    return defined $temp; 
} 

# add a tuple to the structure
sub add { 
    my $self = shift; 
    my $tuple = shift; 
    my $temp = $self; 
    for (my $i=0; $i<@$tuple; $i++) { 
	my $s = $tuple->[$i]; 
	$temp->{$s} = bless {} if ! defined $temp->{$s}; 
	$temp=$temp->{$s}; 
    } 
} 

# delete a tuple from the structure 
sub del { 
    my $self = shift; 
    my $tuple = shift; 
    return if ref($self) ne 'Tuples'; 
    return if ! defined $tuple->[0]; 
    return if ! defined $self->{$tuple->[0]} ; 
    my $newtuple = [ @$tuple[1..$#$tuple] ]; 
    $self->{$tuple->[0]}->del($newtuple); 
    delete $self->{$tuple->[0]} if scalar(%{$self->{$tuple->[0]}})==0; 
} 

# generate a contents list for a tuple space
sub contents { 
    my $self = shift; 
    return undef if ref $self ne 'Tuples'; 
    return undef if scalar(%$self) == 0; 
    my $out = []; 
    my @keys = keys %$self; 
    foreach my $k (@keys) { 
	my $result = $self->{$k}->contents; 
	if (defined $result) { 
	    my $res2; 
	    foreach my $r (@$result) { 
		push(@$res2,[$k,@$r]); 
	    } 
	    $result = $res2; 
	} else { 
	    $result = [[$k]]; 
	} 
	push(@$out,(@$result)); 
    } 
    return $out; 
} 

1; 
...end of perl_data/Tuples.pm

Call this using:

contents of perl_data/tuples.pl...
#! /var/local/couch/bin/perl 

use Tuples; 
use DD; 

$tuples = [ 
  [  1, 3, 7 ], 
  [  2, 1, 5 ], 
  [  2, 1, 5 ], 
  [  2, 1, 1 ], 
  [ 11,14,64 ]
]; 


$d = new Tuples($tuples); 
print "d=" . DD($d); 
print "d->contents=" . DD($d->contents); 
if ( $d->member([2,1,1]) ) { 
    print "[2,1,1] is a member of d\n"; 
} else { 
    print "[2,1,1] is not a member of d\n"; 
} 
if ( $d->member([2,2,2]) ) { 
    print "[2,2,2] is a member of d\n"; 
} else { 
    print "[2,2,2] is not a member of d\n"; 
} 

$d->del([2,1,1]); 
$d->add(['frank','george','carol']); 
$d->del([2,1,5]); 
print "d=" . DD($d); 
print "d->contents=" . DD($d->contents); 
...end of perl_data/tuples.pl

This prints:

contents of perl_data/tuples.pl.out...
d=$VAR1 = bless( {
  '11' => bless( {
    '14' => bless( {
      '64' => bless( {}, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' ),
  '1' => bless( {
    '3' => bless( {
      '7' => bless( {}, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' ),
  '2' => bless( {
    '1' => bless( {
      '1' => bless( {}, 'Tuples' ),
      '5' => bless( {}, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' )
}, 'Tuples' );
d->contents=$VAR1 = [
  [
    '11',
    '14',
    '64'
  ],
  [
    '1',
    '3',
    '7'
  ],
  [
    '2',
    '1',
    '1'
  ],
  [
    '2',
    '1',
    '5'
  ]
];
[2,1,1] is a member of d
[2,2,2] is not a member of d
d=$VAR1 = bless( {
  '11' => bless( {
    '14' => bless( {
      '64' => bless( {}, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' ),
  '1' => bless( {
    '3' => bless( {
      '7' => bless( {}, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' ),
  'frank' => bless( {
    'george' => bless( {
      'carol' => bless( {}, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' )
}, 'Tuples' );
d->contents=$VAR1 = [
  [
    '11',
    '14',
    '64'
  ],
  [
    '1',
    '3',
    '7'
  ],
  [
    'frank',
    'george',
    'carol'
  ]
];
...end of perl_data/tuples.pl.out

Extreme power of Tuples module

Can search for a particular tuple in O(tuple size).

Tuples can be different lengths! Consider:

contents of perl_data/tuples2.pl...
#! /var/local/couch/bin/perl 

use Tuples; 
use DD; 

$tuples = [ 
  [  1, 3, 7 ], 
  [  2, 1, 5, 7 ], 
  [  2, 1, 1, 4, 9 ], 
]; 


$d = new Tuples($tuples); 
print "d=" . DD($d); 
print "d->contents=" . DD($d->contents); 
if ( $d->member([2,1,5]) ) { 
    print "[2,1,5] is a prefix of a member of d\n"; 
} else { 
    print "[2,1,5] is not a prefix of a member of d\n"; 
} 
if ( $d->member([2,2]) ) { 
    print "[2,2] is a prefix of a member of d\n"; 
} else { 
    print "[2,2] is not a prefix of a member of d\n"; 
} 

print "d->contents=" . DD($d->contents); 
$d->add(['frank','george','carol']); 
print "d->contents=" . DD($d->contents); 
$d->del([2,1,5]); 
print "d->contents=" . DD($d->contents); 
$d->del([2,1,5,7]); 
print "d->contents=" . DD($d->contents); 
...end of perl_data/tuples2.pl

This prints:

contents of perl_data/tuples2.pl.out...
d=$VAR1 = bless( {
  '1' => bless( {
    '3' => bless( {
      '7' => bless( {}, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' ),
  '2' => bless( {
    '1' => bless( {
      '1' => bless( {
        '4' => bless( {
          '9' => bless( {}, 'Tuples' )
        }, 'Tuples' )
      }, 'Tuples' ),
      '5' => bless( {
        '7' => bless( {}, 'Tuples' )
      }, 'Tuples' )
    }, 'Tuples' )
  }, 'Tuples' )
}, 'Tuples' );
d->contents=$VAR1 = [
  [
    '1',
    '3',
    '7'
  ],
  [
    '2',
    '1',
    '1',
    '4',
    '9'
  ],
  [
    '2',
    '1',
    '5',
    '7'
  ]
];
[2,1,5] is a prefix of a member of d
[2,2] is not a prefix of a member of d
d->contents=$VAR1 = [
  [
    '1',
    '3',
    '7'
  ],
  [
    '2',
    '1',
    '1',
    '4',
    '9'
  ],
  [
    '2',
    '1',
    '5',
    '7'
  ]
];
d->contents=$VAR1 = [
  [
    '1',
    '3',
    '7'
  ],
  [
    'frank',
    'george',
    'carol'
  ],
  [
    '2',
    '1',
    '1',
    '4',
    '9'
  ],
  [
    '2',
    '1',
    '5',
    '7'
  ]
];
d->contents=$VAR1 = [
  [
    '1',
    '3',
    '7'
  ],
  [
    'frank',
    'george',
    'carol'
  ],
  [
    '2',
    '1',
    '1',
    '4',
    '9'
  ],
  [
    '2',
    '1',
    '5',
    '7'
  ]
];
d->contents=$VAR1 = [
  [
    '1',
    '3',
    '7'
  ],
  [
    'frank',
    'george',
    'carol'
  ],
  [
    '2',
    '1',
    '1',
    '4',
    '9'
  ]
];
...end of perl_data/tuples2.pl.out

It was possible to determine whether a prefix of a tuple was represented in the list.
One must, however, delete the whole tuple rather than the prefix.

Whoa there!

Every Perl data structure has implicit preconditions that must be true for the data structure to work properly. For Tuples.pm to work:
Tuple elements must be true scalars (strings or numbers).
Tuple elements can't be references.
In all of the above, there are hidden conditions that make the appropriate structure work properly!
We need to be a lot more precise in order to know exactly what we're doing!

Maps

A map is like a tuple, except that it describes a one-way dependency between its first argument and its second.
This is essentially a hash table.

A problem of language

Perl admits a new kind of programming based upon flexibility of representation and transformation of structure.
It is often more appropriate to transform a structure before operating upon it than to work on it untransformed.
We lack the language to discuss this methodology precisely.
I thus borrow some language from group theory that expresses the appropriate ideas:
- bijective maps
- homomorphisms and isomorphisms
to clarify our thinking and clearly express what's going on.

Bijective mappings

Many Perl tricks rely upon bijective mappings between differing data spaces. For a map (function) f:D->R:
D: domain of mapping f.
R: range of mapping f.
For d in D, f(d) is in R.
f is bijective if and only if (iff) it is both one-one and onto.
f is one-one: if f(a) is equal to f(b), this implies that a is equal to b.
f is onto: for each b in the range R of f, there is an d in D so that f(d) is equal to b.
Bijective maps are invertible: given b in R, it is possible to find d in D so that f(d) is b. This mapping f^-1:R->D is called the inverse of f.

Properties of bijections

The composition of bijections is a bijection. If f:D->E and g:E->F are bijections, then g^.f:D->F defined by g^.f(d) = g(f(d)) is also a bijection.
The inverse of a composition g^.f is (g^.f)^-1 which is f^-1^.g^-1.

Some notes on bijection

It is often important to control the domain and range of a mapping in order to assure a bijection. If
```
 
sub f { join(','), @_} 
```
and
```
 
sub g { split (',',shift) } 
```
then these are inverses -- and f is a bijection -- only if the domain of f is arrays of strings not containing ','! Otherwise, we have a failure of bijection: g(f('this,really','was,a','mistake')) is ('this','really','was','a','mistake'), so that there is one element e so that g(f(e)) isn't e.
Seemingly different values in a domain or range may be equivalent in some sense, and a bijection may be valid only for equivalence classes of items within the domain and range. E.g., suppose that (1,2,6) represents a set. We know that in a set, order isn't important. Thus we know that (6,1,2) is the same set. Thus:
```
sub f { 
    my $out = {}; 
    foreach (@_) { $out->{$_}=1; } 
    return $out; 
} 
sub g { 
    my $in = shift; 
    return keys %$in; 
} 
```
are inverses relative to the equivalence between lists representing different sets.
In mathematical notation, we'd notate this as f:D/E->R, where D is the set of all lists, E is the set of equivalence classes of D (as sets), and R is the set of all single-level hashes with string keys. E is a set of sets of "equivalent" elements of D, e.g., one element of E in this case might be
```
{ (1,2,3), (2,3,1), (3,1,2), (3,2,1), (2,1,3), (1,3,2) } 
```
It is not necessary to be able to construct E in order to think about it; one need merely define the nature of the equivalence.
A typical mapping is made bijective by controlling both its domain and range, as well as considering elements in both the domain and range equivalent according to some equivalence relationships. I.e. f:D/E -> R/S is a mapping from D (where elements in an equivalence class e in E are considered identical) to R (where elements in an equivalence class s in S are considered identical).

The mapping game

For a particular operation, some structures are faster than others.
Two data structures (representations) are equivalent if there is a bijection between them, so that one can flexibly choose one representation or the other for the data.
Operations work faster on some structures than on others.
It is often appropriate to convert your data to an equivalent representation.
Conversion is a win if the time for conversion T_C plus operation time after conversion T_OC is less than operation time before conversion T_O:
```
 T_O > T_C+T_OC
```
Bijection is the strongest form of equivalence. It means that if you have either side of the bijection, you can reconstruct the other.
In other words, bijections are lossless, in the sense that each side embodies everything about the other.

Some common ways to form bijections

If f:D->R is one-one, and f(D)={f(d)|d in D} then f:D->f(D) is a bijection by limitation of range. Suppose D is the set of tuples containing two numbers between 0 and 9. We know that
```
sub f { shift + 10*shift } 
```
uniquely maps these tuples to the numbers between 0 and 99 (by the base theorem, also known as the "fundamental theorem of arithmetic"), so that f is a bijection from {0..9}X{0..9} -> {0..99} .
Another trick in forming bijections is to use induced equivalence. If we know the equivalence relationship on one side of a one-one map, we can posit the existence of a matching equivalence relationship on the other side of the map (in either direction).

Some common bijective operations

Mapping an array to and from a hash:

Domain: all lists of atoms (strings or numbers) in which no string or number appears twice.
Domain equivalence: none.
Range: hashes of atoms, where the value of a hash is the offset of that value in the corresponding array or undef.
Range equivalence: none.

Consider the code:

contents of perl_data/ArrayHash.pm...
#! /var/local/couch/bin/perl 

package ArrayHash; 

use Data::Dumper; 
require Exporter; 

BEGIN { 
    @ArrayHash::ISA = qw(Exporter); 
    @ArrayHash::EXPORT = qw(array2hash hash2array); 
    @ArrayHash::EXPORT_OK = qw(); 
} 

sub array2hash { 
    my $hash = {}; 
    for (my $i=0; $i<@_; $i++) { $hash->{$_[$i]}=$i; }  
    return $hash; 
} 

sub hash2array { 
    my $hash = shift; 
    return sort {$hash->{$a}<=>$hash->{b}} keys %$hash; 
} 

1; 
...end of perl_data/ArrayHash.pm

and call it via:

contents of perl_data/array2hash.pl...
#! /var/local/couch/bin/perl 

use DD; 
use ArrayHash; 

my @array = ('cat','dog','house','bird','horse'); 
print "array=" . DD(\@array); 

my $hash = array2hash(@array); 
print "hash=" . DD($hash); 

my @a2 = &hash2array($hash); 
print "a2=" . DD(\@a2); 
...end of perl_data/array2hash.pl

This prints:

contents of perl_data/array2hash.pl.out...
array=$VAR1 = [
  'cat',
  'dog',
  'house',
  'bird',
  'horse'
];
hash=$VAR1 = {
  'house' => 2,
  'cat' => 0,
  'dog' => 1,
  'horse' => 4,
  'bird' => 3
};
a2=$VAR1 = [
  'cat',
  'house',
  'horse',
  'dog',
  'bird'
];
...end of perl_data/array2hash.pl.out

Mapping an array to and from a hash (with duplicate elements)

Domain: all lists of atoms (strings or numbers).
Range: all hashes of atoms in which the hash value is a hash of array positions at which the value appears in the array representation.

Consider the code:

contents of perl_data/ArrayHash2.pm...
#! /var/local/couch/bin/perl 

package ArrayHash2; 

use Data::Dumper; 
require Exporter; 
use strict; 

BEGIN { 
    @ArrayHash2::ISA = qw(Exporter); 
    @ArrayHash2::EXPORT = qw(array2hash2 hash2array2); 
    @ArrayHash2::EXPORT_OK = qw(); 
} 

sub array2hash2 { 
    my $in = shift; 
    my $hash = {}; 
    for (my $i=0; $i<@$in; $i++) { $hash->{$in->[$i]}->{$i}=1; }  
    return $hash; 
} 

sub hash2array2 { 
    my $hash = shift; 
    my $out=[]; 
    foreach my $firstKey (keys %$hash) { 
	foreach my $secondKey (keys %$firstKey) { 
	    $out->[$secondKey] = $firstKey; 
	} 
    } 
} 

1; 

...end of perl_data/ArrayHash2.pm

Call this with:

contents of perl_data/array2hash2.pl...
#! /var/local/couch/bin/perl 

use DD; 
use ArrayHash2; 

# define an array
my $array = ['cat','dog','house','bird','cat','horse']; 
print "array=" . DD($array); 

# code array as a hash
my $hash = array2hash2($array); 
print "hash=" . DD($hash); 

# hash back to array
my $a2 = hash2array2($hash);
print "a2=" . DD($array); 
...end of perl_data/array2hash2.pl

This prints:

contents of perl_data/array2hash2.pl.out...
array=$VAR1 = [
  'cat',
  'dog',
  'house',
  'bird',
  'cat',
  'horse'
];
hash=$VAR1 = {
  'house' => {
    '2' => 1
  },
  'cat' => {
    '4' => 1,
    '0' => 1
  },
  'dog' => {
    '1' => 1
  },
  'horse' => {
    '5' => 1
  },
  'bird' => {
    '3' => 1
  }
};
a2=$VAR1 = [
  'cat',
  'dog',
  'house',
  'bird',
  'cat',
  'horse'
];
...end of perl_data/array2hash2.pl.out

Mapping an array of tuples (a relation) to and from a hash

Domain: arrays of tuples with unique first elements.
Range: hashes from first element to array consisting of tuple position and value.

Consider the code:

contents of perl_data/TupleIndex.pm...
#! /var/local/couch/bin/perl 

package TupleIndex; 
use Data::Dumper; 
require Exporter; 

BEGIN { 
    @TupleIndex::ISA = qw(Exporter); 
    @TupleIndex::EXPORT = qw(tuple2index index2tuple); 
    @TupleIndex::EXPORT_OK = qw(); 
} 

sub tuple2index { 
   my $array = shift; 
   my $hash = {}; 
   for (my $i=0; $i<@$array; $i++) { 
	$hash->{$array->[$i]->[0]}=[$i,$array->[$i]]; 
   }  
   return $hash; 
} 
   
sub index2tuple { 
    my $hash = shift; 
    return [ sort {$hash->{$a}->[0]<=>$hash->{b}->[0]} keys %$hash ]; 
} 

1; 
...end of perl_data/TupleIndex.pm

Call this using:

contents of perl_data/tuple2index.pl...
#! /var/local/couch/bin/perl 

use DD; 
use TupleIndex; 

my $array = [['cat',2],['dog',5],['house',19],['bird',25],['horse',41]]; 
print "array=" . DD($array); 

my $hash = &tuple2index($array); 
print "hash=" . DD($hash); 

my $a2 = &index2tuple($hash); 
print "a2=" . DD($array); 
...end of perl_data/tuple2index.pl

This prints:

contents of perl_data/tuple2index.pl.out...
array=$VAR1 = [
  [
    'cat',
    2
  ],
  [
    'dog',
    5
  ],
  [
    'house',
    19
  ],
  [
    'bird',
    25
  ],
  [
    'horse',
    41
  ]
];
hash=$VAR1 = {
  'house' => [
    2,
    [
      'house',
      19
    ]
  ],
  'cat' => [
    0,
    [
      'cat',
      2
    ]
  ],
  'dog' => [
    1,
    [
      'dog',
      5
    ]
  ],
  'horse' => [
    4,
    [
      'horse',
      41
    ]
  ],
  'bird' => [
    3,
    [
      'bird',
      25
    ]
  ]
};
a2=$VAR1 = [
  [
    'cat',
    2
  ],
  [
    'dog',
    5
  ],
  [
    'house',
    19
  ],
  [
    'bird',
    25
  ],
  [
    'horse',
    41
  ]
];
...end of perl_data/tuple2index.pl.out

Mapping an array of tuples (a relation) to and from a hash (with duplicate keys)

Domain: all arrays of tuples of atoms (numbers and strings).
Range: hash of first tuple value to an array of tuple descriptors for tuples having that value.

Consider the code:

contents of perl_data/TupleIndex2.pm...
#! /var/local/couch/bin/perl 

package TupleIndex2; 
use Data::Dumper; 
require Exporter; 
use strict; 

BEGIN { 
    @TupleIndex2::ISA = qw(Exporter); 
    @TupleIndex2::EXPORT = qw(tuple2index2 index2tuple2); 
    @TupleIndex2::EXPORT_OK = qw(); 
} 

sub tuple2index2 { 
   my $array = shift; 
   my $hash = {}; 
   for (my $i=0; $i<@$array; $i++) { 
	push(@{$hash->{$array->[$i]->[0]}},[$i,$array->[$i]]); 
   }  
   return $hash; 
} 
   
sub index2tuple2 { 
    my $hash = shift; 
    my $array = []; 
    for my $firstKey (keys %$hash) { 
	foreach my $secondKey (@$firstKey) { 
	    $array->[$secondKey->[0]] = $secondKey->[1]; 
	} 
    } 
    return $array; 
} 

1; 
...end of perl_data/TupleIndex2.pm

Call this using:

contents of perl_data/tuple2index2.pl...
#! /var/local/couch/bin/perl 

use TupleIndex2; 
use DD; 
my $array = [['cat',2],['dog',5],['house',19],['dog',25],['house',41]]; 
print "array=" . DD($array); 

my $hash = &tuple2index2($array); 
print "hash=" . DD($hash); 

my $a2 = &index2tuple2($hash); 
print "a2=" . DD($array); 
...end of perl_data/tuple2index2.pl

This prints:

contents of perl_data/tuple2hash2.pl.out...
array=$VAR1 = [
  [
    'cat',
    2
  ],
  [
    'dog',
    5
  ],
  [
    'house',
    19
  ],
  [
    'dog',
    25
  ],
  [
    'house',
    41
  ]
];
hash=$VAR1 = {
  'house' => [
    [
      2,
      [
        'house',
        19
      ]
    ],
    [
      4,
      [
        'house',
        41
      ]
    ]
  ],
  'cat' => [
    [
      0,
      [
        'cat',
        2
      ]
    ]
  ],
  'dog' => [
    [
      1,
      [
        'dog',
        5
      ]
    ],
    [
      3,
      [
        'dog',
        25
      ]
    ]
  ]
};
a2=$VAR1 = [
  [
    'cat',
    2
  ],
  [
    'dog',
    5
  ],
  [
    'house',
    19
  ],
  [
    'dog',
    25
  ],
  [
    'house',
    41
  ]
];
...end of perl_data/tuple2hash2.pl.out

Making a cross-reference table for a tuplespace:

contents of perl_data/xref.pl...
#! /var/local/couch/bin/perl 

use DD; 
my $array = [['cat',2],['dog',5],['house',19],['dog',25],['house',41]]; 
print "array=" . DD($array); 

my $hash = {}; 
for (my $i=0; $i<@$array; $i++) { 
    push(@{$hash->{'byname'}->{$array->[$i]->[0]}},$array->[$i]); 
    push(@{$hash->{'bynumber'}->{$array->[$i]->[1]}},$array->[$i]); 
}  
print "hash=" . DD($hash); 
...end of perl_data/xref.pl

This prints:

contents of perl_data/xref.pl.out...
array=$VAR1 = [
  [
    'cat',
    2
  ],
  [
    'dog',
    5
  ],
  [
    'house',
    19
  ],
  [
    'dog',
    25
  ],
  [
    'house',
    41
  ]
];
hash=$VAR1 = {
  'bynumber' => {
    '25' => [
      [
        'dog',
        25
      ]
    ],
    '19' => [
      [
        'house',
        19
      ]
    ],
    '41' => [
      [
        'house',
        41
      ]
    ],
    '2' => [
      [
        'cat',
        2
      ]
    ],
    '5' => [
      [
        'dog',
        5
      ]
    ]
  },
  'byname' => {
    'house' => [
      $VAR1->{'bynumber'}{'19'}[0],
      $VAR1->{'bynumber'}{'41'}[0]
    ],
    'cat' => [
      $VAR1->{'bynumber'}{'2'}[0]
    ],
    'dog' => [
      $VAR1->{'bynumber'}{'5'}[0],
      $VAR1->{'bynumber'}{'25'}[0]
    ]
  }
};
...end of perl_data/xref.pl.out

Exploiting bijection: searching for a structure

Problem: search for a specific structure in a large set of possible (unconstrained) structures.

Step 1: create a bijection between possible structures and text strings using Data::Dumper.

contents of perl_data/TextRef.pm...
#! /var/local/couch/bin/perl 

package TextRef; 

require Exporter; 
use Data::Dumper; 

BEGIN { 
    @TextRef::ISA = qw(Exporter);
    @TextRef::EXPORT = qw(ref2text text2ref); 
    @TextRef::EXPORT_OK = qw(); 
} 


sub ref2text { 
    my $ref = shift; 
    my $d = new Data::Dumper([$ref]); 
    $d->Indent(0); 
    $d->Dump; 
} 

sub text2ref { eval shift; } 

1; 
 
...end of perl_data/TextRef.pm

Call this using:

contents of perl_data/TextRef.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use TextRef; 

my $str = bless { 'a'=>'b', 'c'=>'d'},'Foo'; 
print Dumper($str); 
my $txt = ref2text($str); 
print "txt=$txt\n"; 
my $st2 = text2ref($txt); 
print Dumper($st2); 
...end of perl_data/TextRef.pl

This prints:

contents of perl_data/TextRef.pl.out...
$VAR1 = bless( {
                 'c' => 'd',
                 'a' => 'b'
               }, 'Foo' );
txt=$VAR1 = bless( {'c' => 'd','a' => 'b'}, 'Foo' );
$VAR1 = bless( {
                 'c' => 'd',
                 'a' => 'b'
               }, 'Foo' );
...end of perl_data/TextRef.pl.out

Step 2: create a bijection between a subset of text strings and tuples of atoms. Consider:

contents of perl_data/TupleRef.pm...
#! /var/local/couch/bin/perl 

package TupleRef; 

require Exporter; 
use Data::Dumper; 
use strict; 

BEGIN { 
    @TupleRef::ISA = qw(Exporter);
    @TupleRef::EXPORT = qw(ref2tuple tuple2ref); 
    @TupleRef::EXPORT_OK = qw(); 
} 

sub ref2tuple { 
    my $ref = shift; 
    my $d = new Data::Dumper([$ref]); 
    $d->Indent(0); 
    my $string = $d->Dump; 
    $string =~ s/{/'__OPBRACE__',/g; 
    $string =~ s/}/,'__CLBRACE__'/g; 
    $string =~ s/\[/'__OPBRACK__',/g; 
    $string =~ s/\]/,'__CLBRACK__'/g; 
    $string =~ s/bless\(/'bless','__OPPAREN__',/g; 
    $string =~ s/\(/'__OPPAREN__',/g; 
    $string =~ s/\)/,'__CLPAREN__'/g; 
    $string =~ s/^\$VAR1 = //g;
    $string =~ s/;$//; 
    eval "[ $string ]"; 
} 

sub tuple2ref { 
    my $tuple = shift; 
    my $d = new Data::Dumper([$tuple]); 
    $d->Indent(0); 
    my $string = $d->Dump; 
    $string =~ s/^\$VAR1 = \[//; 
    $string =~ s/\];$/;/; 
    $string =~ s/'__OPBRACE__',/{/g; 
    $string =~ s/,'__CLBRACE__'/}/g; 
    $string =~ s/'__OPBRACK__',/\[/g; 
    $string =~ s/,'__CLBRACK__'/\]/g; 
    $string =~ s/'bless','__OPPAREN__',/bless\(/g; 
    $string =~ s/'__OPPAREN__',/\(/g; 
    $string =~ s/,'__CLPAREN__'/\)/g; 
# print "string=$string\n"; 
    eval $string; 
} 

1; 
...end of perl_data/TupleRef.pm

And call this using:

contents of perl_data/TupleRef.pl...
#! /var/local/couch/bin/perl 

use DD; 
use TupleRef; 

$test = [
  [1,2,3], 
  (bless ['a','b'],'Foo'), 
  (bless { 'c'=>'d', 'e'=>'f' }, 'Bar')
]; 
print DD($test); 
$tup = ref2tuple($test); 
print DD($tup); 
my $out = tuple2ref($tup); 
print DD($out); 
if (DD($test) eq DD($out)) { 
    print "test succeeded\n"; 
} else { 
    print "test failed\n"; 
} 
...end of perl_data/TupleRef.pl

This prints:

contents of perl_data/TupleRef.pl.out...
$VAR1 = [
  [
    1,
    2,
    3
  ],
  bless( [
    'a',
    'b'
  ], 'Foo' ),
  bless( {
    'e' => 'f',
    'c' => 'd'
  }, 'Bar' )
];
$VAR1 = [
  '__OPBRACK__',
  '__OPBRACK__',
  1,
  2,
  3,
  '__CLBRACK__',
  'bless',
  '__OPPAREN__',
  '__OPBRACK__',
  'a',
  'b',
  '__CLBRACK__',
  'Foo',
  '__CLPAREN__',
  'bless',
  '__OPPAREN__',
  '__OPBRACE__',
  'e',
  'f',
  'c',
  'd',
  '__CLBRACE__',
  'Bar',
  '__CLPAREN__',
  '__CLBRACK__'
];
$VAR1 = [
  [
    1,
    2,
    3
  ],
  bless( [
    'a',
    'b'
  ], 'Foo' ),
  bless( {
    'e' => 'f',
    'c' => 'd'
  }, 'Bar' )
];
test succeeded
...end of perl_data/TupleRef.pl.out

Step 3: Utilize the pattern in the Tuples module to encode these tuples into an appropriate search structure for structures. Consider:

contents of perl_data/Stuples.pm...
#! /var/local/couch/bin/perl 

package Stuples; 
use TupleRef; 
use Data::Dumper; 
use strict; 

require Exporter; 

BEGIN { 
     @Stuples::ISA = qw(Exporter Tuples); 
     @Stuples::EXPORT = qw(); 
     @Stuples::EXPORT_OK = qw(); 
} 

# create a new tuple space
sub new { 
    my $pack = shift; 
    my $tuples = shift; 
    my $self = bless {}; 
    foreach my $t (@$tuples) { $self->add($t); } 
    return $self; 
} 

# check for membership in the tuple space
sub member { 
    my $self = shift; 
    my $element = &ref2tuple(shift); 
    my $temp = $self; 
    foreach my $e (@$element) { 
	return undef if ! defined $temp->{$e}; 
	$temp=$temp->{$e}; 
    } 
    return defined $temp; 
} 

# add a tuple to the structure
sub add { 
    my $self = shift; 
    my $tuple = ref2tuple(shift); 
    my $temp = $self; 
    for (my $i=0; $i<@$tuple; $i++) { 
	my $s = $tuple->[$i]; 
	$temp->{$s} = bless {} if ! defined $temp->{$s}; 
	$temp=$temp->{$s}; 
    } 
} 

# delete a tuple from the structure 
sub del { 
    my $self = shift; 
    my $tuple = ref2tuple(shift); 
    return if ref($self) ne 'Tuples'; 
    return if ! defined $tuple->[0]; 
    return if ! defined $self->{$tuple->[0]} ; 
    my $newtuple = [ @$tuple[1..$#$tuple] ]; 
    $self->{$tuple->[0]}->del($newtuple); 
    delete $self->{$tuple->[0]} if scalar(%{$self->{$tuple->[0]}})==0; 
} 

# generate a contents list for a tuple space
sub contents { 
    my $self = shift; 
    return undef if ref $self ne 'Tuples'; 
    return undef if scalar(%$self) == 0; 
    my $out = []; 
    my @keys = keys %$self; 
    foreach my $k (@keys) { 
	my $result = $self->{$k}->contents; 
	if (defined $result) { 
	    my $res2; 
	    foreach my $r (@$result) { 
		push(@$res2,[$k,@$r]); 
	    } 
	    $result = $res2; 
	} else { 
	    $result = [[$k]]; 
	} 
	push(@$out,(@$result)); 
    } 
    foreach my $k (@keys) { 
	$out->[$k] = &tuple2ref($out->[$k]); 
    } 
    return $out; 
} 

1; 
...end of perl_data/Stuples.pm

Apply this using:

contents of perl_data/Stuples.pl...
#! /var/local/couch/bin/perl 

use DD; 
use Stuples; 

my $thing = new Stuples; 
$thing->add({'a'=>'b', 'c'=>['d',2,3]}); 
$thing->add([1,2,3]); 
$thing->add({'george'=>'frank','al'=>4}); 
print DD($thing); 

if ($thing->member({'george'=>'frank','al'=>4})) { 
     print "membership works\n"; 
} else { 
     print "membership doesn't work\n"; 
} 

if ($thing->member({'george'=>'bob','al'=>4})) { 
     print "membership doesn't work\n"; 
} else { 
     print "membership works\n"; 
} 
...end of perl_data/Stuples.pl

This prints:

contents of perl_data/Stuples.pl.out...
$VAR1 = bless( {
  '__OPBRACK__' => bless( {
    '1' => bless( {
      '2' => bless( {
        '3' => bless( {
          '__CLBRACK__' => bless( {}, 'Stuples' )
        }, 'Stuples' )
      }, 'Stuples' )
    }, 'Stuples' )
  }, 'Stuples' ),
  '__OPBRACE__' => bless( {
    'c' => bless( {
      '__OPBRACK__' => bless( {
        'd' => bless( {
          '2' => bless( {
            '3' => bless( {
              '__CLBRACK__' => bless( {
                'a' => bless( {
                  'b' => bless( {
                    '__CLBRACE__' => bless( {}, 'Stuples' )
                  }, 'Stuples' )
                }, 'Stuples' )
              }, 'Stuples' )
            }, 'Stuples' )
          }, 'Stuples' )
        }, 'Stuples' )
      }, 'Stuples' )
    }, 'Stuples' ),
    'al' => bless( {
      '4' => bless( {
        'george' => bless( {
          'frank' => bless( {
            '__CLBRACE__' => bless( {}, 'Stuples' )
          }, 'Stuples' )
        }, 'Stuples' )
      }, 'Stuples' )
    }, 'Stuples' )
  }, 'Stuples' )
}, 'Stuples' );
membership works
membership works
...end of perl_data/Stuples.pl.out

This is an application of composition of bijections.

 
          Dumper      TupleRef.pm     Tuples.pm
             |             |            | 
structures <---> strings <---> tuples <---> hierarchical hashing
         bijection    "incomplete"   "lossy"

This works, even though it isn't perfect! What gives?
Dumper is a perfect bijection.
Converting between strings and tuples only works if the strings don't contain the magic substrings __OPPAREN__, __OPBRACE__, __CLPAREN__, __CLBRACE__, ...
There must be something less stringent than a bijection that allows one to use a new representation for a specific task.
Answer: homomorphisms

Homomorphisms

A homomorphism is a structure-preserving map.
- homo: preserve
- morphos structure
Preservation of structure means that equivalent operations can be performed on either side of the map with the same result
If f:D->R is a homomorphism for operation e on D, amd e' is the equivalent for e in R, then it is always true that the result of e(d) in D is equivalent with the result of e'(f(d)) in R.
A bijective homomorphism is called an isomorphism.
A homomorphism is only defined in terms of the operations it preserves. It is improper to call something a homomorphism without identifying the operations it preserves.
Example: Array2Hash.pm is a homomorphism for the operation is "determining presence of an array element value", but not an isomorphism unless the array has only one copy of each value.
Two structures for which a homomorphism exists are called homomorphic for the operations that the homomorphism preserves.

Facts about homomorphisms

The composition of two or more homomorphisms (that preserve the same operation) is a homomorphism for the operation.
```
 
  D --f--> E --g--> F
   \       |       / 
    \      |      /
     \   e'|     /
   e  \    |    / e''
       \   |   / 
        \  |  /
         v v v
         result 
```
f is a homomorphism of the operation e if e'(f(x)) is e(x) for all x in D. g is a homomorphism of the operation e' if e''(g(y)) is e'(y) for all y in E. It follows trivially that g^.f is a homomorphism from D to F that preserves e.
Homomorphisms can often be constructed from non-homomorphisms by limitation of domain.
TextRef.pm is only a homomorphism for "structure search" if the structure does not contain magic keywords such as __OPPAREN__, etc. This is an example of limitation of domain.

What's the big deal?

Homomorphisms preserve result but can improve runtime!
Two examples: simple hashing and regexps.

Searching for members

Suppose we want to search an array for various members. One way to do this is:

 
sub amember { 
    my $thing = shift; 
    my $array = shift; 
    foreach my $a (@$array) { return 1 if $thing eq $a; } 
    return undef; 
}

If the array has n elements, this process is always O(n). This runtime remains even if we eliminate all explicit and implicit data copying from the function:

 
sub amember { 
    foreach (@{$_[1]}) { return 1 if $_[0] eq $_; } 
    return undef; 
}

Now we know there's a shorter way to search for members in a hash table:

 
sub hmember { 
    my $thing = shift; 
    my $hash = shift; 
    return defined $hash->{$thing};
}

or, equivalently,

 
sub hmember { defined $_[1]->{$_[0]} }

And we know how to convert between arrays and hashes:

 
sub f { 
    my $array = shift; 
    my $hash = {}; 
    foreach my $a (@$array) { $hash->{$a}=1; } 
    return $hash; 
}

or, equivalently (without data copying)

 
sub f { 
    my $hash = {}; 
    foreach (@{$_[0]}) { $hash->{$_}=1; } 
    return $hash; 
}

Let's look at runtimes for all of these:

 
       Omega(n*1), Avg(n*1), 
       O(n*log₂n)
  $array --------f-------> $hash
     | Omega(n),             | Omega(1), Avg(1), 
     | O(n)                  | O(log₂n)
     v (Theta(n))            v
&amember($thing,$array) = &hmember($thing,$hash)

In this diagram, either path (amember or hmember^.f) returns the same exact result.

amember has runtime O(n) (n=number of elements).
hmember^.f has runtime O(n*log₂n+log₂n).

But let's look at what happens when we query for array elements m times:

 
       Omega(n*1), Avg(n*1), 
       O(n*log₂n)
  $array --------f-------> $hash
     | Omega(n*m),           | Omega(m), Avg(m), 
     | O(n*m)                | O(m*log₂n)
     v (Theta(n*m))           v
&amember($thing,$array) = &hmember($thing,$hash)

In this case:

amember has runtime O(n*m) (n=number of elements).
hmember^.f has runtime O((n+m)*log₂n).

Clearly the second is superior when n and m are roughly the same size.
The moral: the setup time for transforming a structure to be searchable is often worth the effort in terms of time saved when searching.
This looks even better when one looks at average behavior rather than worst case:
- amember has runtime Avg(n*m) (n=number of elements).
- hmember^.f has runtime Avg(n+m).

Indexing searches

Can often speed up a process involving multiple queries by injecting an index into a linear search process.
If
- You need to do a rather long search, and
- you need to repeat it multiple times, and
- the actual goal of the search is relatively simple, then
you can index the search once (in the time of one search * O(log₂n) and then each search takes O(log₂n) (where n is the number of elements being searched).
In this case, the "homomorphism" is trivially from "data" to "data + index".
Result is instant conversion from an O(n²) operation to an n*log₂n operation.
Watch out! If data can change, cost of indexing can be very high indeed.

Example of index injection

Suppose we want to count the appearances of a particular key in a complex and freely constructed hash structure.

This will take O(n) steps per search, where n is the number of keys in the whole structure:

contents of perl_data/index1.pl...
#! /var/local/couch/bin/perl 
use Data::Dumper; 

sub count { 
    my $h = shift;      # hash reference to search 
    my $target = shift; # for which to count references
    my $count = 0; 
    my ($k,$v) ; 
    while (($k,$v) = each %$h) { 
	$count++ if $k eq $target; 
	if (ref $v eq 'HASH') { 
	    $count += &count($v,$target); 
	} else { 
	    $count++ if $v eq $target; 
	} 
    } 
    return $count; 
} 
my $hash = { 'a' => {'b'=>{'a'=>'a'}}, 'd'=>'b'}; 
print &count($hash,'a') . "\n"; 
...end of perl_data/index1.pl

If we need to repeat this for other keys, then we could write, e.g.,

contents of perl_data/index2.pl...
#! /var/local/couch/bin/perl 
use Data::Dumper; 
sub count { 
    my $h = shift; 
    my $count = shift; 	# passed for side-effects
    if (ref $h eq 'HASH') { 
	my ($k,$v) ; 
	while (($k,$v) = each %$h) { 
	    $count->{$k}++; 
	    if (ref $v eq 'HASH') { 
		&count($v,$count); 
	    } else { 
		$count->{$v}++
	    } 
        } 
    } 
} 

my $hash = { 'a' => {'b'=>{'a'=>'a'}}, 'd'=>'b'}; 
my $count = {}; 
&count($hash,$count); 
print Dumper($count) ; 
...end of perl_data/index2.pl

after which $count would be:

 
$count = { 'a'=>3, 'b'=>2, 'd'=>1 } ;

and all further queries degenerate to hash dereferencing.

The following is quite legal and quite weird:

contents of perl_data/Index1.pm...
#! /var/local/couch/bin/perl 

package Index1; 

require Exporter;

BEGIN { 
    @Index1::ISA= qw(Exporter); 
    @Index1::EXPORT=qw(); 
    @Index1::EXPORT_OK=qw(); 
    %Index1::hashes = (); 	# storage for indexes by ADDRESS
} 

# memorize the counts of ALL atoms in a nested 
# hash, and cache the results by hash REFERENCE ADDRESS. 
# after a single call, all subsequent calls occur in 
# O(log n) rather than O(n)
sub count { 
    my $h = shift;      # hash reference to search 
    my $target = shift; # for which to count references
    if (! defined $Index1::hashes{$h}) { 
        my $count = $Index1::hashes{$h} = {}; 
        &count_index($h,$count); 
    } 
    return $Index1::hashes{$h}->{$target}; 
} 

# recursive function does the actual counting. 
sub count_index { 
    my $h = shift; 
    my $count = shift;         # passed for side-effects
    if (ref $h eq 'HASH') { 
        my ($k,$v) ; 
        while (($k,$v) = each %$h) { 
            $count->{$k}++; 
            if (ref $v eq 'HASH') { 
                &count_index($v,$count); 
            } else { 
                $count->{$v}++
            } 
        } 
    } 
} 

# this function doesn't know when hashes CHANGE
# we must reset it when that happens. 
sub reset { 
    my $h = shift; 
    delete $Index1::hashes{$h}; 
} 

1; 
...end of perl_data/Index1.pm

Yes, I used the address of a reference as a key in a hash table %Index1::count. This means that I'll only get data for the exact same variable.

Call this with:

contents of perl_data/Index1.pl...
#! /var/local/couch/bin/perl 

use Index1; 

my $hash1 = { 'a' => {'b'=>{'a'=>'a'}}, 'd'=>'b'}; 
my $hash2= { 'h' => {'k'=>{'g'=>'e'}}}; 

foreach my $t ( 'a' .. 'k' ) { 
    print "count 1 for $t is " . Index1::count($hash1,$t) . "; "; 
    print "count 2 for $t is " . Index1::count($hash2,$t) . "\n"; 
} 
...end of perl_data/Index1.pl

and it prints

contents of perl_data/Index1.pl.out...
count 1 for a is 3; count 2 for a is 
count 1 for b is 2; count 2 for b is 
count 1 for c is ; count 2 for c is 
count 1 for d is 1; count 2 for d is 
count 1 for e is ; count 2 for e is 1
count 1 for f is ; count 2 for f is 
count 1 for g is ; count 2 for g is 1
count 1 for h is ; count 2 for h is 1
count 1 for i is ; count 2 for i is 
count 1 for j is ; count 2 for j is 
count 1 for k is ; count 2 for k is 1
...end of perl_data/Index1.pl.out

Lessons learned

Runtime in Perl greatly depends upon the representation you choose for a particular data structure.
Sequences require arrays.
Sequences are memory-efficient but can make runtimes slower.
Associations require hashes.
Hashes are memory-intensive but quick for purposes of runtime.

lecture in color

downloaded on Nov-23-2009 02:25:06 PM,
was last modified on Dec-31-1969 07:00:00 PM.
All lecture note content is copyright 2003 by
Alva L. Couch, Computer Science, Tufts University
(couch at cs dot tufts dot edu)