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’.


  1. Somehow I feel that you want me to leave a comment.

    Splices in Python do have weird syntax. As of Python 2.4 (released 2004 November 30th), there is an iterator function, “reversed”, which makes this particular task much more compact.

    I personally find great joy in this version, because it uses list comprehension:

    def reverseWords(words):
       return ' '.join([ x for x in reversed(words.split()) ])

    I don’t think it gets much more elegant than this:

    def reverseWords(words):
       return ' '.join(reversed(words.split()))

    but you can get a one-liner using a lambda:

    reverseWords = (lambda words: ' '.join(reversed(words.split())))

    All of those parentheses are starting to look almost lispish.

    (code blocks edited for clarity by apotheon)

    Comment by scoth — 15 December 2006 @ 12:25

  2. The

    reverseWords = (lambda words: ' '.join(reversed(words.split())))

    didn’t show up with so much whitespace in the preview! Have I mentioned recently that this blogging software does really odd things with code blocks in comments?

    (code block edited for clarity by apotheon)

    Comment by scoth — 15 December 2006 @ 12:30

  3. Frankly, I was surprised at the fugly syntax for the Python examples I saw. It’s kind of a relief to see you provide much, much prettier examples. In fact, your examples look surprisingly like the Perl and Ruby examples — moreso than I would have expected.

    In any case, I really figured that Perl, Python, and Ruby would all be about equivalent in elegance of the solution, and the Python examples in the PerlMonks thread didn’t fit that expectation at all. The Perl 6 stuff, on the other hand, blew me away. The first of Larry’s three examples in particular is quite nice (the third is a bit cryptic at first glance).

    It occurs to me that the original Perl example might actually be prettier if presented as a one-line subroutine:

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

    I’m still undecided about whether it looks better or worse that way. I guess it may depend on the code around it.

    Anyway, whether you’ve mentioned it or not, I’m quite aware that the way the comments functionality handles code is a little sketchy from time to time. It’s kind of annoying, but there really isn’t any weblogging software that’s as good in general as WordPress that I’ve seen thus far. I may take a whack at coming up with something I like more and does less damage to comments by writing it from scratch at some point, but not today.

    By the way, I edited your code blocks to make them appear correctly (I think).

    Comment by apotheon — 15 December 2006 @ 12:47

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

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