Reversing a String in Scala
So I’ve been reading “Programming in Scala” by Martin Odersky, Lex Spoon and Bill Venners and I’ve been coming up with ways to get myself thinking and programming more in Scala. Since I spent a better part of my week interviewing people I thought I’d take some time to write the famous “Reverse a String” interview question. This is a pretty straight forward thing to do and thought it would be fun to experiment with some of Scala’s other cool features to get my feet wet.
On my first attempt I wound up with my usual tail-recursive implementation that makes use of an accumulator.
/** * Wrapper function. */ def reverse(str: String) : String = { if ((str == null) || (str.length() <= 1)) str reverse(str, "") } /** * tail call recursive with accumulator */ def reverse(str: String, acc: String) : String = { if (str.length() == 0) acc else reverse(str.substring(1), str.charAt(0) + acc); }
This seemed pretty standard to me. It doesn’t differ much from the Java implementation I’ve written a hundred times, nor is it really all that interesting. I decided to jump ahead a few chapters in the book to see what I could accomplish using a left fold. For those unfamiliar with what a fold left operation is I point you to the Wikipedia entry on it here. The basic idea as stated in the book ”Programming in Scala“ is this: “A fold left operation (z /: xs) (op) involves three objects: a start value z, a list xs, and a binary operation op. The result of the fold is op applied between successive elements of the list prefixed by z.”
Ok that seems like it applies very well to what we are trying to accomplish. Rewritting the above methods into one clean line of Scala code yielded the following
/** * This will fold the list left, and should run in constant time allocation */ def reverseLeft[T](xs: List[T]) = (List[T]() /: xs) {(ys, y) => y :: ys}
Pretty beautiful isn’t it? It’s amazingly simple and achieves the same thing as the tail-recursive implementation. I can’t express how excited I am to get through this book and really start doing real programming with Scala.
So I guess the next time you go for an interview try and remember this for the answer and see how the interviewers faces light up, either with glee or rage that you didn’t solve it using the standard recursive implementation
Until next time …
