如何在Haskell中制作ticktack游戏的模式? [英] How to make a pattern of ticktack game in Haskell?

问题描述

实现带有2个参数的函数滴答作响.第一个参数是自然数的元组，它定义运动场的行数和列数.第二个列表包含由排位赛球员"x"和"o"轮流玩的排球比赛的记录.打印游戏的实际状态，游戏场将以字符-"和"|"为边界，空方块为"，字符"x"和"o"将为玩家所玩过的正方形.

Implement the function ticktack which has 2 arguments. First argument is a tuple of natural numbers and defines the number of rows and columns of a play field. Second list contains a record of a match of ticktacktoe game given by coordinates on which played in turns player 'x' and player 'o'. Print actual state of the game in the way where play-field will be bordered by characters '-' and '|', empty squares ' ' and characters 'x' and 'o' will be on squares where the players have played.

ticktack::(Int,Int) -> [(Int,Int)] -> Result

我已经尝试过这样的事情:

I already tried something like this:

type Result = [String]
pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x))

ticktack::(Int,Int) -> [(Int,Int)] -> Result
ticktack (0,0) (x:xs) = []
ticktack (a,b) [] = []
ticktack (a,b) (x:xs) =[ [if a == fst x && b == snd x then 'x' else ' ' | b <- [1..b]]| a <- [1..a]] ++ ticktack (a,b) xs 

但是它只返回1个结果的N [Strings]，所以我需要将这些结果合并为一个[String].

But it returns me only N [Strings] with 1 result, so i need these results merge into one [String].

推荐答案

正如@luqui在对问题的评论中所说:

As @luqui says in a comment to the question:

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

You could either merge the outputs ... or you could search the history once for each space in the board. ...

在附近的问题中中描述了前一种解决方案. "chess" 问题一直存在 解决了，与您的"noughts& crosss" 问题只是表面上不同，所以应该 适应解决方案不要太难.但是:

The former solution is described in a nearby question. The "chess" problem having been solved there is only superficially distinct from your "noughts & crosses" problem, so it should not be too hard to adapt the solution. However:

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

• In that case, the board size is fixed and small, so we were not worried about the inefficiency of merging the boards pairwise.

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

In this case, the board size is variable, so a solution by the latter method may be worth a try.

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

To make the algorithm even more efficient, instead of scrolling across the board and searching for matching moves at every cell, we will scroll across the moves and assign values to a board represented as a mutable array. Mutable arrays may be considered an "advanced technique" in functional programming, so it could also be a good exercise for an intermediate Haskeller. I only used them once or twice before, so let us see if I can figure this out!

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

At the heart of the program will be a rectangular array of bytes. An array goes in two flavours: mutable and "frozen". While a frozen array cannot be changed, It is a rule that a mutable array may only exist in a monadic context, so we can only freely pass around an array when it is frozen. If this seems to be overcomplicated, I can only ask the reader to believe that the additional safety guarantees are worth this complication.

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

Anyway, here are the types:

type Position = (Int, Int)

type Field s = STUArray s Position Char

type FrozenField = UArray Position Char

我们将创建一个函数，该函数应用" 移动到数组的列表，将其解冻并冻结为 需要.

We will create a function that "applies" a list of moves to an array, thawing and freezing it as needed.

type Move = (Char, Position)

applyMoves :: FrozenField -> [Move] -> FrozenField

(Move的想法是在板上标记一个标记就足够了，而无需知道 轮到谁了.)

(The idea of Move is that it is sufficient to put a mark on the board, without needing to know whose turn it is.)

应用于适当大小的空白字段，此功能将解决我们的问题-我们将 只需调整输入和输出的格式.

Applied to an empty field of the appropriate size, this function will solve our problem — we shall only need to adjust the format of the input and the output.

empty :: Position -> FrozenField

positionsToMoves :: [Position] -> [Move]

arrayToLists :: FrozenField -> [[Char]]

我们的最终程序将如下所示:

Our final program will then look like this:

tictac :: Position -> [Position] -> IO ()
tictac corner = pp . arrayToLists . applyMoves (empty corner) . positionsToMoves

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

I hope it looks sensible? Even though we have not yet written any tangible code.

是的

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

First, we will need some imports. No one likes imports, but, for some reason, it is not yet automated. So, here:

import Data.Foldable (traverse_)
import Data.Array.Unboxed
import Data.Array.ST
import GHC.ST (ST)

使用数组最简单的方法是创建一个空数组.让我们尝试一下:

The simplest thing one can do with arrays is to create an empty one. Let us give it a try:

empty :: Position -> FrozenField
empty corner = runSTUArray (newArray ((1, 1), corner) ' ')

这个想法是newArray在内存中声明一个区域并用空格填充，而runSTUArray 冻结它，以便可以将其安全地传输到程序的另一部分.我们可以代替 "inline" 创建数组并赢得了一定的速度，但是我们只需要做一次，而我 希望保持可组合性-我认为该程序将更简单.

