Reversing a string of words: C# v Perl V Ruby v Haskell
Recently, the C# programmers at work have been asking job applicants to write a function to reverse a string of words. For example, given an input string of: " one two three four " the function should produce: "four three two one" That is, the input string reversed word by word, with a single space between each word and with no leading or trailing space. (You may assume that the input string consists only of alphabetic characters, spaces and tabs). A popular C# approach goes something like: private static string reverseWords(string str) { string[] words = Array.FindAll<string>(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(); } Though the C# programmers seem happy enough with this solution, it's a bit too verbose for my personal taste. For cheap thrills, I'd like to show them some solutions to their little problem in other, er, less verbose languages. In Perl, I have: sub reverseWords { join ' ', reverse split(' ', shift) } In Ruby: def reverseWords(str) str.split(' ').reverse.join(' ') end Finally, and please don't laugh, in Haskell (GHC): reverseWords :: String -> String reverseWords xs = (concat (intersperse " " (reverse (words xs)))) which does appear to work correctly. However, I would like to do justice to Haskell as a language -- and given that my clumsy Haskell is not written in expert style -- I'm hoping that someone on this list might offer a better, faster, or more idiomatic Haskell solution to this little problem. Thanks, /-\ Send instant messages to your online friends http://au.messenger.yahoo.com
Andrew Savige wrote:
Finally, and please don't laugh, in Haskell (GHC):
reverseWords :: String -> String reverseWords xs = (concat (intersperse " " (reverse (words xs))))
which does appear to work correctly. However, I would like to do justice to Haskell as a language -- and given that my clumsy Haskell is not written in expert style -- I'm hoping that someone on this list might offer a better, faster, or more idiomatic Haskell solution to this little problem.
What about just: reverseWords = concat . intersperse " " . reverse . words -- http://www.metamilk.com
Hi
What about just:
reverseWords = concat . intersperse " " . reverse . words
Dr Haskell says: [http://www-users.cs.york.ac.uk/~ndm/projects/drhaskell.php] "Use unwords instead of concat (intersperse space ...)" Which gives us: reverseWords = unwords . reverse . words Thanks Neil
On 10/12/2006, at 11:51 PM, Neil Mitchell wrote:
Hi
What about just:
reverseWords = concat . intersperse " " . reverse . words
Dr Haskell says: [http://www-users.cs.york.ac.uk/~ndm/projects/drhaskell.php]
"Use unwords instead of concat (intersperse space ...)"
Which gives us:
reverseWords = unwords . reverse . words
Lovely stuff. Just in case you prefer reading left-to-right, another variation is: import Control.Arrow reverseWords = words >>> reverse >>> unwords
On 10/12/2006, at 10:50 PM, Andrew Savige wrote:
A popular C# approach goes something like:
private static string reverseWords(string str) { string[] words = Array.FindAll<string>(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(); }
Yikes! There ought to be a law against public displays of C# which are not accompanied by health warnings. :-) Cheers, Bernie.
Hi
A popular C# approach goes something like:
private static string reverseWords(string str) { string[] words = Array.FindAll<string>(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(); }
Why not: String.Join(" ", words) ? Saves all the hassle with StringBuilder etc. Thanks Neil
--- Neil Mitchell
Why not: String.Join(" ", words) ?
Saves all the hassle with StringBuilder etc.
I agree. The StringBuilder code could be replaced with: Array.Reverse(words); return String.Join(" ", words); However, every response to this question I've seen (admittedly only three or four so far) used StringBuilder. When I ask, "why not use Join?" most C# programmers seem to respond that StringBuilder is "faster" (I haven't measured the difference in performance). To be fair to C#, I'm not a C# expert and haven't asked this question (yet;-) in a public C# forum but StringBuilder seems the "natural" approach of practising C# programmers. Perhaps most practicing Java programmers would similarly reach straight for the StringBuffer hammer? It would be interesting to pose this problem to a Java expert (which is not me). Given their similarities, I would expect a Java and C# solution to this problem to look fairly similar. Cheers, /-\ Send instant messages to your online friends http://au.messenger.yahoo.com
Hi
However, every response to this question I've seen (admittedly only three or four so far) used StringBuilder. When I ask, "why not use Join?" most C# programmers seem to respond that StringBuilder is "faster" (I haven't measured the difference in performance).
I don't know, but I'd be really surprised if Join wasn't implemented in terms of StringBuilder at worst. Possibly it does a summation of the lengths of the String's in the list, and does exactly one allocation, making it much more efficient. Either way, if there is a function in the libraries, you shouldn't be able to write one which is faster! I suspect people saying "use StringBuilder" have read an article on a website telling them that String concat is slow - but haven't thought about the implications... Thanks Neil
the typical good solution to this problem in c or c++ is to use a
string reverse function on the entire buffer, then re-reverse each
word. this leaves multiple spaces correctly embedded in the larger
string.
that approach, of course, won't work in haskell, since it relies on
updates. but if the challenge includes transforming "one two three
four " into " four three two one", how could this be done?
On 12/10/06, Neil Mitchell
Hi
However, every response to this question I've seen (admittedly only three or four so far) used StringBuilder. When I ask, "why not use Join?" most C# programmers seem to respond that StringBuilder is "faster" (I haven't measured the difference in performance).
I don't know, but I'd be really surprised if Join wasn't implemented in terms of StringBuilder at worst. Possibly it does a summation of the lengths of the String's in the list, and does exactly one allocation, making it much more efficient. Either way, if there is a function in the libraries, you shouldn't be able to write one which is faster!
I suspect people saying "use StringBuilder" have read an article on a website telling them that String concat is slow - but haven't thought about the implications...
Thanks
Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Dec 11, 2006, at 18:48 , Steve Downey wrote:
the typical good solution to this problem in c or c++ is to use a string reverse function on the entire buffer, then re-reverse each word. this leaves multiple spaces correctly embedded in the larger string. that approach, of course, won't work in haskell, since it relies on updates. but if the challenge includes transforming "one two three four " into " four three two one", how could this be done?
Off the top of my head, the C++ one translates to: *Main> concatMap reverse . groupBy (\l r -> (l == ' ') == (r == ' ')) . reverse $ "one two three four " " four three two one" There are almost certainly more idiomatic ways to do it, but I'm still learning. -- brandon s. allbery [linux,solaris,freebsd,perl] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
On 12/12/2006, at 11:13 AM, Brandon S. Allbery KF8NH wrote:
On Dec 11, 2006, at 18:48 , Steve Downey wrote:
the typical good solution to this problem in c or c++ is to use a string reverse function on the entire buffer, then re-reverse each word. this leaves multiple spaces correctly embedded in the larger string. that approach, of course, won't work in haskell, since it relies on updates. but if the challenge includes transforming "one two three four " into " four three two one", how could this be done?
Off the top of my head, the C++ one translates to:
*Main> concatMap reverse . groupBy (\l r -> (l == ' ') == (r == ' ')) . reverse $ "one two three four " " four three two one"
There are almost certainly more idiomatic ways to do it, but I'm still learning.
Perhaps something like this is close to the algorithm you describe: import Data.Char (isSpace) rev :: String -> String rev str = revAcc (reverse str) [] where revAcc [] acc = acc revAcc (x:xs) acc | isSpace x = acc ++ (x : revAcc xs []) | otherwise = revAcc xs (x : acc) Cheers, Bernie.
Brandon S. Allbery KF8NH writes:
Off the top of my head, the C++ one translates to:
*Main> concatMap reverse . groupBy (\l r -> (l == ' ') == (r == ' ')) . reverse $ "one two three four " " four three two one"
There are almost certainly more idiomatic ways to do it, but I'm still learning.
Nice. Here is something similar: reverseWords = concat . reverse . groupBy eqsp where eqsp x y = isSpace x == isSpace y Regards, Yitz _._ .._. ___.. _. .... _.. . .__ _... ___.. ... _. _._
On Dec 13, 2006, at 3:54 AM, Yitz Gale wrote:
Nice. Here is something similar:
reverseWords = concat . reverse . groupBy eqsp where eqsp x y = isSpace x == isSpace y
This can be made even nicer using the 'on' function [1]: reverseWords = concat . reverse . groupBy ((==) `on` isSpace) [1] http://www.haskell.org/pipermail/libraries/2006-November/006156.html / Ulf
ulfn:
On Dec 13, 2006, at 3:54 AM, Yitz Gale wrote:
Nice. Here is something similar:
reverseWords = concat . reverse . groupBy eqsp where eqsp x y = isSpace x == isSpace y
This can be made even nicer using the 'on' function [1]:
reverseWords = concat . reverse . groupBy ((==) `on` isSpace)
[1] http://www.haskell.org/pipermail/libraries/2006-November/006156.html
Lambdabot trick(tm), use 'join' in the [] monad, instead of 'concat' join . reverse . groupBy ((==) `on` isSpace) -- Don
ok, i'll bite. why should i prefer join rather than concat in the list
monad. and, moreover, why is this a lambdabot trick?
i suspect that the answer actually has a deep connection to the
'dummies' thread next door. while any program that produces the right
result is correct, there are some that are more correct than others. a
good introductory guide to haskell should lead you in that direction.
reasoning by analogy, for c++, andy koenig's accelerated c++ had a
huge impact on teaching c++ because it didn't start with C or pidgen
c++, but instead required the student to accept that many mechanisms
would be explained later, but that they should be used -now-.
i suspect that being biased towards higher order functions, and
writing new functions such that monads (although the more i learn i
think that should be typeclasses) can take advantage of those
functions, is the skill that needs to be learned / taught. the
equivalent of the central dogma of OO, where it's all about objects
having identity, state , and behavior.
On 12/13/06, Donald Bruce Stewart
ulfn:
On Dec 13, 2006, at 3:54 AM, Yitz Gale wrote:
Nice. Here is something similar:
reverseWords = concat . reverse . groupBy eqsp where eqsp x y = isSpace x == isSpace y
This can be made even nicer using the 'on' function [1]:
reverseWords = concat . reverse . groupBy ((==) `on` isSpace)
[1] http://www.haskell.org/pipermail/libraries/2006-November/006156.html
Lambdabot trick(tm), use 'join' in the [] monad, instead of 'concat'
join . reverse . groupBy ((==) `on` isSpace)
-- Don _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
sdowney:
ok, i'll bite. why should i prefer join rather than concat in the list monad. and, moreover, why is this a lambdabot trick?
Oh, but you shouldn't prefer it! It's obfuscating! It's a trick simply because lambdabot knows the rewriting: 12:16 dons> ?pl reverseWords = concat . reverse . groupBy ((==) `on` isSpace) 12:16 lambdabot> reverseWords = join . reverse . groupBy ((==) `on` isSpace) Refactoring autobots to the resuce!
i suspect that the answer actually has a deep connection to the 'dummies' thread next door. while any program that produces the right result is correct, there are some that are more correct than others. a good introductory guide to haskell should lead you in that direction.
reasoning by analogy, for c++, andy koenig's accelerated c++ had a huge impact on teaching c++ because it didn't start with C or pidgen c++, but instead required the student to accept that many mechanisms would be explained later, but that they should be used -now-.
i suspect that being biased towards higher order functions, and writing new functions such that monads (although the more i learn i think that should be typeclasses) can take advantage of those functions, is the skill that needs to be learned / taught. the equivalent of the central dogma of OO, where it's all about objects having identity, state , and behavior.
Yes, and I think a proper understanding of higher order functions, parametric and bounded polymorphism and monadic computations is sorely lacking in a lot of undergraduate courses. With monads in C#, and parametric polymorphism in Java, I wonder how long it will be before you're expected to understand these concepts to program real world Java/C#/... -- Don
On 13/12/06, Ulf Norell
reverseWords = concat . reverse . groupBy ((==) `on` isSpace)
Didn't equating go in? reverseWords = concat . reverse . groupBy (equating isSpace) -- -David House, dmhouse@gmail.com
Hi Steve,
On 12/11/06, Steve Downey
transforming "one two three four " into " four three two one", how could this be done?
This is a good problem for Parsechttp://www.cs.uu.nl/%7Edaan/download/parsec/parsec.html : import Text.ParserCombinators.Parsec reverseWords = concat . reverse . split where split = fromRight . parse wordsSpaces "" fromRight (Right s) = s wordsSpaces = many (many1 space <|> many1 alphaNum) -Greg
Bernie Pope wrote:
On 10/12/2006, at 10:50 PM, Andrew Savige wrote:
A popular C# approach goes something like:
private static string reverseWords(string str) { string[] words = Array.FindAll<string>(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(); }
Yikes! There ought to be a law against public displays of C# which are not accompanied by health warnings.
*** HNC Haskell News Channel - Headlines *** *** C# can cause code cancer *** Recent investigations by medical experts have shown that certain imperative programming language like C#,C++ and Java have a high risk of developing code cancer. "It has long been suspected that certain language species are more vulnerable to malign code proliferation than others. Yet the full danger has only been discovered as of now and astonishes even myself", says Dr. Haskell, leading expert for code sanity at the Higher Order Health Organisation (HOHO). "Code cancer diagnostics are still evolving these days, see my own research at http://www-users.cs.york.ac.uk/~ndm/projects/drhaskell.php. But when code for trivial problems grows ridiculously large, the diagnosis 'code cancer' is definite." Asked about recovery, Dr. Haskell explains "We currently do not posses a treatment for code cancer. Usually, the only solution is to erase the hard drive and to install a recent distribution of any modern Haskell compiler". Critics claim that the danger of code cancer is well known. Dr. Hylo, free scientist at the Haskell Institute for Healthy Induction (HIHI) http://wiki.di.uminho.pt/wiki/bin/view/Alcino/DrHylo points out that "while one cannot overestimate the well known role of a healthy and strong type system against code cancer as well as bug and virus infestations, this role is well known. On the other hand, the danger of exhaustion by general recursion is far underestimated and the remedy of unfolding the benefits of structural recursion is still under-appreciated. I further recommend to bracket it with eating five bananas a day." Regards, apfelmus, minion of the Haskell Association for Humorous Articles (HAHA)
A popular C# approach goes something like: private static string reverseWords(string str) { [...]
Yikes! There ought to be a law against public displays of C# which are not accompanied by health warnings.
Oh come on. if someone had bothered to abstract out string splits and string joins as separate functions it wouldnt be all that horrid..
Bernie.
Tim Newsham http://www.thenewsh.com/~newsham/
On Sun, Dec 10, 2006 at 10:50:38PM +1100, Andrew Savige wrote:
Finally, and please don't laugh, in Haskell (GHC):
reverseWords :: String -> String reverseWords xs = (concat (intersperse " " (reverse (words xs))))
which does appear to work correctly. However, I would like to do justice to Haskell as a language -- and given that my clumsy Haskell is not written in expert style -- I'm hoping that someone on this list might offer a better, faster, or more idiomatic Haskell solution to this little problem.
reverseWords = unwords . reverse . words -- David Roundy Department of Physics Oregon State University
participants (14)
-
Andrew Savige -
apfelmus＠quantentunnel.de -
Bernie Pope -
Brandon S. Allbery KF8NH -
Brian Hulley -
David House -
David Roundy -
dons＠cse.unsw.edu.au -
Greg Fitzgerald -
Neil Mitchell -
Steve Downey -
Tim Newsham -
Ulf Norell -
Yitz Gale