Programming Praxis – Reverse Words

In today’s Programming Praxis exercise, we’re revisiting the well-known interviewing problem of reversing the words in a string. This time, we have to do the reversal in place and without using any library functions for determining the words. Let’s get started, shall we?

Haskell doesn’t do much in the way of in-place modifications by default. Attempting to modify a string (or indeed the majority of all data structures) will create a copy of it (though part of the new one may refer to same memory occupied by the original). I figured the closest thing to modifying the string in place would be to turn it into a mutable array. It’s not entirely in-place since we still have to convert to and from the array, but it’s the closest we’re going to get.

import Data.Array.IO

We start with a function to switch to characters in a string.

switch :: (MArray a e m, Ix i) => i -> i -> a i e -> m ()
switch i j a = do x <- readArray a i
                  writeArray a i =<< readArray a j
                  writeArray a j x

Next, we make a function to reverse part of a string.

revRange :: Int -> Int -> IOArray Int a -> IO (IOArray Int a)
revRange i j a = mapM_ (\n -> switch n (j+i-n) a) [i..div (i+j) 2] >> return a

The algorithm for reversing the words in a string is the same as in the Scheme version: reverse the entire string, then reverse the individual words.

reverseWords :: String -> IO String
reverseWords xs = do a <- newListArray (0, length xs - 1) xs
                     (s,e) <- getBounds a
                     f 0 e =<< revRange s e a where
    f i e a = if i > e then getElems a else nextSpace i e a >>=
                 \s -> f (s+1) e =<< revRange i (s-1) a
    nextSpace i e a = if i > e then return i else readArray a i >>= \c ->
                      if c == ' ' then return i else nextSpace (i+1) e a

Let’s see if everything is working properly:

main :: IO ()
main = do let a =? b = print . (== b) =<< reverseWords a
          "" =? ""
          " " =? " "
          "  " =? "  "
          "hello" =? "hello"
          "hello " =? " hello"
          " hello" =? "hello "
          "the quick brown fox" =? "fox brown quick the"
          "the quick  brown fox" =? "fox brown  quick the"
          "the quick  brown 42 fox!" =? "fox! 42 brown  quick the"

Yup. Having to do things in place does make the code a lot longer than the original solution though.

About these ads

Tags: , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: