Google Code Jam - Alien Language I've successfully solved the Alien Languages problem for Google Code Jam in Haskell:

The algorithm is trivial - turn the patterns into regular expressions and see how many of the known words match these expressions.

But - this has taken me far longer than I expected it to, and most of the time I was battling with getting my types correct. Which leaves me wondering whether there is something wrong with my understanding of functional programming.

module Main where

-- http://code.google.com/codejam/contest/90101/dashboard#s=p0
-- Input and output with standard redirection operators

-- Unless otherwise indicated, all modules used are either bundled with
-- the Haskell Platform (http://hackage.haskell.org/platform/) or available
-- as a separate download from Hackage (http://hackage.haskell.org/).

import Data.List
import Text.Regex.Posix
import Data.String.Utils

numberOfMatches :: String -&gt; [String] -&gt; Int
numberOfMatches pattern = foldl' matches 0
  where
    matches acc word = if word =~ pattern' :: Bool
                           then acc + 1
                           else acc
    pattern' = replace "(" "[" $ replace ")" "]" pattern

getResult :: String -&gt; ([String], Int, [String]) -&gt; ([String], Int, [String])
getResult pattern (w, count, accum) = (w, count - 1, res : accum)
    where res = "Case #" ++ show count ++ ": " ++ show (numberOfMatches pattern w)

main :: IO ()
main = do
  (header:xs) &lt;- fmap lines getContents -- IO is a Functor.
  let [_, d, n] = map read $ words header
  let knownWords = take d xs
  let patterns = drop d xs
  let (_, _, results) = foldr getResult (knownWords, n, []) patterns
  mapM_ putStrLn results


Which, for a test input of:


3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc



Yields the results:


Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0
A good rule of thumb is that you should only ever use foldr when you're really sure that your fold is not an instance of something simpler. In your case, the fold is doing pretty much exactly two things while traversing the pattern list:


Keeping track of the "case index"
Accumulating the result list


The second should be easily recognisable as a map - maybe less obvious is that the first can just be written as a zip with an enumeration:

getResult :: [String] -&gt; (Int, String) -&gt; String
getResult w (count, pattern) =
  "Case #" ++ show count ++ ": " ++ show (numberOfMatches pattern w)

main :: IO ()
main = do
  [...]
  let results = map (getResult knownWords) $ zip [1..n] patterns


Which is much easier to understand than trying to bend the fold to do the right thing.

Also, just as a suggestion, here's main implemented in a more "imperative" (read: monadic) style. After all, Haskell is said to be the best imperative language ever invented, so we can do that proudly:

main :: IO ()
main = do
  [_, d, n] &lt;- fmap (map read . words) getLine
  knownWords &lt;- replicateM d getLine
  forM_ [1..n] $ \count -&gt; do
    pattern &lt;- getLine
    let matches = numberOfMatches pattern knownWords
    putStrLn $ concat ["Case #", show count, ": ", show matches]