haskell - 打印所有可能的世界配置

Question

刚开始使用 Haskell!作为练习，我正在尝试实现的当前问题如下:

我们有 n 个正方形，打印所有可能的世界配置，其中:

(1) 每个方块可能有一个“P”(坑)或没有(2^n 的可能性)。

(2) 在所有 n 个方格中最多只能有一个“W”(wumpus)(n+1 种可能性)。

将两个正方形表示为两个字符串，这里是 n=2 的输出示例。我们有 (2^n)·(n+1) = (2^2)·(2+1) = 12 个配置。

[[" W"," "],[" "," W"],[" "," "],
 [" W","P"],[" ","PW"],[" ","P"],
 ["PW"," "],["P"," W"],["P"," "],
 ["PW","P"],["P","PW"],["P","P"]]

条件(1)很容易实现。环顾四周，我找到了几种表达方式:

p 0 = [[]]
p n = [x:xs | x <- [" ","P"], xs <- p (n-1)]

或者

p n = mapM (\x -> [" ","P"]) [1..n]

或者

p n = replicateM n [" ","P"]

我还不能声称理解最后两个，但它们是为了完整性。

问题:如何添加条件(2)？ 可以通过列表理解来完成吗？
我的不太好看的新手解决方案涉及以下功能:

insertw :: Int -> [String] -> [String]
insertw n xs 
    | n < 0     = xs
    | n >= lgth = xs
    | otherwise = (take (n) xs) ++ [xs!!n++"W"] ++ (drop (n+1) xs)
    where lgth  = length xs

duplicate :: Int -> [String] -> [[String]]
duplicate i squares 
    | i > lgth   = []
    | otherwise  = (insertw i squares) : duplicate (i+1) squares
    where lgth   = length squares

worlds :: Int -> [[String]]
worlds n = concat . map (duplicate 0) . p $ n

Answer 1

对我来说似乎很明显:)。在列表推导式中，后面的列表可以依赖于前面的列表中生成的值。第二个函数通过在添加 wumpus 时调用第一个函数来生成您的集合。

p 0 = [[]]
p n = [[x,' ']:xs | x <- [' ','P'], xs <- p (n-1)]

pw 0 = [[]]
pw n = [[x,w]:xs | w <- [' ','W'], x <- [' ','P'], xs <- if w == 'W' then p (n-1) else pw (n-1)]

它不是尽可能干净，但我总是发现列表推导式为问题带来了优雅:)。完全值得的。