2
\$\begingroup\$

I'm just starting out in Haskell and have been set an assignment for uni where I have to create a reverse index of words in a text file and find what line numbers they appear on. I also have to remove any stop words like "the" or "and" that aren't needed.

So far I have this, but I feel that there should be a better way to remove duplicates from a list and to filter by non-letters:

module Main where
import qualified Data.List as List
import qualified Data.Char as Char
import qualified Data.Set as Set
import qualified Data.Maybe as Maybe

main = do
    -- load file to be indexed and stop words
    text <- readFile "test.txt"
    stopWords <- readFile "stopWords.txt"

    -- convert all chars to lower case, split by lines, then split by words
    let word = map words (lines (map Char.toLower text))
    let stopWord = map words (lines (map Char.toLower stopWords))

    -- concatenate lists, remove non letters, then remove any empty list elements
    let word' = filter (not.null) (map (filter Char.isLetter) (concat word))
    let stopWord' = filter (not.null) (map (filter Char.isLetter) (concat stopWord))

    -- cast both lists to a set to remove duplicates and remove any instances of stopWord' from word'
    let index = Set.toList (Set.difference (Set.fromList word') (Set.fromList stopWord'))

    -- get line numbers from indexed words
    let lineNumbers = generateIndex index word

    -- zip index of words with line numbers and print
    mapM print (List.zip index lineNumbers)

generateIndex :: [String] -> [[String]] -> [[Int]]
generateIndex xs y = foldr (\ x -> (++) [getLineNumbers x y]) [] xs

getLineNumbers' :: String -> [[String]] -> Int -> [Int]
getLineNumbers' x [] n = []
getLineNumbers' x (y:ys) n
    | x `elem` y = n : getLineNumbers' x ys (n + 1)
    | otherwise = getLineNumbers' x ys (n + 1)

getLineNumbers :: String -> [[String]] -> [Int]
getLineNumbers x y = getLineNumbers' x y 1
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Think carefully about what data structure you're using, lists aren't always the best choice. In this case you need to do two major things with your words.

  1. Associate words with the line number they first appear on.
  2. Remove words from one group using entries from another.

Right off the bat whenever you need to associate one set of elements with another, you should think of a map. In Haskell, you'll want to look at the documentation for Data.Map.

By reordering and reconsidering the operations you're performing on lists and sets, you should be able to rewrite your code to use maps and significantly cut down the amount of code you have written and end up with something more expressive too.

As it isn't clear that you've actually turned in this assignment I'm afraid I'll have to be coy, but here's the most pointed help I can give you on your specific questions.

Regarding removing duplicate words, the trick is to rely on the fact that maps can only contain a given key once. Pay close attention to the various ways of constructing a list that are specified in the documentation for Data.Map.

Filtering out the non-letters in a string doesn't get much simpler than filter Char.isLetter in your code above. The dissatisfaction you are feeling might be because of the gross duplication between the definitions of word and stopWord, and word' and stopWord'. Any time you have two lines in Haskell that are identical but for the value you're operating on, your code is crying out for a new function definition.

Your code is lingering in IO far more than is necessary, pull the pure data manipulating machinery out into separate functions. To start you off, knowing no more than the type signatures I've given here, what do you think these functions do? What part of your code do they replace? Take a shot at defining them.

normalize :: String -> String
??? :: [a] -> [(a, Int)]
??? :: String -> [([String], Int)]
\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the suggestions. I've made a normalize function like you suggested which took out a few messy lines of code and has made it a bit more readable. In terms of using a map to not allow duplicates, what's the difference between that and a set like I've used? A set won't allow duplicates either. I could be wrong, but I haven't found a way of having a list of Ints inside a map which is needed for an index \$\endgroup\$ May 7, 2014 at 13:02
  • \$\begingroup\$ The trick (and it's a little tricky) is to leverage one of the ways of constructing a Map to achieve both de-duping and associating words with the first line number they appear on at once. Check out fromListWith (and maybe insertWith to understand its semantics). \$\endgroup\$
    – bisserlis
    May 7, 2014 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.