The idea is that newArray claims a region in memory and fills it with spaces, and runSTUArray freezes it so that it can be safely transported to another part of a program. We could instead "inline" the creation of the array and win some speed, but we only need to do it once, and I wanted to keep it composable — I think the program will be simpler this way.

另一种容易做的事情是编写胶水" 代码来调整输入和输出格式:

Another easy thing to do is to write the "glue" code that adjusts the input and output format:

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] ]

正常列表处理在这里没有什么异常.

Nothing unusual here, run-of-the-mill list processing.

最后，最困难的部分是将任意数量的移动应用于给定的冻结数组的代码:

Finally, the hard part — the code that applies any number of moves to a given frozen array:

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 monad中进行修改. foldST包含所有 命令式" 内循环" .

The pattern is the same as in the function empty: modify an array, then freeze it — and all the modifications have to happen in an ST monad, for safety. foldST contains all the "imperative" "inner loop" of our program.

让我们首先打开UArray和STUArray类型.它们是什么，有什么区别?

Let us unwrap the UArray and STUArray types first. What are they and what is the difference?

UArray表示未装箱的数组" ，即值数组，而不是 指针.在我们的例子中，该值实际上是Unicode字符，而不是C 字节" char，因此它不是字节，而是变量 大小实体.以拆箱形式存储时，它将转换为Int32并以不可见的方式返回 给我们. Int32对于我们存储3个不同值的卑鄙目的来说当然太过分了， 因此这里有改进的空间.要了解有关未装箱值的更多信息，我邀请您 请查看1991年向他们介绍的文章， .

UArray means "unboxed array", which is to say an array of values, as opposed to an array of pointers. The value in our case is actually a Unicode character, not a C "byte" char, so it is not a byte, but a variable size entity. When it is stored in unboxed form, it is converted to an Int32 and back invisibly to us. An Int32 is of course way too much for our humble purpose of storing 3 different values, so there is space for improvement here. To find out more about unboxed values, I invite you to check the article that introduced them back in 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年的原始文章: 惰性功能状态线程" .

That the values are unboxed does not mean that you can change them though. A pure value in Haskell is always immutable. So, were you to change a single value in an array, the whole array would be copied — expensive! This is where STUArray comes in. ST stands for State Thread, and what STUArray is is an "unfrozen" array, where you can overwrite individual values without copying the whole thing. To ensure safety, it can only live in a monad, in this case the ST monad. (Notice how an STUArray value never appears outside of an ST s wrap.) You can imagine an ST computation as a small imperative process with its own memory, separate from the outside world. The story goes that they invented ST first, and then figured out they can get IO from it, so IO is actually ST in disguise. For more details on how ST works, check out the original article from 1994: "Lazy Functional State Threads".

现在让我们更加仔细地研究foldST.我们看到的是功能上， 有道理.首先我们将start'的值绑定到u，然后返回u-相同 多变的.从功能的角度来看，这与编写相同:

Let us now take a more careful look at foldST. What we see is that functionally, it does not make sense. First we bind the value of start' to u, and then we return u — the same variable. From the functional point of view, this is the same as writing:

u <- start'
return u

-按单子法则等同于u.诀窍在于它们之间发生的事情:

— Which would be equivalent to u by monad laws. The trick is in what happens inbetween:

traverse_ (f u) moves

让我们检查类型.

λ :type traverse_
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

因此，正在使用u作为参数调用某些函数，但结果是无用的()类型. 在功能设置中，此行将毫无意义.但是在单子中，绑定值可能会出现 改变. f是可以更改monad状态的函数，因此可以更改monad的值. 返回它们时的绑定名称. C中的类似代码将如下所示:

So, some function is being called, with u as argument, but the result is the useless () type. In a functional setting, this line would mean nothing. But in a monad, bound values may appear to change. f is a function that can change the state of a monad, and so can change the value of the bound names when they are returned. The analogous code in C would go somewhat like this:

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中，指针算法被抽象化了，但是ST中的traverse_本质上可以工作 像这样.我对C或ST抽象的内部原理都不是很熟悉，所以 这仅是一个类比，而不是试图进行精确再现的尝试.尽管如此，我希望它能帮助读者观察ST与普通命令式C代码之间的相似性.

In Haskell, the pointer arithmetic is abstracted away, but essentially traverse_ in ST works like this. I am not really familiar with C nor with the inner workings of the ST abstraction, so this is merely an analogy, not an attempt at a precise rendition. Nevertheless I hope it helps the reader to observe the similarity between ST and ordinary imperative C code.

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

It runs reasonably fast. Takes only a moment to draw a million-step match on a million-sized board. I hope it is also explained clearly enough. Do not hesitate to comment if something is amiss or unclear.

这篇关于如何在Haskell中制作ticktack游戏的模式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！