@luqui在对问题的评论中说：

  

您可以合并输出...，也可以在历史记录中为每个空格搜索一次   董事会。 ...

以前的解决方案是described in a nearby question。 “ chess” 问题已经 解决了，与您的“ noughts＆crosss” 问题只是表面上不同，所以应该 适应解决方案不要太难。但是：

• 在这种情况下，电路板尺寸固定且很小，因此我们不必担心效率低下 成对合并板的操作。

• 在这种情况下，电路板尺寸是可变的，因此后一种方法的解决方案可能值得一试。

使算法更加有效，而不是全盘滚动并搜索 在每个单元格上匹配匹配的移动，我们将滚动移动并为板分配值 表示为可变数组。可变数组可以被视为“高级技术” 函数式编程，因此对于中级Haskeller来说也是一个不错的练习。我只是 曾经使用过它们一两次，所以让我们看看是否可以解决！

这如何工作？

程序的核心是一个矩形字节数组。数组有两种口味： 可变且“冻结” 。虽然不能更改冻结的数组，但是可变数组是一个规则 可能仅存在于单子上下文中，因此我们只能在冻结数组时自由地对其进行传递。 如果这看起来过于复杂，我只能请读者相信 安全保障值得为此付出努力。

无论如何，以下是这些类型：

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

我希望它看起来明智吗？即使我们尚未编写任何有形的代码。

我们可以编写代码吗？

是的

首先，我们将需要一些进口。没有人喜欢进口，但是由于某种原因，目前还没有 自动化。所以，在这里：

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中的模式相同：修改数组，然后冻结它-所有 为了安全起见，必须在ST单子中进行修改。 foldST包含所有 “命令式” “内循环” 。

（P.S。）这实际上如何工作？

让我们首先解开UArray和STUArray类型。它们是什么，有什么区别？

UArray的意思是“未装箱的数组” ，也就是说，是一个值数组，而不是 指针。在我们的例子中，该值实际上是Unicode字符，而不是C “字节” char，因此它不是字节，而是变量 大小实体。以拆箱形式存储时，它将转换为Int32并以不可见的方式返回 给我们。 Int32对于我们存储3个不同值的卑鄙目的当然太过分了， 因此这里有改进的空间。要了解有关未装箱值的更多信息，我邀请您 请查看1991年为他们介绍的文章"Unboxed Values as First Class Citizens in a Non-Strict Functional Language"。

将值取消装箱并不意味着您可以更改它们。 Haskell的纯价值 永远是一成不变的。因此，如果您要更改数组中的单个值，则整个数组将是 复制-昂贵！这是STUArray进入的地方。ST代表State Thread，以及什么 STUArray是一个“未冻结” 数组，您可以在其中覆盖单个值而无需复制 整个东西。为了确保安全，它只能存在于monad中，在这种情况下为ST monad。 （注意STUArray值永远不会出现在ST s换行符之外。）您可以想象一个 ST计算是一个小的命令性过程，具有自己的内存，与外界分开 世界。传说他们首先发明了ST，然后发现他们可以从中获得IO 因此，IO实际上是ST的变相。有关ST的工作方式的更多详细信息，请查看 1994年的原始文章："Lazy Functional State Threads"。

现在让我们更加仔细地研究foldST。我们看到的是功能上， 合理。首先，我们将start'的值绑定到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作为参数调用某些函数，但结果是无用的()类型。 在功能设置中，此行将毫无意义。但是在单子中，绑定值可能会出现 改变。 f是可以更改monad状态的函数，因此可以更改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_中的ST有效 像这样。我对C或ST抽象的内部原理都不是很熟悉，所以 这仅是一个类比，而不是试图进行精确再现的尝试。尽管如此，我希望它能帮助读者观察ST与普通命令式C代码之间的相似性。

任务完成！

运行速度相当快。仅需一点时间就可以在一百万个尺寸上绘制一百万步的比赛 板。我希望对它的解释也足够清楚。如果有什么不妥之处或不清楚之处，请随时发表评论。