Couldn't match expected type with actual type

Question

I am a total Haskell noob and I was hoping someone could help me with this because I've been at this for hours and I just know that I'm doing something ridiculously stupid.

The program is supposed to scan a dictionary file to determine all valid word sequences for a collection of sentences with spaces removed.

Ex. "insidewaysoften" could be broken down to "in side ways often", "inside way soften", etc.

I wrote my prototype in python and it works just fine (as does my Java implementation), but the course requires a Haskell implementation and I cannot get it to work. Apologies in advance for the crimes I have committed against the language and GHC with the following code:

import System.Environment   

main = do
  [dictFilename,sentFilename] <- getArgs  
  dictFile <- readFile dictFilename
  sentFile <- readFile sentFilename

  mapM (\sentence -> solve "" "" sentence (words dictFile)) (words sentFile)

solve prefix header [] dict =
  if (header `elem` dict) 
  then return prefix ++ header
  else return ""

solve prefix header sent dict = do
  let more = solve prefix (header ++ (take 1 sent)) (drop 1 sent) dict

  if (header `elem` dict) 
  then return (solve (prefix ++ header ++ " ") "" sent dict) ++ more
  else return more

Answer 1

The first thing when investigating type errors is to write down the type signatures of functions you know.

Here, solve may have type

solve :: String -> String -> String -> [String] -> String

or

solve :: String -> String -> String -> [String] -> IO String

Depending on whether it should have any side-effects while computing the value. Seeing you using mapM and return all over the place, I guess the IO version may have been intended.

Now, if you write down the signature, you start getting much more meaningful error messages. For example, instead of this:

tmp.hs:19:16:
    Couldn't match expected type `Char' with actual type `[Char]'
    Expected type: [Char]
      Actual type: [[Char]]
    In the return type of a call of `solve'
    In the first argument of `return', namely
      `(solve (prefix ++ header ++ " ") "" sent dict)'

, which does not make much sense, you get this:

tmp.hs:14:8:
    Couldn't match expected type `IO String' with actual type `[a0]'
    In the expression: return prefix ++ header
    In the expression:
      if (header `elem` dict) then return prefix ++ header else return ""
    In an equation for `solve':
        solve prefix header [] dict
          = if (header `elem` dict) then
                  return prefix ++ header
            else
                return ""

,which shows exactly where the problem is. Function application has the highest priority in Haskell, so return prefix ++ header is equivalent to (return prefix) ++ header, which is definitely not what you meant.

By the way, if I remove IO from the return type, remove all the returns and change the invocation by adding putStrLn, the code compiles and works! The only problem is that it concatenates all the possible sentences together into a single string without any delimiting.