Programming Praxis – Permuted Index

In today’s Programming Praxis exercise we have to implement David Parnas’ permuted index system. Let’s get started.

We’re going to need some imports.

import Data.Char
import Data.List
import qualified Data.List.Key as K
import Text.Printf

We start by defining the list of stop words:

stopList :: [String]
stopList = words "a an and by for if in is of on the to"

Creating all the rotations of a line can be done with a simple list comprehension.

rot :: [String] -> [(String, String)]
rot xs = [(unwords a, unwords b) | (a, b) <- init $
          zip (inits xs) (tails xs), notElem (head b) stopList]

To print the index, we check how big the longest pre- and postfixes are and pad the others accordingly.

prettyPrint :: [(String, String)] -> IO ()
prettyPrint xs = mapM_ (\(a, b) -> printf "%*s   %-*s\n" l1 a l2 b) xs
    where l1 = maximum $ map (length . fst) xs
          l2 = maximum $ map (length . snd) xs

The only step left is to put all the rotations in the correct order.

permuteIndex :: String -> IO ()
permuteIndex = prettyPrint . K.sort (\(_, x) -> (map toLower x, x)) .
               concatMap (rot . words) . lines

A quick test shows that we get the correct output:

main :: IO ()
main = permuteIndex $ "All's well that ends well.\n" ++
                      "Nature abhors a vacuum.\n" ++
                      "Every man has a price.\n"

Making it work with files or console input is merely a matter of binding the result of readFile or getContents to permuteIndex.

About these ads

Tags: , , , , , , ,

One Response to “Programming Praxis – Permuted Index”

  1. I. J. Kennedy Says:

    Your praxes are very helpful. Thanks for posting them.

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: