正如@luqui 在对该问题的评论中所说：
您可以合并输出...或者您可以为每个空间搜索一次历史记录
董事会。 ...
之前的解决方案是在附近的问题中描述 https://stackoverflow.com/a/58685116. The "chess"问题已经
解决了，与你的只是表面上的不同“圈和叉”问题，所以应该
适应解决方案不要太难。然而：
为了使算法更加高效，而不是在棋盘上滚动并搜索
匹配每个单元格的动作，我们将滚动动作并将值分配给棋盘
表示为可变数组。可变数组可以被认为是「先进技术」在
函数式编程，因此对于中级 Haskeller 来说这也是一个很好的练习。我只是
以前用过它们一两次，所以让我们看看我是否能解决这个问题！
这将如何运作？
该程序的核心是一个字节矩形数组。数组有两种类型：
可变的和"frozen"。虽然冻结数组无法更改，但可变数组是一条规则
可能只存在于单子上下文中，因此我们只能在数组被冻结时自由地传递它。
如果这看起来过于复杂，我只能请读者相信额外的
安全保证是值得的。
不管怎样，有以下几种类型：
type Position = (Int, Int)
type Field s = STUArray s Position Char
type FrozenField = UArray Position Char
我们将创建一个函数“适用”移动到数组的列表，将其解冻和冻结为
需要。
type Move = (Char, Position)
applyMoves :: FrozenField -> [Move] -> FrozenField
（这个想法Move是在板上做个标记就足够了，不需要知道
轮到谁了。）
应用于适当大小的空字段，该函数将解决我们的问题 - 我们将
只需要调整输入和输出的格式。
empty :: Position -> FrozenField
positionsToMoves :: [Position] -> [Move]
arrayToLists :: FrozenField -> [[Char]]
我们的最终程序将如下所示：
tictac :: Position -> [Position] -> IO ()
tictac corner = pp . arrayToLists . applyMoves (empty corner) . positionsToMoves
我希望它看起来很明智？尽管我们还没有编写任何有形的代码。
我们可以写代码吗？
Yes.
首先，我们需要一些进口。没有人喜欢进口，但由于某种原因，目前还没有
自动化。所以在这里：
import Data.Foldable (traverse_)
import Data.Array.Unboxed
import Data.Array.ST
import GHC.ST (ST)
使用数组可以做的最简单的事情就是创建一个空数组。让我们尝试一下：
empty :: Position -> FrozenField
empty corner = runSTUArray (newArray ((1, 1), corner) ' ')
这个想法是newArray声明内存中的一个区域并用空格填充它，并且runSTUArray冻结它，以便可以安全地将其传输到程序的另一部分。我们可以改为"inline"创建数组并赢得一些速度，但我们只需要做一次，我
希望保持它的可组合性——我认为这样程序会更简单。
另一件容易做的事情是写"glue"调整输入输出格式的代码：
positionsToMoves :: [Position] -> [Move]
positionsToMoves = zip (cycle ['x', 'o'])
arrayToLists :: FrozenField -> [[Char]]
arrayToLists u =
let ((minHeight, minWidth), (maxHeight, maxWidth)) = bounds u
in [ [ u ! (row, column) | column <- [minWidth.. maxWidth] ] | row <- [minHeight.. maxHeight] ]
这里没有什么不寻常的，普通的列表处理。
最后，最困难的部分 - 将任意数量的移动应用于给定冻结数组的代码：
applyMoves :: FrozenField -> [Move] -> FrozenField
applyMoves start xs = runSTUArray (foldST applyMove (thaw start) xs)
where
foldST :: (a -> b -> ST s ()) -> ST s a -> [b] -> ST s a
foldST f start' moves = do
u <- start'
traverse_ (f u) moves
return u
applyMove :: Field s -> Move -> ST s ()
applyMove u (x, i) = writeArray u i x
模式与函数中的模式相同empty：修改一个数组，然后冻结它——以及所有
修改必须发生在STmonad，为了安全。foldST包含所有的“至关重要的” “内循环”我们的计划。
(P.S.)这实际上是如何运作的？
让我们打开包装UArray and STUArray首先类型。它们是什么以及有什么区别？
UArray means “拆箱数组”，也就是说一个值数组，而不是一个数组
指针。我们例子中的值实际上是一个 Unicode 字符，而不是 C"byte" char，所以它不是一个字节，而是一个变量
大小实体。当它以未装箱的形式存储时，它会转换为Int32然后隐形地回来
对我们来说。一个Int32对于我们存储 3 个不同值的卑微目的来说当然太多了，
所以这里还有改进的空间。要了解有关未装箱值的更多信息，我邀请您
查看 1991 年介绍它们的文章，“作为一等公民的未装箱价值观
非严格的函数式语言” https://www.microsoft.com/en-us/research/wp-content/uploads/1991/01/unboxed-values.pdf.
这些值未装箱并不意味着您可以更改它们。 Haskell 中的纯值
总是不可变的。因此，如果您更改数组中的单个值，整个数组将是
抄袭——贵！这是哪里STUArray进来。ST代表State Thread，还有什么STUArray是 是 一个“解冻”数组，您可以在其中覆盖单个值而无需复制
整个东西。为了确保安全，它只能生活在一个 monad 中，在本例中是ST monad.
（注意如何STUArray值永远不会出现在 a 之外ST s wrap.)你可以想象一个ST计算作为一个小的命令式进程，拥有自己的内存，与外部分离
世界。据说他们发明了ST首先，然后发现他们可以获得IO从
它，所以IO实际上是ST伪装的。有关如何操作的更多详细信息ST有效，查看
1994年的原创文章：“惰性功能状态线程” https://www.microsoft.com/en-us/research/wp-content/uploads/1994/06/lazy-functional-state-threads.pdf..
现在让我们更仔细地看看foldST。我们看到的是功能上， 它不是
合理。首先我们绑定的值start' to u，然后我们返回u- 相同
多变的。从功能的角度来看，这与写法是一样的：
u <- start'
return u
— 这相当于u由单子定律。诀窍在于中间发生的事情：
traverse_ (f u) moves
让我们检查一下类型。
λ :type traverse_
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
因此，正在调用某个函数u作为论证，但结果是无用的()类型。
在功能设置中，这条线毫无意义。但在 monad 中，绑定值可能appear改变。f是一个可以改变 monad 状态的函数，因此可以改变
返回时的绑定名称。 C 中的类似代码有点像这样：
char* foldST(void f(char*, Move), int n_start, char start[], int n_moves, Move moves[])
{
// u <- start
char* u = malloc(sizeof(char) * n_start);
memcpy(u, start, sizeof(char) * n_start);
// traverse_ (f u) moves
for (int i = 0; i < n_moves; i++)
{
f(u, moves[i]);
}
// return u
return u;
}
在 Haskell 中，指针算术被抽象掉了，但本质上traverse_ in ST作品
像这样。我不太熟悉 C 也不熟悉 C 的内部工作原理ST抽象化，所以
这只是一个类比，而不是试图精确再现。尽管如此，我希望它能帮助读者观察两者之间的相似之处ST和普通的命令式 C 代码。
任务完成！
它运行得相当快。只需片刻即可在百万尺寸上绘制百万步比赛
木板。我希望它也解释得足够清楚。如果有问题或不清楚，请随时发表评论。
