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: bonsai, code, Haskell, index, kata, permuted, praxis, programming