CODEWITHSUNDEEP
dictionaryhaskellrecursionbacktracking
stackoverload
stackoverload

Reputation: 119

Applying Haskell map function in recursion

Recently I've been doing some Haskell. I need to generate all possibilities of strings, that is I am given [String], I should output [[String]].

solveGame :: [String] -> [[String]]
solveGame ts = recGame [] ts
  where recGame xs [] = [xs]
        recGame xs (t:ts) = map (recGame (xs ++ ) ts) [[x] | x <- (gen t)]

where, gen outputs number of all possible strings to recur, therefore, gen :: String -> [String]. So basically the problem is to permute all possible strings, generated by gen. I tried to run my version, but it outputs the errors. Is it alright to do it in this way?

Input for solveGame will be matrix n*n of stars (for example ["**", "**"]) and the output should be list of all possible matrices filled with 1 and 0 (this list will will contain 16 matrices like ["10", "01"])

The errors that I have:

Takuzu.hs:15:16: error:
    • Couldn't match expected type ‘[[String]]’
                  with actual type ‘[String] -> [a1]’
    • Probable cause: ‘recGame’ is applied to too few arguments
      In the expression: recGame [] ts
      In an equation for ‘solveGame’:
          solveGame ts
            = recGame [] ts
            where
                recGame xs [] = [xs]
                recGame xs (t : ts)
                  = map (recGame (xs ++) ts) [[...] | x <- (gen t)]
   |
15 | solveGame ts = recGame [] ts
   |                ^^^^^^^^^^^^^

Takuzu.hs:15:24: error:
    • Couldn't match expected type ‘[a1] -> [a1]’
                  with actual type ‘[a0]’
    • In the first argument of ‘recGame’, namely ‘[]’
      In the expression: recGame [] ts
      In an equation for ‘solveGame’:
          solveGame ts
            = recGame [] ts
            where
                recGame xs [] = [xs]
                recGame xs (t : ts)
                  = map (recGame (xs ++) ts) [[...] | x <- (gen t)]
   |
15 | solveGame ts = recGame [] ts
   |                        ^^

Takuzu.hs:16:9: error:
    • Couldn't match type ‘[a]’ with ‘[a] -> [a]’
      Expected type: ([a] -> [a]) -> [String] -> [String] -> [a]
        Actual type: [a] -> [String] -> [[a]]
    • In an equation for ‘solveGame’:
          solveGame ts
            = recGame [] ts
            where
                recGame xs [] = [xs]
                recGame xs (t : ts)
                  = map (recGame (xs ++) ts) [[...] | x <- (gen t)]
    • Relevant bindings include
        recGame :: ([a] -> [a]) -> [String] -> [String] -> [a]
          (bound at Takuzu.hs:16:9)
   |
16 |   where recGame xs [] = [xs]
   |         ^^^^^^^^^^^^^^^^^^^^...
Failed, no modules loaded.

Upvotes: 0

Views: 128

Answers (1)

bradrn
bradrn

Reputation: 8467

Looking at the error message, it looks like GHC is inferring the wrong type for recGame. (How do I know this? It’s because every time recGame is mentioned in the error messages, there’s a lot of [a] -> [a] stuff, which doesn’t look right.) So, as a first step, let’s add a type signature:

solveGame :: [String] -> [[String]]
solveGame ts = recGame [] ts
  where 
    recGame :: [String] -> [String] -> [[String]]
    recGame xs [] = [xs]
    recGame xs (t:ts) = map (recGame (xs ++ ) ts) [[x] | x <- (gen t)]

Once we do this, we get some more useful error messages:

so.hs:10:30: error:
    • Couldn't match expected type ‘[String] -> [String]’
                  with actual type ‘[[String]]’
    • Possible cause: ‘recGame’ is applied to too many arguments
      In the first argument of ‘map’, namely ‘(recGame (xs ++) ts)’
      In the expression: map (recGame (xs ++) ts) [[x] | x <- (gen t)]
      In an equation for ‘recGame’:
          recGame xs (t : ts) = map (recGame (xs ++) ts) [[x] | x <- (gen t)]
   |
10 |     recGame xs (t:ts) = map (recGame (xs ++ ) ts) [[x] | x <- (gen t)]
   |                              ^^^^^^^^^^^^^^^^^^^

so.hs:10:39: error:
    • Couldn't match expected type ‘[String]’
                  with actual type ‘[String] -> [String]’
    • In the first argument of ‘recGame’, namely ‘(xs ++)’
      In the first argument of ‘map’, namely ‘(recGame (xs ++) ts)’
      In the expression: map (recGame (xs ++) ts) [[x] | x <- (gen t)]
   |
10 |     recGame xs (t:ts) = map (recGame (xs ++ ) ts) [[x] | x <- (gen t)]
   |                                       ^^^^^

So, it looks like in the (t:ts) case, you’re giving (xs++) as a parameter to recGame — but (xs++) is a function, so you can’t do that! I don’t know what you’re trying to do here, so I can’t suggest a fix, but that is definitely the error, and it’s one you should fix.

Upvotes: 2

Related Questions