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: /(?
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.
lamby
First attempt at Prolog is:
06 Sep 2008, 00:20
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.