Haskell - 如何使用列表 monad 在井字游戏中生成下一步
Haskell - how to generate next move in tic tac toe game with list monad
我正在 Haskell 中为 n * n 棋盘实现一个井字游戏，我需要生成我可以从下一步移动中获得的所有棋盘配置。
我的板子定义如下：
data Cell = E
| X
| O
deriving (Eq,Show)
type Row a = [a]
type Board = Row (Row Cell)
iniBoard :: Int -> Board
iniBoard n = let row = replicate n E in replicate n row
我可以确定给定的棋盘配置是否对玩家 x 有利，所以我有
win :: Cell -> Board -> Bool
win E _ = False
win x brd = any full $ diags brd ++ rows brd ++ cols brd
where
diags brd = mainDiag : [secondDiag]
mainDiag = zipWith (!!) brd [0..]
secondDiag = zipWith (!!) revBrd [0..]
revBrd = do
xs <- brd
return (reverse xs)
rows = id
cols = transpose
full xs = all (==x) xs
但我不知道如何生成玩家 x 下一步可以做出的所有棋盘配置。
我明白了，我需要遍历所有单元格并检查，如果单元格是空的，那么我可以在此处放置标记并 return 新配置。如果我已经有获胜配置，那么就没有下一步了，我必须return空列表
我有这样的代码：
nxt :: Cell -> Board -> [Board]
nxt x brd = do
if (win x brd || win (switch x) brd)
then
[]
else
undefined
我该怎么做，使用 list monad？感谢您的帮助！
和
picks :: [x] -> [([x], x, [x])]
picks [] = []
picks (x : xs) = ([] , x, xs) : [(x : sy, y, ys) | (sy, y, ys) <- picks xs]
（这是 this 的调整版本），所有可能的下一个板是
import Data.List.Split (chunksOf)
next :: Int -> Cell -> Board -> [Board]
next n who b =
picks (concat b) >>= \(sy, y, ys) ->
case y of E -> [chunksOf n $ sy ++ [who] ++ ys] ;
_ -> []
其中 who 是 X 或 O 之一，或者是课程。
这只不过是一个过滤器，用来保留空的，同时在那些已经过滤过的地图上绘制地图。有了列表理解就更简单了，
next n who b = [ chunksOf n $ sy ++ [who] ++ ys
| (sy, E, ys) <- picks $ concat b ]
picks 函数在连接的行中一个接一个地挑选所有可能的单元格，同时还保留前缀和后缀； chunksOf n 从一长排单元格重建电路板，连续 n 个单元格。所以整体效果是所有可能的板的列表，其中 E 被替换为 who。
更高效的 picks 将以相反的顺序构建其前缀 (sy)；创建一个名为 "zippers" 的列表。然后在重建时必须相应地反转它们。
编辑： 如列表理解所示，它本来可以用 do 符号写成：
next n who b = do
(sy, E, ys) <- picks $ concat b
return (chunksOf n $ sy ++ [who] ++ ys])
在 do 表示法中，模式不匹配被转换为对 fail 的调用，在列表 monad 中，这会导致跳过一个元素，同时整个计算继续进行而不会失败。
edit2: 一个基于 Data.List 的代码，一次完成输入，是
import Data.List (mapAccumL)
-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
next who b = concat . snd $ mapAccumL f (id, drop 1 xs) xs
where
xs = concat b
n = length b
f (k,r) x = ( (k.(x:), drop 1 r) , [chunksOf n $ k (who:r) | x==E] )
感谢 גלעד ברקן 的讨论。
如果我们查看 >>= 的类型签名，我们会发现它是
(>>=) :: Monad m => m a -> (a -> m b) -> m b
如果您希望能够 "chain" 您的 nxt 函数，绑定的整个类型签名必须是：
[Board] -> (Board -> [Board]) -> [Board]
所以 nxt 必须具有类型 Board -> [Board]。现在我们必须问自己 nxt 到底做了什么：它需要一个棋盘和 returns 当前棋盘的所有可能移动。巧合的是，nxt 的类型正是 >>= 所需要的：Board -> [Board]。可是等等。我们怎么知道轮到谁了？就像您已经做的那样，我们可以将当前标记作为参数传递给 place，但这也会改变类型签名：Cell -> Board -> [Board]。我们还能链接这个函数吗？ 是的，我们可以。使用部分应用，我们已经可以通过传递下一个标记然后绑定结果函数来应用下一个标记：
nxt :: Cell -> Board -> [Board]
nxt X :: Board -> [Board]
现在我们要做的就是遍历每一个字段，检查是否为空。如果是，那么我们用我们的标记替换它并遍历其他字段。 :
nxt :: Cell -> Board -> [Board]
nxt _ [] = []
nxt mark (row:rest) = map (:rest) (replaceAll mark row) ++ (map (row:) $ nxt mark rest)
where
replaceAll _ [] = []
replaceAll m (x:xs)
| x == E = (m:xs) : (map (x:) $ replaceAll m xs)
| otherwise = map (x:) $ replaceAll m xs
现在你可以像这样连动：
iniState 3 >>= nxt X >>= nxt O
为了更好的使用目的，我建议将模拟功能和实际走法查找功能分开。例如，您可以像这样轻松编写一个函数，其中 returns 所有棋盘都将赢得特定尺寸和特定玩家：
winner :: Cell -> Int -> [Board]
winner who size = filter (win who)
$ foldr (>=>) return (take (n*n) $ cycle [nxt O, nxt X])
$ initBoard n
我会留给你来实现游戏部分作为练习。
其他答案涵盖了直接的解决方案。在这里，我提出了一个 lens 解决方案，因为它非常适用于该任务。
使用lens我们可以分别指定以下两件事：
- 我们要对数据结构的哪些部分进行操作。
- 我们想对这些部分进行哪些操作。
我们想指向板上的空单元格作为目标。 Traversal' Board Cell表示整个数据结构的类型为Board，而目标的类型为Cell。
import Control.Lens
emptyCells :: Traversal' Board Cell
emptyCells = each . each . filtered (==E)
现在我们可以用emptyCells进行各种操作了。
board = iniBoard 3
-- get the number of targets:
lengthOf emptyCells board -- 9
-- return a flat list of the targets
toListOf emptyCells board -- [E,E,E,E,E,E,E,E,E]
-- set all targets to a value
set emptyCells X board -- [[X,X,X],[X,X,X],[X,X,X]]
-- set the nth target to a value
set (elementOf emptyCells 2) X board -- [[E,E,X],[E,E,E],[E,E,E]]
-- get the nth target, if it exists
preview (elementOf emptyCells 2) board -- Just E
我们还可以使用 emptyCells 和 holesOf 函数巧妙地实现 next。 holesOf emptyCells returns 板的 "holes" 列表。每个孔基本上包含一个 Cell 和一个函数，该函数接受一个 Cell 参数和 returns 一个新的 Board，并将提供的 Cell 插入某个位置。
不幸的是，漏洞的实现相当抽象，并且 holesOf emptyCells 具有无信息的 Board ->[Control.Lens.Internal.Context.Pretext (->) Cell Cell Board] 类型。我们应该只记得 Control.Comonad.Store 提供了一个处理孔的接口。 pos returns 一个空洞的焦点元素（这里是一个 Cell），而 peek 在空洞中插入一个新元素和 returns 结果数据结构.
对于nxt x board，我们需要将x插入到每个有空单元格的位置。考虑到这一点，nxt 就变成了：
import Control.Comonad.Store
nxt :: Cell -> Board -> [Board]
nxt x = map (peek x) . holesOf emptyCells
这是一个遍历棋盘的版本，只在遇到 E 时添加可能的着法：
nxt' :: Cell -> Board -> [Board]
nxt' x brd = do (E,i) <- zip b [0..]
return (chunksOf l $ (take i b) ++ [x] ++ (drop (i + 1) b))
where l = length brd
b = concat brd
我正在 Haskell 中为 n * n 棋盘实现一个井字游戏，我需要生成我可以从下一步移动中获得的所有棋盘配置。
我的板子定义如下：
data Cell = E
| X
| O
deriving (Eq,Show)
type Row a = [a]
type Board = Row (Row Cell)
iniBoard :: Int -> Board
iniBoard n = let row = replicate n E in replicate n row
我可以确定给定的棋盘配置是否对玩家 x 有利，所以我有
win :: Cell -> Board -> Bool
win E _ = False
win x brd = any full $ diags brd ++ rows brd ++ cols brd
where
diags brd = mainDiag : [secondDiag]
mainDiag = zipWith (!!) brd [0..]
secondDiag = zipWith (!!) revBrd [0..]
revBrd = do
xs <- brd
return (reverse xs)
rows = id
cols = transpose
full xs = all (==x) xs
但我不知道如何生成玩家 x 下一步可以做出的所有棋盘配置。
我明白了，我需要遍历所有单元格并检查，如果单元格是空的，那么我可以在此处放置标记并 return 新配置。如果我已经有获胜配置，那么就没有下一步了，我必须return空列表
我有这样的代码：
nxt :: Cell -> Board -> [Board]
nxt x brd = do
if (win x brd || win (switch x) brd)
then
[]
else
undefined
我该怎么做，使用 list monad？感谢您的帮助！
和
picks :: [x] -> [([x], x, [x])]
picks [] = []
picks (x : xs) = ([] , x, xs) : [(x : sy, y, ys) | (sy, y, ys) <- picks xs]
（这是 this 的调整版本），所有可能的下一个板是
import Data.List.Split (chunksOf)
next :: Int -> Cell -> Board -> [Board]
next n who b =
picks (concat b) >>= \(sy, y, ys) ->
case y of E -> [chunksOf n $ sy ++ [who] ++ ys] ;
_ -> []
其中 who 是 X 或 O 之一，或者是课程。
这只不过是一个过滤器，用来保留空的，同时在那些已经过滤过的地图上绘制地图。有了列表理解就更简单了，
next n who b = [ chunksOf n $ sy ++ [who] ++ ys
| (sy, E, ys) <- picks $ concat b ]
picks 函数在连接的行中一个接一个地挑选所有可能的单元格，同时还保留前缀和后缀； chunksOf n 从一长排单元格重建电路板，连续 n 个单元格。所以整体效果是所有可能的板的列表，其中 E 被替换为 who。
更高效的 picks 将以相反的顺序构建其前缀 (sy)；创建一个名为 "zippers" 的列表。然后在重建时必须相应地反转它们。
编辑： 如列表理解所示，它本来可以用 do 符号写成：
next n who b = do
(sy, E, ys) <- picks $ concat b
return (chunksOf n $ sy ++ [who] ++ ys])
在 do 表示法中，模式不匹配被转换为对 fail 的调用，在列表 monad 中，这会导致跳过一个元素，同时整个计算继续进行而不会失败。
edit2: 一个基于 Data.List 的代码，一次完成输入，是
import Data.List (mapAccumL)
-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
next who b = concat . snd $ mapAccumL f (id, drop 1 xs) xs
where
xs = concat b
n = length b
f (k,r) x = ( (k.(x:), drop 1 r) , [chunksOf n $ k (who:r) | x==E] )
感谢 גלעד ברקן 的讨论。
如果我们查看 >>= 的类型签名，我们会发现它是
(>>=) :: Monad m => m a -> (a -> m b) -> m b
如果您希望能够 "chain" 您的 nxt 函数，绑定的整个类型签名必须是：
[Board] -> (Board -> [Board]) -> [Board]
所以 nxt 必须具有类型 Board -> [Board]。现在我们必须问自己 nxt 到底做了什么：它需要一个棋盘和 returns 当前棋盘的所有可能移动。巧合的是，nxt 的类型正是 >>= 所需要的：Board -> [Board]。可是等等。我们怎么知道轮到谁了？就像您已经做的那样，我们可以将当前标记作为参数传递给 place，但这也会改变类型签名：Cell -> Board -> [Board]。我们还能链接这个函数吗？ 是的，我们可以。使用部分应用，我们已经可以通过传递下一个标记然后绑定结果函数来应用下一个标记：
nxt :: Cell -> Board -> [Board]
nxt X :: Board -> [Board]
现在我们要做的就是遍历每一个字段，检查是否为空。如果是，那么我们用我们的标记替换它并遍历其他字段。 :
nxt :: Cell -> Board -> [Board]
nxt _ [] = []
nxt mark (row:rest) = map (:rest) (replaceAll mark row) ++ (map (row:) $ nxt mark rest)
where
replaceAll _ [] = []
replaceAll m (x:xs)
| x == E = (m:xs) : (map (x:) $ replaceAll m xs)
| otherwise = map (x:) $ replaceAll m xs
现在你可以像这样连动：
iniState 3 >>= nxt X >>= nxt O
为了更好的使用目的，我建议将模拟功能和实际走法查找功能分开。例如，您可以像这样轻松编写一个函数，其中 returns 所有棋盘都将赢得特定尺寸和特定玩家：
winner :: Cell -> Int -> [Board]
winner who size = filter (win who)
$ foldr (>=>) return (take (n*n) $ cycle [nxt O, nxt X])
$ initBoard n
我会留给你来实现游戏部分作为练习。
其他答案涵盖了直接的解决方案。在这里，我提出了一个 lens 解决方案，因为它非常适用于该任务。
使用lens我们可以分别指定以下两件事：
- 我们要对数据结构的哪些部分进行操作。
- 我们想对这些部分进行哪些操作。
我们想指向板上的空单元格作为目标。 Traversal' Board Cell表示整个数据结构的类型为Board，而目标的类型为Cell。
import Control.Lens
emptyCells :: Traversal' Board Cell
emptyCells = each . each . filtered (==E)
现在我们可以用emptyCells进行各种操作了。
board = iniBoard 3
-- get the number of targets:
lengthOf emptyCells board -- 9
-- return a flat list of the targets
toListOf emptyCells board -- [E,E,E,E,E,E,E,E,E]
-- set all targets to a value
set emptyCells X board -- [[X,X,X],[X,X,X],[X,X,X]]
-- set the nth target to a value
set (elementOf emptyCells 2) X board -- [[E,E,X],[E,E,E],[E,E,E]]
-- get the nth target, if it exists
preview (elementOf emptyCells 2) board -- Just E
我们还可以使用 emptyCells 和 holesOf 函数巧妙地实现 next。 holesOf emptyCells returns 板的 "holes" 列表。每个孔基本上包含一个 Cell 和一个函数，该函数接受一个 Cell 参数和 returns 一个新的 Board，并将提供的 Cell 插入某个位置。
不幸的是，漏洞的实现相当抽象，并且 holesOf emptyCells 具有无信息的 Board ->[Control.Lens.Internal.Context.Pretext (->) Cell Cell Board] 类型。我们应该只记得 Control.Comonad.Store 提供了一个处理孔的接口。 pos returns 一个空洞的焦点元素（这里是一个 Cell），而 peek 在空洞中插入一个新元素和 returns 结果数据结构.
对于nxt x board，我们需要将x插入到每个有空单元格的位置。考虑到这一点，nxt 就变成了：
import Control.Comonad.Store
nxt :: Cell -> Board -> [Board]
nxt x = map (peek x) . holesOf emptyCells
这是一个遍历棋盘的版本，只在遇到 E 时添加可能的着法：
nxt' :: Cell -> Board -> [Board]
nxt' x brd = do (E,i) <- zip b [0..]
return (chunksOf l $ (take i b) ++ [x] ++ (drop (i + 1) b))
where l = length brd
b = concat brd