Haskell递归中map函数应用报错求助：字符串组合生成问题

首先要肯定你的核心思路：先为每一行生成所有可能的0/1填充组合（通过gen函数），再通过递归把各行的组合做笛卡尔积拼接，得到所有完整矩阵。这个思路完全贴合问题需求，是解决这类组合生成问题的标准方法。

接下来分析你遇到的编译错误，核心是递归函数recGame的参数传递和结果拼接逻辑出了问题：

1. 参数类型不匹配：你写的recGame (xs ++) ts里，xs ++是一个[String] -> [String]类型的函数，但recGame的第一个参数需要的是已经构建好的行列表（[String]类型），正确写法应该是把当前生成的行x添加到xs中，即xs ++ [x]。
2. 结果拼接错误：map会把每个x对应的递归结果（[[String]]）再包装一层，最终得到[[[String]]]，但我们需要的是[[String]]，所以应该用concat来合并这些子列表，或者用列表推导式直接展开。
3. 列表推导式语法问题：你写的[[...] | x <- (gen t)]里的[...]应该直接是x，因为gen t已经生成了当前行的所有可能字符串。

修正后的完整代码 #

solveGame :: [String] -> [[String]]
solveGame ts = recGame [] ts
  where
    -- 生成单个星号字符串的所有0/1组合
    gen :: String -> [String]
    gen [] = [""]
    gen ('*':cs) = [c : rest | c <- "01", rest <- gen cs]
    -- 题目说明输入是纯星号矩阵，下面这行可省略；如果有非*字符需求可以保留
    gen (c:cs) = [c : rest | rest <- gen cs]

    -- 递归构建所有矩阵组合
    recGame :: [String] -> [String] -> [[String]]
    recGame xs [] = [xs]  -- 所有行处理完毕，返回当前构建的完整矩阵
    recGame xs (t:ts) = concat [recGame (xs ++ [x]) ts | x <- gen t]
    -- 等价写法：concatMap (\x -> recGame (xs ++ [x]) ts) (gen t)

代码解释 #

• gen函数：递归处理输入字符串的每个字符，遇到*就替换为0或1，最终生成当前行的所有可能0/1组合。
• recGame函数：
  • 终止条件：当没有剩余行模板（ts为空）时，返回包含当前已构建矩阵xs的列表（这是一个完整的有效组合）。
  • 递归步骤：对当前行模板t生成的每个可能行x，把x追加到已构建的行列表xs中，递归处理剩下的行模板ts，最后用concat把所有递归得到的矩阵组合合并成一个大列表。

测试验证 #

比如输入["**", "**"]，运行solveGame ["**", "**"]会返回16种不同的2x2矩阵组合，包括["10", "01"]等，完全符合你的需求。

内容的提问来源于stack exchange，提问作者stackoverload