September 06, 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;
        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;
        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.

- 2 comments by 0 or more people Not publicly viewable

  1. lamby

    First attempt at Prolog is:

    balanced(X) :- balanced(X, []).
    balanced([], []) :- true.
    balanced([H|T], [H|Ts]) :- balanced(T, Ts).
    balanced(['['|T], S) :- balanced(T, [']'|S]).
    balanced(['('|T], S) :- balanced(T, [')'|S]).

    06 Sep 2008, 00:20

  2. Tony Morris

    The point was missed by yourself and many others it seems. I apologise for my failure in this regard.

    “Anyone who uses “uncurry (flip (,))” is thinking backwards about a problem.”
    This is a false statement.

    30 Oct 2008, 23:17

Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.

September 2008

Mo Tu We Th Fr Sa Su
Aug |  Today  | Oct
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30               

Search this blog



Most recent comments

  • Apart from the plea "can I have your old one?" (the yearning never diminishes) I'd like to leave you… by Sue on this entry
  • Unfortunately I still haven't seen a film for which you have to read up on quantum mechanics as I mi… by Sue on this entry
  • I've never been to watch a film before when it's been recommended that you first read up on quantum … by Sue on this entry
  • Well this is very interesting, i really liked reading this blog, this was very informative and very … by Mio Navman Spirit S300 on this entry
  • I thought it was fascinating. Griffin isn't like any other, media–trained, polished politician, and … by Tim on this entry

Blog archive



Not signed in
Sign in

Powered by BlogBuilder