Iterate over all (Row, Column) possibilities?

Question

This will be a TicTacToe implementation:

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

As you can see, the initialField is just an empty list and as players make moves, (pos, player) tupels will get added to the list. So far so good. But now I have trouble writing a possibleMoves :: Field -> [Pos] function to get the empty fields. How do I iterate over all Row, Column possibilities in Haskell? I get the feeling that my approach is wrong, but I'm new to Haskell so I have no better idea.

Answer 1

We can get all positions with list comprehensions (see also the other answers)

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

and all plays with a map

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

Then we can define possibleMoves (you will need to import Data.List to get \\, list difference):

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

A somewhat more compact version takes advantage of list comprehension constraints:

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

Answer 2

All rows (ref = Getting a list of all possible data type values in Haskell):

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

All columns:

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

The compute the Cartesian product to find all possibilities (ref = Cartesian product of 2 lists in 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)]

Answer 3

If you want an ultra short, "ulta-Haskelly" version:

enumAll :: (Bounded a, Enum a) => [a]
enumAll = [minBound..maxBound]

positions :: [Pos]
positions = (,) <$> enumAll <*> enumAll

(You'll also need to import Control.Applicative for the <$> and <*> operators)

Then in ghci:

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

How the hell does this work?

enumAll is just a generic helper function (I was surprised not to be able to quickly find it in the standard libraries; it's possible I missed it and you don't even need to define it yourself). It gives you a list of every possibility for any bounded enumerable type. It's fairly straightforward; Bounded means the type has minBound and maxBound, Enum means you can use the [a..b] syntax to get a list of everything from a to b.

(,) is just the pair-building function. If you type :t (,) into ghci, it tells you (,) :: a -> b -> (a, b).

Now, what about those weird <$> and <*> symbols? They're basically "special" forms of function application. So you can read it almost like we're simply applying (,) to the two arguments enumAll and enumAll. But because it's "special" application, it doesn't just give us the pair (enumAll, enumAll).

What we're doing here is using the Applicative instance for lists. I'm not going to get into that in full detail, but what this does is help us think that [Row] is not a list of row values, but rather a single "unknown" row value. It's a value that could be any element of the list, but we don't know which one. The technical term usually used for this is that [Row] can be thought of as a nondeterministic Row; it's a Row value that could be a number of possibilities, but we haven't been able to determine which one it actually is.

So what we're doing is applying the function (,) (which just takes two arguments to build a pair), to two nondeterminsitic values, to get a nondeterminsitic pair (this is where we need the "special" version of function application with <$> and <*>; if we apply (,) normally with (,) enumAll enumAll or build the pair directly with (enumAll, enumAll) then all we get is a normal pair of nondeterminsitic values, instead of a nondeterministic pair of normal values - ([a], [b]) vs [(a, b)]) . And if I take a pair from all possibilities of one bounded enum and all possibilities of another bounded enum, then I should get all possibilities of pair! Which is exactly what happens.

The type signature positions :: [Pos] is actually necessary here. That's what tells Haskell we're building a list of (Row, Column) pairs rather than any other kind of pair of enums, which is how it knows that the first enumAll was enumerating all rows and the second wsa enumerating all columns. The most general type (,) <$> enumAll <*> enumAll is actually (Enum a, Bounded a, Enum b, Bounded b) => [(a, b)], which will work just fine but is a pain to work with interactively in ghci because you'll keep getting ambiguous type variables whenever you try to print things.