Chad Perrin: SOB

14 December 2006

linguistic comparisons: string reversal

Filed under: Geek — apotheon @ 07:48

Over at PerlMonks, a discussion cropped up about reversing a string of words in a number of different languages. It all started with the OP‘s encounter with C# programmers at work who commit the sin of cargo-cult premature optimization: they think about trying to optimize code for the computer before worrying about optimizing it for writing and maintaining, and aren’t even checking the optimization to see if it gets them anything, apparently.

The “canonical” C# version of a string reversal function is:

private static string reverseWords(string str) {
    string[] words = Array.FindAll(str.Split(
                     new char[] {' ','\t'}),
                     delegate(string s) {
                        return !String.IsNullOrEmpty(s); });
    int i = words.Length - 1;
    if (i < 0)
        return String.Empty;
    StringBuilder sb = new StringBuilder(words[i]);
    while (--i >= 0)
        sb.Append(' ').Append(words[i]);
    return sb.ToString();

It’s a mess. It’s a disaster area. The version the OP prefers (and so do I) would be:

return String.Join(" ", words);

The OP then went on to provide some examples of how to accomplish the same thing in a number of different languages. This being in Perl, of course, there were about a half dozen or so other Perl versions presented in the discussion thread (TIMTOWTDI and all that), but I still like the OP’s best:

sub reverseWords {
  join ' ', reverse split(' ', shift)

The OP’s Ruby example is similarly elegant:

def reverseWords(s)
  s.split.reverse.join(' ')

Contrary to what my immediately previous post here at SOB might suggest, I rather like what I know about Haskell so far. I just think it should stand on its own merits, and doesn’t need someone inventing excuses to denigrate other languages to make Haskell look better by comparison. Here’s a very elegant Haskell solution to the string reversal, also of the OP’s making (with credit given to the Haskell-Cafe mailing list for help):

reverseWords = unwords . reverse . words

There were additional examples presented in a number of other languages, including even Lua and JavaScript (ew), both of which were predictably less elegant than others. REBOL put in a respectable showing. There were shell language entries to the examples, which of course looked like shell scripts — usable, understandable, uglay.

Because these comparisons often end up being about Perl vs. Python, I figured I’d bow to tradition and include Python from the discussion here. One discussion participant offered this example:

def reverseWords (s):
    l = s.split(" ")
    return " ".join(filter(lambda x: x != '', l))

Another contributor offered this:

def reverseWords(words):
    return ' '.join(words.split()[::-1])

. . . which is much more succinct. Both, however, suffer from symbol-obfuscation in a manner reminiscent of common Pythonista complaints about Perl. I mean, really — just compare both of those to the Perl example above and tell me which is more readable. I tend to think that x: x != '', l and [::-1] are less than perfectly clear. Is there a better (more readable and elegant) way to do this in Python?

Larry Wall himself, meanwhile, showed up to share these three gems of Perl 6 golf:

sub reverseWords ($) {~reverse .comb}
sub reverseWords {~reverse comb @}

He commented that “The first two could even be construed as readable.” I responded that if we really want to golf to the fewest strokes, we might want to consider UCBLogo. Here’s my example:

That’s it. No keystrokes needed to define the function at all. If this was the Scottish game of golf, my ball would have started in the hole rather than on the tee. That’s because in UCBLogo, all data types are lists, and UCBLogo has a reverse procedure effectively identical to Perl’s reverse() function (which means it operates on lists, among other things, rather than being a string-based function). Because the data types are already lists in UCBLogo, including the equivalent of a multi-word “string”, there’s no need to use join() and split() (or comb, in Perl 6) to turn string data into list data before operating on it.

Someone else entirely suggested that one could achieve the same effect with Perl by loading up your data as a list in the first place, rather than as a string. For instance, instead of doing this:

$var = "one two three four";
. . . you might do this:

@var = qw(one two three four);

I’m paraphrasing, of course, but that’s the upshot of how the example might be altered. He’s right, you could do that — but it’s sorta cheating. The idea was to have a string (or whatever your language uses for the same purposes as strings), thus allowing the full range of the language’s common text/string manipulation tools. By creating the data as a list, and never making it a single string at all, one doesn’t satisfy that spirit of the challenge. At least, that’s my thought on the matter. As I said in the discussion:

Absolutely. You can do list-oriented programming in Perl as well. The problem that arises is that while doing list-oriented programming you lose the ability to do certain text manipulations without breaking the list-oriented style. For instance, you run afoul of problems with regular expressions over a string if you represent the string as an array. Similarly, you must convert to a list when you read strings in from external sources. There are many things that Perl does better for text processing than UCBLogo, but I think UCBLogo wins on this one score.

Generally, Perl is probably much better at text manipulation than UCBLogo, but in this case I was stunned to find that UCBLogo was a pretty clear winner. Go fig’.

fibonacci sequence comparisons

Filed under: Geek — apotheon @ 04:51

I ran across an online attempt to claim that Haskell has something approaching the perfect programming language syntax. It compared the code for a fibonacci sequence generator in a number of different languages, including haskell. From what I’ve seen, the guy doesn’t seem to know much about any of the languages other than Haskell, because some of those fib generators are atrocious examples of code in their respective languages. All of them could be better written than they were.

For instance, this was his example of Perl:

sub fib {
  my ($n, $a, $b) = (shift, 0, 1);
  ($a, $b) = ($b, $a + $b) while $n-- > 0;

I took the liberty of formatting the code to be a little prettier, and altered the subroutine name. Otherwise, it’s exactly the same.

Here’s an example of how I might write the same thing using recursion:

sub fib {
  my $n = shift;
  return $n if $n < 2;
  return fib($n - 1) + fib($n - 2);

That’s pretty much the canonical solution, matching the mathematical definition pretty closely. I’ve heard it said that it’s pretty slow, but running that on the number 20 is pretty much instantaneous when you use the Memoize module to optimize your Perl code:

!/usr/local/bin/perl -l

use strict; use warnings; use Memoize;


foreach my $x (0..$ARGV[0]) { print fib($x); }

sub fib { my $n = shift; return $n if $n < 2; return fib($n - 1) + fib($n - 2); }

That gives you the full sequence. If you just want the end number, replace the foreach loop with:

print fib($ARGV[0]);

(The same surrounding code and optimization works for the Haskell guy’s version as well.)

Blaming Perl for your own lack of ability to write code using the language’s commonly accepted best practices is hardly sporting — especially when the syntactic clarity of the Haskell code to which it’s being compared uses recursion, but the Perl example avoids it in favor of lengthy, complex lines of semi-obfuscated code.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License