Sequences, Sets, Bags, Functions

Groups of Items

A sequence is an ordered list of items, whose items aren't necessarily unique. Perl's arrays are sequences of a finite size:

my @sequence = qw/bar baz ban baz baz/;

A set, however, is an unordered collection of unique items. Perl provides native support for sets in the form of the keys of hashes:

my %set1 = map { $_ => undef } qw/foo bar baz/;
my %set2 = map { $_ => undef } qw/bar foo foo baz/; # Same as above
my %set3 = map { $_ => undef } qw/baz baz bar bar foo foo/; # Also same as above

Because sets are unordered, and contain unique items, the sets formed by the keys of the hashes above are identical. Generally sets are used to test for membership:

my %acceptable = map { $_ => undef } qw/foo bar baz/;
die unless exists $acceptable{ $key };

Set::Scalar provides further useful set operations.

Bags - or multisets - are like sets, in that order is unimportant. However, they differ from sets in that values can be repeated. In Perl, the values of a hash are a bag, but you're more likely to be familiar with them from multi-value CGI forms:

my $q = CGI->new;
@values = $q->param('form_field');

param('form_field') represents a bag - you'll get a consistent number of elements (cardinality), and repetitions are allowed, but there are no guarantees about ordering.

You can also express a bag as a hash where the values are number of repetitions:

my %bag = ( foo => 1, bar => 2, baz => 3 );

Set::Bag provides useful functions on bags.



While Perl doesn't really have the concept of a pair, you can think of a pair as being a two-item array.

my @pairs = ([0, 0], [1, 2], [2, 4], [3, 6], [4, 8], [5, 10]);

Mathematically, a function is a (perhaps infinite) collection of pairs, where the first items of the pairs are a set, and the function applied to the first element of the pair returns the second element. @pairs above is equivalent to:

f n = 2n

(for natural numbers smaller than 6). This means that Perl's arrays and hashes are really functions with finite inputs:

my @double_small_number = (0, 2, 4, 6, 8, 10);
is( $double_small_number[2], 4, "Apply double_small_number to 2" );

my %convert_to_numeral = (
'I' => 1,
'II' => 2,
'III' => 3,
'IV' => 4,
'V' => 5,
is( $convert_to_numeral{'III'}, 3, "Apply convert_to_numeral to III");

Wikipedia: Functions


I want to use Set::Bag module you mentioned, but it seems to be a deadlink. Searching on CPAN also does not give any results. Can you provide me some other link to this module?

Leave a comment

About Peter Sergeant

user-pic I blog about Perl.