A Hash as a Set

Part I · Module 6 · Chapter 6.9 · A Hash as a Set

1. Keys Only, Values Ignored

use strict;
use warnings;

my %is_allowed = map { $_ => 1 } qw(alu fifo decoder);

for my $block (qw(fifo cpu)) {
    printf "%-6s allowed: %s\n", $block, ($is_allowed{$block} ? "yes" : "no");
}

fifo   allowed: yes
cpu    allowed: no

The values are all 1 and nothing ever reads them — their only job is to make the key exist. What matters is which keys are present.

map { $_ => 1 } @list is the standard way to build such a set: the block returns two items per input, which flatten into the hash by Chapter 5.12's rule. map is Chapter 5.10's.

This is the structure Chapter 5.11 §1 pointed forward to. Compare the two membership tests:

For a handful of names in a one-off check, grep is fine. For a check inside a loop, or against a list of thousands, the hash is the one that works — and the difference is not a micro-optimisation, it is the difference between a script finishing and not.

2. The Deduplication Idiom

use strict;
use warnings;

my @blocks = qw(alu fifo alu decoder fifo alu);

my %seen;
my @unique = grep { !$seen{$_}++ } @blocks;

printf "original : %d  [%s]\n", scalar(@blocks), join(" ", @blocks);
printf "unique   : %d  [%s]\n", scalar(@unique), join(" ", @unique);

original : 6  [alu fifo alu decoder fifo alu]
unique   : 3  [alu fifo decoder]

Six down to three. That one expression is the answer Perl programmers give to "how do I remove duplicates", and it is worth taking apart because it is dense.

How !$seen{$_}++ works

Read it from the inside:

1. $seen{$_} reads the entry for the current item. The first time an item appears this is undef.
2. ++ is a post-increment: it returns the value before adding one. So the first time it returns undef — which is false — and the entry becomes 1. Every later time it returns 1 or more, which is true.
3. ! negates that. First time: !false is true. Later times: !true is false.
4. grep keeps the items where the block was true — so it keeps each item exactly the first time it appears.

Two earlier findings make it work silently:

• The first read is of an absent key, and Chapter 6.8 §3 measured that ++ on an absent key neither warns nor needs initialising.
• $_ inside grep is Chapter 5.10's, and this block only reads $_, so there is no alias hazard.

A longer form says the same thing if you prefer it explicit:

use strict;
use warnings;

my @blocks = qw(alu fifo alu decoder fifo alu);

my %seen;
my @unique;

for my $block (@blocks) {
    next if exists $seen{$block};
    $seen{$block} = 1;
    push @unique, $block;
}

printf "unique : %d  [%s]\n", scalar(@unique), join(" ", @unique);

unique : 3  [alu fifo decoder]

Same result, six lines instead of one, and exists rather than truth. For a team unfamiliar with the idiom this is the kinder version; the one-liner is what you will read in other people's code, so you need to recognise it either way.

3. The Idiom Preserves Input Order — and keys Does Not

This is the reason to use grep rather than the obvious alternative.

use strict;
use warnings;

my @input = qw(zebra apple zebra mango cherry);

my %seen;
my @via_grep = grep { !$seen{$_}++ } @input;

my %set;
$set{$_} = 1 for @input;
my @via_keys = keys %set;

printf "input    : %s\n", join(" ", @input);
printf "via grep : %s\n", join(" ", @via_grep);
printf "via keys : %s\n", join(" ", @via_keys);

Run five times:

zebra apple mango cherry
zebra apple mango cherry
zebra apple mango cherry
zebra apple mango cherry
zebra apple mango cherry

mango cherry zebra apple
cherry apple zebra mango
zebra cherry apple mango
cherry mango zebra apple
apple zebra cherry mango

The grep form gave the identical order five times out of five. The keys form did not settle on an order at all — the five lines above are five different orderings, and repeating the whole capture later produced another set in which two runs happened to agree and three did not. The reproducible fact is that the grep line is stable and the keys line is not; the specific orderings are whatever that process's seed produced.

The reason is Chapter 6.6: keys has no order, so collecting the keys of a set throws away the sequence the items arrived in. grep walks the input list, so the output is a subsequence of the input and its order is the input's.

4. Detecting Duplicates Rather Than Removing Them

The same post-increment, used the other way round, reports what repeated:

use strict;
use warnings;

my @tests = qw(a b a c b a);

my %seen;
my @repeats;

for my $test (@tests) {
    push @repeats, $test if $seen{$test}++;
}

printf "input    : %s\n", join(" ", @tests);
printf "repeats  : %s\n", join(" ", @repeats);
printf "distinct : %d of %d\n", scalar(keys %seen), scalar(@tests);

input    : a b a c b a
repeats  : a b a
distinct : 3 of 6

Three distinct values — a, b, c — out of six observations, which is Chapter 6.8 §1's two numbers again.

Note repeats contains a twice — once for each time it appeared beyond the first. That is usually what you want for a report: "this test was submitted three times" is three rows of evidence, not one.

If you want each duplicated name once, deduplicate the list of repeats:

use strict;
use warnings;

my @tests = qw(a b a c b a);

my %count;
$count{$_}++ for @tests;

my @duplicated = sort grep { $count{$_} > 1 } keys %count;

printf "names appearing more than once: %s\n", join(" ", @duplicated);

names appearing more than once: a b

Built on Chapter 6.8's tally plus a grep over the keys — which is the clearer way to express "more than once" than any variation on the post-increment trick.

This is the check Chapter 6.3 §3 needed: a hash built from rows silently keeps the last of a duplicated key, and a tally tells you which keys were duplicated so you can decide what to do about it.

5. Set Algebra With grep

Two sets and grep give you the usual operations:

use strict;
use warnings;

my @ran      = qw(alu fifo decoder);
my @expected = qw(fifo decoder cpu);

my %is_expected = map { $_ => 1 } @expected;
my %did_run     = map { $_ => 1 } @ran;

printf "ran and expected    : %s\n", join(" ", sort grep {  $is_expected{$_} } @ran);
printf "ran but unexpected  : %s\n", join(" ", sort grep { !$is_expected{$_} } @ran);
printf "expected but missing: %s\n", join(" ", sort grep { !$did_run{$_}     } @expected);

ran and expected    : decoder fifo
ran but unexpected  : alu
expected but missing: cpu

Three questions, three one-liners:

• Intersection — grep { $other{$_} } over one list.
• Difference — grep { !$other{$_} }.
• The other difference — swap which list you walk and which set you test against. That asymmetry is the point: "ran but not expected" and "expected but did not run" are different questions and need different directions.

That last pair is a genuinely useful report. A regression that ran a test nobody asked for and skipped one that was requested has two different problems, and this is three lines to find both.

Note each line sorts its output, for Chapter 6.6's reason — the grep preserves the order of the list it walks, which here is a qw literal, so sorting is for the report's benefit rather than for determinism.

6. Why This Matters in Engineering Work

Deduplicating a list of names. A filelist assembled from several sources, a list of blocks collected from multiple reports, a set of signals gathered by walking a hierarchy. All of them can contain the same entry twice, and the one-liner handles it while keeping the order the entries were found in.

"Have I processed this already." A script walking a dependency graph or a directory tree needs to avoid revisiting, and next if $seen{$item}++; is the guard — one line, and it both tests and records.

Did we run what we were asked to. §5's three-way comparison between the requested set and the completed set is one of the most useful things a flow wrapper can report, and it is three greps.

And the order question is a real decision. A deduplicated list printed in hash order changes between runs, so a filelist generated that way has a different content hash every time — which breaks caching, breaks diffs, and makes a build look non-reproducible. The grep form costs nothing and removes the problem.

7. Common Mistakes

Testing the value when it might be false. if ($set{$k}) fails for a present key whose value is 0. Use exists unless you control the values.

Using keys %seen when order matters. It changes between runs. Use the grep form.

Concluding from one run that keys preserves order. It can coincide with the input by chance.

Writing $seen{$_}++ in a grep without the !. You would keep every item except the first of each.

Using a pre-increment. !++$seen{$_} is always false — the increment happens first, so the value is never 0.

Reaching for grep over a list for repeated membership tests. Chapter 5.11 §1's point: build a set once instead.

Reporting duplicate names from the repeats list without deduplicating it. A name seen three times appears twice in that list.

8. Exercise

Exercise 1 — build a set. Make a set of four allowed block names with map, then test two present and two absent names. Then rewrite the test with exists and say when the difference would matter.

Exercise 2 — the one-liner. Deduplicate a seven-item list containing three distinct values. Report both counts and the unique list.

Exercise 3 — take it apart. For the first and second appearance of one item, write down what $seen{$_} holds, what ++ returns, what ! gives, and whether grep keeps it. Four values per appearance.

Exercise 4 — order, five runs. Deduplicate the same list via grep and via keys, printing both. Run it five times and record all ten lines. State which form you would use for a generated filelist and why.

Exercise 5 — break it. Change !$seen{$_}++ to !++$seen{$_} and record what you get. Explain the result in one sentence.

Exercise 6 — report the duplicates. From a list where two names repeat, produce the list of every repeat occurrence and, separately, the sorted list of names that appeared more than once. Say which you would put in a warning message.

Exercise 7 — three-way comparison. Given a requested set and a completed set that overlap partially, report what ran and was expected, what ran unexpectedly, and what was expected and missing. Confirm the last two are different lists.

9. Summary

• Ignoring the values turns a hash into a set, and map { $_ => 1 } @list is how you build one.
• A set lookup costs the same regardless of size, which is why it replaces grep for repeated membership tests.
• Test with exists unless you control the values and they are all true.
• grep { !$seen{$_}++ } @list deduplicates — the post-increment returns the old value, so only the first appearance is kept.
• The grep form preserves input order: identical across five runs, where keys %seen gave five different orders.
• One run is not evidence about hash order. It can match the input by chance.
• push @repeats, $x if $seen{$x}++ collects every repeat occurrence; a tally plus grep { $count{$_} > 1 } gives each duplicated name once.
• Intersection is grep { $other{$_} } and difference is grep { !$other{$_} } — and swapping which list you walk answers the other direction.

Chapter 6.10 covers the conversion that has been implicit throughout this module — a hash used as a list becomes alternating keys and values, and a list of pairs becomes a hash, which is how hashes get into and out of subroutines.