6
\$\begingroup\$

I have written a program to process Google 1-Gram dataset in order to obtain the list of most frequent words. This is my second more or less working program in Haskell, so I really want to know if it complies with current Haskell best practices.

I want to hear any your thought about virtually anything: performance, coding style, naming, even grammar and spelling in comments.

-- This script processes Google N-Gram dataset to obtain the list of the most
-- frequent words sorted by their frequency descending.
--
-- Usage example:
--     $ zcat googlebooks-eng-all-1gram-20120701-{a..z}.gz |
--       ./ProcessGoogleDataset 1950 5000 "$(echo {a..z})" > result.txt
--
-- where 1950 means to filter out only records newer then year 1950,
--       5000 means number of the most frequent words to collect,
--       {a..z} means the list of letters allowed in words.
--
-- Copyright (c) 2015, Pavel Kretov.
-- Provided under the terms of Apache 2.0 License.
import Control.Monad.IO.Class (liftIO)
import Data.Char              (isSpace, isLower)
import Data.Function          (on)
import Data.List              (foldl', sortBy, groupBy, partition)
import Data.List.Ordered      (mergeBy)
import Data.Maybe             (fromJust)
import Data.Ord               (comparing)
import Data.Tuple             (swap)
import System.Environment     (getArgs)
import System.IO              (stdin, stdout)

-- Heap seems convenient for finding most frequent items.
import qualified Data.Heap           as H

-- Use Conduit package for IO as it has proven to be faster
-- then built-in (lines . readFile) approach.
import Data.Conduit           (($$), (=$))
import qualified Data.Conduit.Text   as CT
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.List   as CL
import qualified Data.Conduit.Lazy   as CZ

-- Conduit thinks Data.Text is better then plain strings.
import qualified Data.Text           as T
import qualified Data.Text.Read      as TR

-- Conduit really insists on that for lazy IO.
import Control.Monad.Trans.Resource (runResourceT)

-- Parses input 'str' into integer value. Produces an error if string
-- cannot be parsed successfully.
parseInt :: T.Text -> Int
parseInt str = case TR.decimal str of
                   Left errorText -> error errorText
                   Right (val, _) -> val

-- Parses a line of raw input into a tuple of word, year, and frequency.
-- Produces an error if line cannot be parsed successfully.
parseEntry :: T.Text -> (T.Text, Int, Int)
parseEntry line = (word, parseInt year, parseInt freq)
    where [word, year, freq, _] = T.words line

-- Filters away entries older then 'year'.
filterByYear :: Int -> [(T.Text, Int, Int)] -> [(T.Text, Int, Int)]
filterByYear year = filter (\(w,y,f) -> y >= year)

-- Removes year component from the input tuple.
removeYears :: [(T.Text, Int, Int)] -> [(T.Text, Int)]
removeYears = map $ \(w,y,f) -> (w,f)

-- Original dataset contains additional qualifiers as underscore suffices,
-- something like "_NOUN" or "_ADJ". This function removes them.
removeSuffices :: [(T.Text, Int)] -> [(T.Text, Int)]
removeSuffices = map (\(word, f) -> (truncateUnderscore word, f))
    where truncateUnderscore = T.takeWhile (\c -> c /= '_')

-- Filter away entries where word contains non-alphabetic characters. The list
-- of characters comprising the aplabet is given as argument. Note that
-- character case matters for comparison.
filterAlphabetic :: [Char] -> [(T.Text, Int)] -> [(T.Text, Int)]
filterAlphabetic alphabet =
    filter (\(word, f) -> T.all (`elem` alphabet) word)

-- Summs frequencies for all consecutive tuples with same word.
aggregateByWord :: [(T.Text, Int)] -> [(T.Text, Int)]
aggregateByWord xs = id
     $ map (foldl (\(w,f) (w',f') -> (w',f+f')) (T.empty,0))
     $ groupBy ((==) `on` fst) xs 

resortByFirstLetter :: [(T.Text, Int)] -> [(T.Text, Int)]
resortByFirstLetter = id
     . concatMap (sortBy (comparing fst))
     . groupBy   ((==) `on` (T.head . fst))

-- Naive 'mostFreq' implementation. It is not actually used in this program
-- and left just for reference.
naiveMostFreq :: Int -> [(T.Text, Int)] -> [(T.Text, Int)]
naiveMostFreq n xs = take n $ sortBy (flip $ comparing snd) xs 

-- Optimized implementation of 'naiveMostFreq'. This function takes most
-- frequent items from the input list. 
-- http://stackoverflow.com/a/31348931/1447225
mostFreq :: Int -> [(T.Text, Int)] -> [(T.Text, Int)]
mostFreq n dataset = final
  where
    pairs = map swap dataset
    (first, rest) = splitAt n pairs
    start = H.fromList first :: H.MinHeap (Int, T.Text)
    stop  = foldl' step start rest
    step heap pair = if H.viewHead heap < Just pair
                         then H.insert pair (fromJust $ H.viewTail heap)
                         else heap
    final = map swap (H.toList stop)
    swap ~(a,b) = (b,a)

formatOutputLine :: (T.Text, Int) -> T.Text
formatOutputLine (word, freq) =
    T.concat [word, T.pack "\t", T.pack $ show freq, T.pack "\n"] 

main :: IO ()
main = runResourceT $ do
    -- Parse command line parameters. Note that all whitespace characters are
    -- filtered away from 'aplphabet' parameter for user convenience.
    args <- liftIO getArgs
    let year     = parseInt (T.pack $ args !! 0)
    let limit    = parseInt (T.pack $ args !! 1)
    let alphabet = filter (not . isSpace)
                                     (args !! 2) 

    -- Read lines from STDIN as a lazy list.
    -- Note here that UTF-8 is hardcoded.
    rawLines <- CZ.lazyConsume
            $ CB.sourceHandle stdin
           =$ CT.decodeUtf8
           =$ CT.lines

    -- Do actual processing.
    let result = id
            $ sortBy (flip $ comparing snd)
            $ mostFreq limit
            $ aggregateByWord
            $ resortByFirstLetter
            $ aggregateByWord
            $ filterAlphabetic alphabet
            $ removeSuffices
            $ removeYears
            $ filterByYear year
            $ map parseEntry rawLines

    -- Write result to STDOUT.
    CL.sourceList (map formatOutputLine result)
           $$ CT.encodeUtf8
           =$ CB.sinkHandle stdout

You may download source dataset by the following command, but note that it's quite large (about 4.5 GB in compressed form).

$ wget http://storage.googleapis.com/books/ngrams/books/googlebooks-eng-all-1gram-20120701-{a..z}.gz
\$\endgroup\$
2
\$\begingroup\$

Here are only general thoughts about your code (it doesn’t talk about optimization, or data structures)

Code organisation

I would say it’s time to split your code: you have 19 imports and it becomes hard to know which part of your program requires which library.

You need to separate input/output code, argument handling and data processing. It will allow you to write unit tests more easily.

Comments

Avoid -- Do actual processing comments style. It doesn’t tell anything about the code itself, it just helps the developper to know where she/he is, which a good organisation of the code would have tell him/her.

When commenting functions, describe the arguments and what the function returns (the Haddock documentation will give some hint).

The naive mostFreq implementation code should be put in comments if it is not used.

Code style

Why don’t you use Haddock when commenting your code ? It even allows you to put small tests for QuickCheck.

I’m not a fan of your use of id just to make your code look better. Code should do something.

Hlint advices:

  • ProcessGoogleDataset.hs:67:23: Warning: Use first

    Found:
      \ (word, f) -> (truncateUnderscore word, f)
    Why not:
      Control.Arrow.first truncateUnderscore
    
  • ProcessGoogleDataset.hs:68:45: Warning: Avoid lambda

    Found:
      \ c -> c /= '_'
    Why not:
      (/= '_')
    
  • ProcessGoogleDataset.hs:73:21: Warning: Use String

    Found:
      [Char] -> [(T.Text, Int)] -> [(T.Text, Int)]
    Why not:
      String -> [(T.Text, Int)] -> [(T.Text, Int)]
    
  • ProcessGoogleDataset.hs:118:39: Warning: Use head

    Found:
      args !! 0
    Why not:
      head args
    

There are many (T.Text, Int) and (T.Text, Int, Int). It would help to define types (even type synonyms) to make it clear of what data they hold.

Program behaviour

Since your program will be run as a command line program, I think it should behave like a standard command line utility.

For example, it should have a help option, handle incorrect parameter, setting the return code, work with standard files (not only standard input) etc.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I cannot write a detailed answer right now, but many thanks for pointing me to hlint program. I should have definitely checked it out by myself before posting the code. \$\endgroup\$ – firegurafiku Aug 4 '15 at 20:03
  • \$\begingroup\$ I don't agree with each of your advice. For example, I mind splitting the program into two files as I want to have several one-file scripts in a single directory. And I really like using id to make $ align. The rest of your notes are quite reasonable, I'll try to incorporate them into my code. Thank you for reviewing! \$\endgroup\$ – firegurafiku Aug 6 '15 at 22:24
  • \$\begingroup\$ Keeping the script as one file can be heard in the case it is really used as a script (launched directly from the command line without compiling it to an executable). In this case, you could place a shebang at the beginning of your code like #!/usr/bin/runhaskell (the runhaskell executable should be located in a commonly used place). It would make it clear they are meant to be scripts and not compiled. \$\endgroup\$ – zigazou Aug 7 '15 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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