Posts Tagged ‘in’

Programming Praxis – Reverse Words

March 8, 2011

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.