Coding with a full toolset

A few years ago, I created a talk (and later an entire class) about "transparadigm programming" in Perl 6.

The basic premise was that while some languages restrict you to only a single hammer (or worse: a box full of hammers), Perl 6 was designed to be a complete toolkit: integrating OO, functional, concurrent, declarative, and procedural tools to allow you to choose exactly the right combination for each job.

That idea came back to me in full force recently. In last week's Perl Weekly Challenge, the second task was to take a list of file paths and find the longest common initial subpath (i.e. the deepest directory they all share).

The solutions offered by the various registered participants were all very clean, and often both efficient and elegant. Yet most of them were variations on the same procedural solution: Split each path on the directory separator, then for 1-to-N: compare all the Nth components and quit if they're not identical. Something like:

my @components = @list.map({.split('/')};

for 1..* -> $n {
next if all(@components).elems > $n
&& [~~] @components.values».[$n];

say @components.first.[0..$n-1].join('/');
last;
}

Not that there's anything wrong with that approach.

Except that it feels like a lot more "manual labour" than was actually necessary; a lot of low-level procedural "Tell me how", instead of high-level declarative or functional "Tell me what".

When I came to solve this problem myself, I thought about it like this:

My search space is all the possible initial subpaths of all of the paths. Within that space, I need to find the longest initial subpath that all the paths share. In other words, I need to convert each path into a set of increasingly long subpaths, then find the intersection of those sets, then find the longest element in that intersection set.

Which can be translated directly into Perl 6, like so:


@list.map({m:ex{^.*\/}».Str}).reduce({$^a∩$^b}).keys.max(*.chars).say;

or (for those who like comments) like so:

@list\ # In the list...
.map({m:ex{^ .* '/'}\ # Find all initial subpaths
».Str})\ # ...as lists of strings
.reduce({$^a ∩ $^b})\ # Then find all shared subpaths
.keys.max(*.chars)\ # Then find the longest
.say; # Then print it

We start with the list of paths, and transform each of them via a .map operation.

The m:ex{^ .* '/'} within the mapping is an exhaustive match operation. Rather than matching just the longest possible sequence of characters ending in a slash, the regex matches every possible sequence of characters ending in a slash. In other words, it matches every possible increasingly longer initial subpath, and returns them all...as a list of Match objects.

The trailing ».Str after the exhaustive match then converts each such Match object into a simple string, so that the surrounding .map operation produces a list of lists of strings, representing all the possible initial subpaths.

We then need to treat each of these lists as a set, and to find the intersection of them all (i.e. the subpaths they all share). So we need to inject a set-intersection operator (∩) between each of the lists, which is precisely what .reduce({$^a ∩ $^b}) does.

The outcome of this operation is a single set containing all the initial subpaths that are shared by all the original paths, where each subpath is a single key of the set. So calling .keys gives us a list of all the subpaths, and we can find the longest of them by asking for the one in which the number of characters is maximal: .max(*.chars)

Then we just print that maximal subpath (.say), and we're done.

To me, even though this version is considerably shorter than the procedural approach, it's also easier to follow. It reads strictly left-to-right, in a single line of code. And at every step along the way, it just describes what transformation it wants next, and lets Perl 6 do the hard work. It's straightforward...because it can use exactly the right tool (OO, functional, or declarative) for each step in the overall task. And it's short...because all those tools are already built right into the core language.

So that's another thing I love about Perl 6:
"All the right tools, right at hand."

Damian


(And, yes, I'm well aware that I could have made my version at least 30% shorter, like so:
keys([∩] @list.map:{~«m:ex{^.*\/}}).max(*.chars).say
The problem is that also makes it at least 30% harder to understand! ;-)

4 Comments

In the example above the first line should be

my @components = @list.map({.split('/')};

right?

Perhaps it's the APLer in me, but I actually find the 30% shorter version considerably easier to understand. :-)

I'm curious, though, why one doesn't need ».Str in that version.

Leave a comment

About Damian Conway

user-pic I blog about Perl.