在递归中应用 Haskell 映射函数

Question

最近我一直在做一些Haskell。我需要生成字符串的所有可能性，即给定 [String]，我应该输出 [[String]].

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

其中，gen 输出所有可能重复出现的字符串的数量，因此， gen :: String -> [String]。所以基本上问题是排列所有可能的字符串，由 gen 生成。我尝试运行我的版本，但它输出错误。这样可以吗？

solveGame 的输入将是星号矩阵 n*n （例如 ["**", "**"]）并且输出应该是所有可能的矩阵的列表，其中填充有 1 和 0（此列表将包含 16 个矩阵，例如 ["10", "01"]）

我遇到的错误：

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.

Answer 1

查看错误消息，GHC 似乎在为 recGame 推断出错误的类型。（我怎么知道的？这是因为每次错误消息中提到 recGame 时，都会有很多 [a] -> [a] 的东西，看起来不对。）所以，作为第一步，让我们添加类型签名：

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)]

执行此操作后，我们会收到一些更有用的错误消息：

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)]
   |                                       ^^^^^

所以，在 (t:ts) 的情况下，您将 (xs++) 作为参数提供给 recGame — 但 (xs++) 是一个函数，所以您不能那样做！我不知道你想在这里做什么，所以我不能建议修复，但这绝对是错误，你应该修复它。

在递归中应用 Haskell 映射函数

Applying Haskell map function in recursion

recursion

dictionary

haskell

backtracking