Итерации над всеми возможностями (Row, Column)?

Это будет реализация TicTacToe:

data Row = A | B | C deriving (Show, Read, Eq, Ord, Enum, Bounded)
data Column = X | Y | Z deriving (Show, Read, Eq, Ord, Enum, Bounded)
type Pos = (Row, Column)
data Player = Player String
data Field = Field [(Pos, Player)]
initialField :: Field
initialField = Field []

Как вы можете видеть, initialField - это только пустой список, и по мере того, как игроки делают ходы, в список добавляются тепели (pos, player). Все идет нормально. Но теперь мне трудно написать функцию possibleMoves :: Field -> [Pos], чтобы получить пустые поля. Как перебрать все возможности Row, Column в Haskell? У меня такое чувство, что мой подход неправильный, но я новичок в Haskell, поэтому у меня нет лучшей идеи.

3 ответа

Мы можем получить все позиции со списком (см. также другие ответы)

positions :: [Pos]
positions = [(r,c) | r <- [A,B,C], c <- [X,Y,Z]]

и все игры с отображением

occupied :: Field -> [Pos]
occupied (Field l) = fmap fst l

Затем мы можем определить возможныеMoves (вам нужно будет импортировать Data.List, чтобы получить \\, разницу в списке):

possibleMoves :: Field -> [Pos]
possibleMoves f = positions \\ (occupied f)

В несколько более компактной версии используются ограничения на понимание списков:

possibleMoves :: Field -> [Pos]
possibleMoves (Field l) = [(r,c) | r <- [A,B,C], c <- [X,Y,Z], (r,c) `notElem` occupied]
 where occupied = fmap fst l


Все строки (ref = Получение списка всех возможных значений типа данных в Haskell):

Prelude> [(minBound :: Row) ..]
[A,B,C]

Все столбцы:

Prelude> [(minBound :: Column) ..]
[X,Y,Z]

Вычислить декартово произведение, чтобы найти все возможности (ref = Декартово произведение двух списков в Haskell):

Prelude> [(x, y) | x <- [(minBound :: Row)..], y <- [(minBound :: Column)..]]
[(A,X),(A,Y),(A,Z),(B,X),(B,Y),(B,Z),(C,X),(C,Y),(C,Z)]


Если вам нужна ультра короткая версия "ulta-Haskelly":

enumAll :: (Bounded a, Enum a) => [a]
enumAll = [minBound..maxBound]
positions :: [Pos]
positions = (,) <$> enumAll <*> enumAll

(Вам также потребуется импортировать Control.Applicative для операторов <$> и <*>)

Тогда в ghci:

*Main> positions
[(A,X),(A,Y),(A,Z),(B,X),(B,Y),(B,Z),(C,X),(C,Y),(C,Z)]

Как, черт возьми, это работает?

enumAll - всего лишь общая вспомогательная функция (я был удивлен тем, что не смог быстро найти ее в стандартных библиотеках, возможно, я пропустил ее, и вам даже не нужно ее самостоятельно определять). Он дает вам список всех возможностей для любого ограниченного перечислимого типа. Это довольно просто; Bounded означает, что тип имеет minBound и maxBound, Enum означает, что вы можете использовать синтаксис [a..b] для получения списка всего от a до b.

(,) - это просто функция построения пар. Если вы наберете :t (,) в ghci, он сообщает вам (,) :: a -> b -> (a, b).

Теперь, как насчет этих странных символов <$> и <*>? Они в основном являются "специальными" формами применения функций. Поэтому вы можете прочитать это почти так, как будто мы просто применяем (,) к двум аргументам enumAll и enumAll. Но поскольку это "специальное" приложение, оно не просто дает нам пару (enumAll, enumAll).

Что мы здесь делаем, используйте экземпляр Applicative для списков. Я не буду подробно разбираться в этом, но то, что это делает, помогает нам думать, что [Row] - это не список значений строк, а одно значение неизвестного значения. Это значение, которое может быть любым элементом списка, но мы не знаем, какой из них. Технический термин, обычно используемый для этого, состоит в том, что [Row] можно рассматривать как недетерминированный Row; это значение Row, которое может быть несколькими возможностями, но мы не смогли определить, какой из них он на самом деле.

Так что мы делаем, применяя функцию (,) (которая просто берет два аргумента для построения пары), до двух неопределенных значений, чтобы получить недетерминированную пару (здесь нам нужна "специальная" версия с <$> и <*>, если мы применим (,) обычно с (,) enumAll enumAll или создадим пару непосредственно с помощью (enumAll, enumAll), тогда мы получим нормальную пару недетерминированных значений вместо недетерминированной пары нормальных значения - ([a], [b]) vs [(a, b)]). И если я возьму пару из всех возможностей одного ограниченного перечисления и всех возможностей другого ограниченного перечисления, тогда я должен получить все возможности пары! Что именно происходит.

Здесь действительно нужна подпись типа positions :: [Pos]. Это то, что говорит Haskell, мы строим список пар (Row, Column), а не любой другой вид переименований, так как он знает, что первый enumAll перечислял все строки, а второй wsa перечислял все столбцы. Самый общий тип (,) <$> enumAll <*> enumAll на самом деле (Enum a, Bounded a, Enum b, Bounded b) => [(a, b)], который будет работать просто отлично, но это боль для интерактивного взаимодействия в ghci, потому что вы будете получать неоднозначные переменные типа всякий раз, когда пытаетесь распечатать вещи.

licensed under cc by-sa 3.0 with attribution.