Finding duplicated entries

Question

Since the Esteemed Academia wants me to learn Haskell, and Haskell seems just weird for me, I thought that to train some basic Haskell skills I'd write a simple script I now need in Haskell.

This is what the script is supposed to do... I have a file that looks like this:

oo R
j
j ai            I'm a comment
kd oo
stack j
a

I needed to extract duplicated elements from this file with lines they appear on. The catch is that the tab character denotes comments; so I'm a comment should not be considered here and in particular, this a from I'm a comment should not match this a that appears as the last element from these sample lines.

If fed this particular sample file, my script should report finding duplicate elements: oo on lines 1 and 4 and j on lines 2, 3 and 5. I believe I wrote a script that does this correctly.

Here it is:

import qualified Data.Map as Map
import Data.List
import Data.Function

main = do
  input <- fmap preprocess getContents
  printDupes $ findDupes input

preprocess input = let
    untabbedLines = map (takeWhile (/= '\t')) $ lines input
    wordsedLines = map words untabbedLines
    numberedLines = zip wordsedLines [1..]
    numberedWords = concat $ map indexDown numberedLines where
      indexDown (words', index) = map (flip (,) $ index) words'
  in numberedWords

findDupes entries = let
    occurences = Map.fromListWith (flip (++)) $ map (fmap (:[])) entries
  in Map.filter ((>1).length) occurences

printDupes :: Map.Map String [Int] -> IO()
printDupes dupes = let
    showPositions positions = intercalate ", " $ map show positions
    printDupe (dupe, positions) = putStrLn $ "Duplicated element " ++ dupe ++ " found on positions: " ++ showPositions positions
  in let
    sortedDupes = sortBy (compare `on` snd) $ Map.assocs dupes
  in mapM_ printDupe sortedDupes

The task is simple, but I guess it's OK for learning how to code in Haskell...

So could you kindly review this self-imposed exercise? What could've been done better than I did? Simpler? Shorter? I'm sure much, but what precisely? Also how to improve readability?

Answer 1

It can be helpful to run hlint to see if it spots some improvements. In this case, it notes that:

• you can replace concat $ map with concatMap on line 13
• you can replace flip (,) $ index with (,index) on line 14 if you enable the TupleSections extension, or at least drop the dollar sign if you don't

A few additional things it misses are:

• you can drop the in let on line 25
• you can replace sortBy (compare `on` snd) with sortOn snd in line 26

It's also generally accepted as good practice to put type signatures on top-level functions. You may feel it looks cluttered, but it really helps others understand your programs. For example, I had to add them before I started working on your program, just so I could figure out what was going on.

A larger stylistic issue is that idiomatic Haskell code typically doesn't create a lot of bindings for intermediate results that are only used once. I suspect that you've gone this route (labelling untabbedLines and wordsedLines, etc.) for two reasons -- first, you're probably more used to an imperative programming style that lays out an algorithm as a series ordered steps, and all these bindings are helping you think through the process ("first, I remove the tabbed comments, second I make the lines into words, third I number them, etc., etc.); second, you may be using it as a kind of self-documenting coding style, but I think comments make better documentation than awkward camelcase pseudonouns like wordsedLines.

So, a more usual way of writing your preprocess would be:

preprocess input
  = concatMap indexDown
  $ flip zip [1..]
  $ map words
  $ map (takeWhile (/= '\t'))  -- comments start with tab
  $ lines input
  where
    -- number each word on the line with the index
    indexDown (words', index) = map (,index) words'

Howoever, it's also pretty standard replace the pattern foo x = f $ g $ h $ k x with the point-free form foo = f . g . h . k. It's possible to get carried away with point-free code, but this particular transformation is pretty routine. Some people might prefer to collapse the map over the lines, too:

preprocess
  = concatMap indexDown
  . flip zip [1..]
  . map (words . takeWhile (/= '\t'))
  . lines
  where
    -- number each word on the line with the index
    indexDown (words', index) = map (,index) words'

Also, in situations like this with maps at multiple levels (lines and words), it's worth considering if a list comprehension might not be easier to understand:

preprocess' :: String -> [(String, Int)]
preprocess' input =
  [ (w, i)
  -- get each numbered line of words
  | (i, ws) <- zip [1..]
               $ map (words . takeWhile (/= '\t'))
               $ lines input
  -- and process each word
  , w <- ws ]

A similar consideration applies to findDupes. It would be more usual to collapse it into a single functional pipeline in point-free form:

findDupes :: [(String, Int)] -> Map.Map String [Int]
findDupes = Map.filter ((>1) . length)
          . Map.fromListWith (flip (++))
          . map (fmap (:[]))

However, I think map (fmap (:[])) is probably too clever by half. At the very least, it would be clearer to import second from Data.Bifunctor and write map (second (:[])), though even better would be to just use a lambda which makes the intended transformation clear at a glance:

map (\(w,i) -> (w,[i]))

A rewrite of printDupes would probably look like:

printDupes :: Map.Map String [Int] -> IO ()
printDupes dupes =
  forM_ (sortOn snd $ Map.assocs dupes) $ \(w, idxs) ->
    putStrLn $ "Duplicated element " ++ w ++
               " found on positions: " ++
               (intercalate ", " $ map show idxs)

(Here, forM_ comes from Control.Monad and is just a flipped version of mapM_.)

One additional stylistic issue regards your handling of IO. Here, the main function is responsible for actually performing input and then calls on a pure function to perform the processing. When it comes time to generate output, though, it passes off that responsibility to another function. Haskell programs are usually carefully organized around their IO, with a clear division of responsibility between the IO and the pure processing, and it's usual to have input and output all handled at the same "level". I realize that sounds a little fuzzy and hand-wavy, but it boils down to this -- it would be more usual to localize input and output in main and have the remainder of the program (including printDupes) be pure. So, printDupes would instead look something like:

printDupes :: Map.Map String [Int] -> String
printDupes =
  unlines . map render . sortOn snd . Map.assocs
  where render (w,idxs)
          = "Duplicated element " ++ w ++
            " found on positions: " ++
            intercalate ", " (map show idxs)

I also personally find it a little odd that findDups takes a list [(String,Int)] but then returns a Map String [Int]. The Map seems like an implementation detail, and it "feels" like the function ought to return a [(String,[Int])], and it might as well sort this list while it's at it.

Anyway, with all those changes and some renaming of functions, the final program might look like:

{-# OPTIONS_GHC -Wall #-}

import qualified Data.Map as Map
import Data.List

main :: IO ()
main = interact (renderDups . findDups . getWords)

getWords :: String -> [(String, Int)]
getWords input =
  [ (w, i)
  | (i, ws) <- zip [1..]
               $ map (words . takeWhile (/= '\t'))
               $ lines input
  , w <- ws ]

findDups :: [(String, Int)] -> [(String, [Int])]
findDups = sortOn snd . Map.assocs
         . Map.filter ((>1) . length)
         . Map.fromListWith (flip (++))
         . map (\(w,i) -> (w,[i]))

renderDups :: [(String, [Int])] -> String
renderDups = unlines . map render
  where render (w,idxs)
          = "Duplicated element " ++ w ++
            " found on positions: " ++
            intercalate ", " (map show idxs)