All entries for Saturday 06 September 2008

Straw Men burn easily

Tony Morris posted an article to his blog giving an example program. The blog title predicates a comparison between languages on one example. This is sensible if one does it infinitely often, and aggregates the results, unfortunately in order to effectively compare languages one must be fair with the examples from each language. I dislike the style in which the haskell/scala/functionaljava examples were written – trying to be far too clever. Anyone who uses “uncurry (flip (,))” is thinking backwards about a problem: Pun intended!

I asked in the wuglug IRC channel if anyone had any more interesting solutions to the problem. I haven’t seen any other algorithm that isn’t either based on the stack, or repeatedly deleting matching pairs of brackets. Faux came up with:

private static boolean parse(String test)
{
    int prev;
    do
    {
        prev = test.length();
        test = test.replaceAll("\\(\\)", "").replaceAll("\\[\\]", "");
    } while (test.length() != prev);

    return test.length() == 0;
}

Its incredibly easy to see intent in this code, and it can be easily generalised according to Mr. Morris’ comparison by abstracting ”\\(\\)” etc. into an array and wrapping a for loop around it:

private static String[] pairs = {"\\(\\)", "\\[\\]"};
private static boolean parse(String test)
{
    int prev;
    do
    {
        prev = test.length();
        for(String pair:pairs)
            test = test.replaceAll(pair, "");
    } while (test.length() != prev);

    return test.length() == 0;
}

Lamby provided the awesome regex: /(? (\((?>(?&r))\))|([(?>(?&r))\]))*/ . This is completely unreadable, however, it is very neat, and could be reasonably commented. In my opinion it is no harder to read than Mr. Morris’ Haskell.

As someone who does rather like the Haskell programming language, I felt it would be interesting to come up with an example in that. The stack based algorithm is more efficient being O(n), rather than O(n^2) – so I decided to play around with that. Its very prology, and might be better written in that language.

parse x = stack x []
stack [] [] = True
stack ('(':x) y = stack x ('(':y)
stack ('[':x) y = stack x ('[':y)
stack (')':x) ('(':y) = stack x y 
stack (']':x) ('[':y) = stack x y 
stack _ _ = False

In comparison with the original Haskell example, this imports nothing outside of prelude, is
(in my opinion) easier to understand, is probably faster – since it uses very simple recursion – and is 8 characters shorter. If anyone has a better solution that doesn’t use a parser generator, and preferably makes minimal use of libraries.

: 06 Sep 2008 00:13 |  Tags: Reflections |  Comments (2) |  Close comments |  Report a problem