Google Code Jam - Alien Language
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]