Set Operations

A month or so ago, while working on ABC, I tried to use [∪] (reduce on set union) in my grammar actions. Unfortunately, it blew up when I tried it in Niecza. I assumed the problem was that I hadn’t implemented zero or one arguments forms of set union, and made a quick effort to add them. It didn’t work, so I worked around the problem by using the set constructor directly and added it to my to-do list.

I finally got around to tackling the problem again this week, and my earlier difficulties were quickly explained when I looked at the stack trace for the error message. turns out to be list associative. That means if you write $a ∪ $b ∪ $c, the actual call generated is infix:<∪> ($a, $b, $c), and the reduce meta-op generates that call internally. So I needed to change infix:<∪> from a binary sub to an N-ary sub.

Previously the code looked like this

proto sub infix:<∪>($, $ --> Set) is equiv(&infix:<|>) {*}
multi sub infix:<∪>(Any $a, Any $b --> Set) { $a.Set ∪ $b.Set }
multi sub infix:<∪>(Set $a, Set $b --> Set) { Set.new: $a.keys, $b.keys }
multi sub infix:<∪>(Baggy $a, Any $b --> Bag) { $a ∪ $b.Bag }
multi sub infix:<∪>(Any $a, Baggy $b --> Bag) { $a.Bag ∪ $b }
multi sub infix:<∪>(Baggy $a, Baggy $b --> Bag) {
    Bag.new-from-pairs(($a.Set ∪ $b.Set).map({ ; $_ => $a{$_} max $b{$_} }))
}

So the rules were, if you had a Baggy (ie Bag or KeyBag), you promoted both arguments to Bag. Otherwise both arguments were promoted to Set. Also note that, because of this, the proto signature was wrong — it could generate a Set or a Bag.

I replaced them with a single sub:

only sub infix:<∪>(\|$p) is equiv(&infix:<|>) {
    my $set = Set.new: $p.map(*.Set.keys);
    if $p.grep(Baggy) {
        my @bags = $p.map(*.Bag);
        Bag.new-from-pairs($set.map({ ; $_ => [max] @bags>>.{$_} }));
    } else {
        $set;
    }
}

Line 2 creates the Set version of the union. Then we check to see if any of the arguments are Baggy using $p.grep(Baggy). (That filters out all the non-Baggy from the argument list, and then (because it is used in a boolean context) returns true if the resulting list has any elements in it.) If there is a Baggy, then we convert all the arguments to Bag. Line 5 is a spiffy bit of code that creates a new Bag using the maximum count for each element found in $set. Finally, if there were no Baggyarguments, just return $set.

Once I had that working, I did the same for infix:<∩>. Then I started looking at infix:<(-)>. I’ve only ever seen set difference used as a binary operation, so my first step was to think about how to generalize it to N arguments. My thought was $a (-) $b (-) $c should be ($a (-) $b) (-) $c. If someone has a good reason this shouldn’t be the case, please let me know!

Then the next question was, what should Baggy objects do here? Previously set difference always converted its arguments to Set. But it seemed to me there was a pretty obvious way to do it. After consideration, I concluded it should only use the Bag form if the first argument (the “set” things are being subtracted from) was a Baggy. Here’s my current code for infix:<∖> (note the new name, which is the ISO symbol for set difference rather than the common backslash):

only sub infix:<∖>(\|$p) is equiv(&infix:<^>) {
    return ∅ unless $p;
    if $p[0] ~~ Baggy {
        my @bags = $p.map(*.Bag);
        my $base = @bags.shift;
        Bag.new-from-pairs($base.keys.map({ ; $_ => $base{$_} - [+] @bags>>.{$_} }));
    } else {
        my @sets = $p.map(*.Set);
        my $base = @sets.shift;
        Set.new: $base.keys.grep(* ∉ @sets.any );
    }
}

This works (I think — I haven’t really tested the Baggy functionality, I’ve only run the existing Set tests). But it breaks some spectests (which assume set difference always returns a Set). And it involves the unspecified details mentioned above, so I’m stepping out on a bit of a limb. So I’m posting here looking for feedback before I commit these changes.

(Edited to add: I’ve also added infix:<⊖> for symmetric difference; that’s one of the standard symbols used, but it’s not ISO standard.)

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: