Как говорит @luqui в комментарии к вопросу:
Вы можете объединить выходные данные ... или вы можете искать в истории один раз для каждого пробела на доске. ...
Первое решение описано в соседнем вопросе . Решенная здесь проблема "шахматы" лишь поверхностно отличается от вашей проблемы "крестики-нолики" , поэтому адаптировать решение не должно быть слишком сложно. Однако:
В этом случае размер платы фиксирован и мал, поэтому нас не беспокоит неэффективность объединения досок попарно.
В этом случае размер платы является переменным, поэтому стоит попробовать решение последним методом.
Чтобы сделать алгоритм еще более эффективным, вместо прокрутки поBoard и в поисках подходящих ходов в каждой ячейке мы прокручиваем ходы и назначаем значения доске, представленной в виде изменяемого массива. Изменяемые массивы можно считать «продвинутой техникой» в функциональном программировании, поэтому это также может быть хорошим упражнением для промежуточного Хаскеллера. Я использовал их только один или два раза, поэтому давайте посмотрим, смогу ли я это выяснить!
Как это будет работать?
В основе программы будет прямоугольный массивбайтов. Массив представлен в двух вариантах: изменяемый и «замороженный» . Хотя замороженный массив не может быть изменен, существует правило, что изменяемый массив может существовать только в монадическом контексте, поэтому мы можем свободно передавать массив только тогда, когда он заморожен. Если это кажется слишком сложным, я могу только попросить читателя поверить, что дополнительные гарантии безопасности стоят этого усложнения.
В любом случае, вот типы:
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" создать массив и выиграть некоторую скорость, но нам нужно сделать это только один раз, и я хотел, чтобы он был компонуемым - я думаю, что программа будет проще в этом смысле.
Еще одна простая вещь - это написать «клей» код, который регулирует формат ввода и вывода:
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 содержит все "императив" "внутренний цикл" нашей программы.
(PS) Как это на самом деле работает?
Давайте сначала развернем типы UArray и STUArray. Каковы они и в чем разница?
UArray означает «нераспакованный массив» , то есть массив значений, в отличие от массива указателей,Значение в нашем случае на самом деле является символом Unicode, а не C "байтом" char, так что это не байт, а сущность переменного размера. Когда он хранится в распакованном виде, он преобразуется в Int32 и возвращается нам незаметно. Int32, конечно, слишком много для нашей скромной цели хранения 3 различных значений, поэтому здесь есть место для улучшения. Чтобы узнать больше о распакованных значениях, я предлагаю вам ознакомиться со статьей, в которой они были введены еще в 1991 году, «Распакованные значения как граждан первого класса на неограниченном функциональном языке» .
То, что значения распакованы, не означает, что вы можете изменить их. Чистая ценность в Хаскеле всегда неизменна. Итак, если вы измените одно значение в массиве, весь массив будет скопирован - дорого! Вот где приходит STUArray. ST обозначает State Thread, а STUArray представляет собой «незамерзающий» массив , где вы можете перезаписывать отдельные значения, не копируя все это. Для обеспечения безопасности он может жить только в монаде, в данном случае в монаде ST. (Обратите внимание, что значение 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 - это функция, которая может изменять состояние монады и, следовательно, может изменять значение связанных имен, когда они возвращаются. Аналогичный код в 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 работает следующим образом. Я не очень знаком ни с Си, ни с внутренней работой абстракции ST, так что это всего лишь аналогия, а не попытка точного воспроизведения. Тем не менее, я надеюсь, что это поможет читателю заметить сходство между ST и обычным императивным кодом C.
Миссия выполнена!
Она работает достаточно быстро. Требуется всего лишь мгновение, чтобы нарисовать матч на миллион шагов на доске размером в миллион. Я надеюсь, что это также объясняется достаточно четко. Не стесняйтесь комментировать, если что-то не так или неясно.