WordCount in Haskell

user_14664028 0
Viewed 142

I'm trying to count the amount of occurences of every word in a text to then represent it as a list of tuples.

I've tried by using an accumulator and I've tried by using the concat and filter. What occurs to be the problem is that I'm not sure how to deal with lists inside a list.

I'm not sure how to continue from here, I tried to call the function wordCountt using filter (x /=) on the argument but that wouldn't run for some reason. Would really appreciate some guidance here.

Cheers

type Document = [Sentence]
type WordTally = [(String, Int)]

wordCountt :: Document -> WordTally
wordCountt [] = []
wordCountt [(x:xs), ys] = [(x, length (filter (x ==) (concat [(x:xs), ys])))] ++ wordCountt [xs, ys]```



```wordCountt [["a", "rose", "is", "a", "rose"],["but", "so", "is", "a", "rose"]]
[("a",3),("rose",3),("is",2),("a",2),("rose",2)*** Exception: CompLing.hs:(60,1)-(61,100): Non-exhaustive patterns in function wordCountt```
filter list haskell
2 Answers

For making histograms, I always liked Map.fromListWith:

import qualified Data.Map.Strict as Map
import           Data.Map (Map)

histogram :: Ord a => [a] -> Map a Int
histogram xs = Map.fromListWith (+) (zip xs (repeat 1))

The way it works:

> zip (words "a rose is a rose") (repeat 1)
[("a",1),("rose",1),("is",1),("a",1),("rose",1)]

> Map.fromListWith (+) [("hello",1),("hello",1)]
fromList [("hello",2)]

> Map.fromListWith (+) [("a",1),("rose",1),("is",1),("a",1),("rose",1)]
fromList [("a",2),("is",1),("rose",2)]

> histogram (words "a rose is a rose")
fromList [("a",2),("is",1),("rose",2)]

So when the same word occurs in two (word, count) tuples, the counts get +'ed.

user_2359080

I think you try to do too much in a single function. This means the function is harder to implement, debug, and perhaps most important, convincing yourself that it works.

We can split the function into two parts:

  1. a function that adds a given element to a WordTally; and
  2. a function that enumerates over all the words of the documents and keeps updating the WordTally.

The update function will look like:

addWord :: WordTally -> String -> WordTally
addWord = …

thus function thus takes a WordTally and a String. If the String ready is a "member" of the wordcount, then you increment the count, otherwise we add this with one. You can use explicit recursion for this.

Then the wordCountt is a fold-pattern on this. Indeed, we can make use of:

wordCountt :: Document -> WordTally
wordCountt d = foldl addWord [] (concat d)

or shorter:

wordCountt :: Document -> WordTally
wordCountt = foldl addWord [] . concat

We thus start with an empty list as WordTally, and each time add a element from the list of lists of a document and update the WordTally accordingly, until we reach the end of the words.

This will however not be very efficient, since updating the WordTally list, will take O(n) per word, and thus make this an O(n2) algorithm. You can (later) look at Map for example, which is a container that can insert/update in O(log n).

user_675790
Related