In my last article, I outlined the purpose of a stock program: a non-trivial coding exercise to be done in every new programming language somebody is learning. I also stated that «Four in a Row» is becoming my personal stock program, and that I'd like to implement it in Haskell.
The main challenge in Haskell is the functional programming paradigm. Immutability is the main difference between an implementation of «Four in a Row» in a functional programming language compared to rather structured programming languages such as C or Python. The object-oriented aspect of an implementation in Python makes hardly any difference, for OOP equally allows for mutable an immutable programming beneath the surface. (In introductory courses on OOP, hidden mutability is rather praised as a virtue than frowned upon; the disadvantages of mutability are only taught in advanced courses by showing the advantages of constructs like immutable classes. Learn and unlearn, but I'm digressing…)
A later re-implementation of my stock program in Python might profit from the experiences made in Haskell. Structured programming also allows for immutability, and list comprehensions allow for compact code to produce new state based on older state, without modifying existing state. (This re-implementation could be subject matter for a fourth article, but let's not get ahead of ourselves.)
In this article, I'm going to show how the board logic for the game «Four in a Row» can be implemented in Haskell.
Let There Be Code
As analyzed in my previous article, the board logic consists of five building blocks:
- Create an empty grid with given dimensions.
- Validate if a move (i.e. the choice of a column) is allowed for a given board.
- Set a player's stone in the right place on the grid based on the choice of a column.
- Detect if a player has won the game by checking if four of the player's stones lay in a horizontal, vertical, or diagonal line.
- Format the grid as a string in order to display it on the command line.
The last building block, formatting, won't be covered in this article. I first have to learn more about strings, formatting, and IO in Haskell, but I don't like to wait to cover the other parts, which I'm already capable of implementing with my current knowledge.
Before implementing the actual logic, let's define a couple of type aliases:
type Grid = [Row] type Row = [Int] type Col = [Int] type Stone = Int
A grid (type
Grid) is a list of rows. A row (type
Row) itself is a list of
integers. As discussed in my previous article, 0 is going to be used for empty
fields. The fields occupied by player one and two shall be represented by the
numbers 1 and 2, respectively.
Just like a row, a column (type
Col) is a list of integers. It is an
alternative way to express the relationships between individual fields. The
Grid, however, uses the
Row type as its building blocks.
Stone is an integer, too. It represents a player's number for fields
occupied by his or her stones.
Those types won't add powerful abstractions to the program, but make the signature of certain functions a bit clearer. (It's also possible to limit the scope of the types declared to certain values, but let's focus on the program logic instead.)
Creating a Grid
new_grid accepts two integer parameters (number of rows and
columns), and produces a grid of those dimensions:
new_grid :: Int -> Int -> Grid new_grid r c = [new_row c | _ <- [1..r]]
A list comprehension is used to build up the grid as a list of
r rows. The
row itself is created by a function
new_row :: Int -> Row new_row c = [0 | _ <- [1..c]]
Again, a list comprehension is used to build a single row consisting of
elements: one per column.
new_grid function can be used as follows (
> indicates the REPL, the
output has been wrapped for better readability):
> new_grid 6 7 [[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0]]
Validating a Move
A move solely consists of a column index. Let's assume a 6x7 grid (6 rows, 7 columns) if nothing else is stated. A valid move must be in the range of 0 (leftmost column) to 6 (inclusive, rightmost column).
For a move to be valid, the column must have an empty field, i.e. it must contain the value 0. Since the columns are filled up from the bottom, a column is not full if its the top-most field is equal to 0. So this validation seems trivial.
However, in order to deal with columns rather than rows (remember, the grid
is defined in terms of rows, not the other way around), we first need a way to
gather the fields of a column. The function
get_column expects a grid and a
column index and returns the fields belonging to that particular column:
get_column :: Grid -> Int -> Col get_column g c = [row !! c | row <- g]
A list comprehension is used to select the element at index
c in every grid
row using the index operator (
is_valid_move simply extracts the column chosen by the player
and checks its topmost field to be empty (equals 0, that is):
is_valid_move :: Grid -> Int -> Bool is_valid_move g c = (get_column g c) !! 0 == 0
(Notice that no boundary checks are implemented throughout the program, unless absolutely necessary for getting the logic right.)
This function can be used as follows:
> g = new_grid 6 7 > is_valid_move g 0 True
Setting a Stone
The first two building blocks were easy to write without modifying state. Performing a move on the grid by setting a stone into a certain column, however, is a step that requires a modification of some sort. The solution is to not mutate the given grid, but to produce a new grid based on the given grid by accounting for a player's move.
apply_move expects a grid, a column (chosen by the player and
is_valid_move), and the player's number (to set the right
value in the new grid):
apply_move :: Grid -> Int -> Int -> Grid
Because only a column is given, the row coordinate has to be figured out. Since stones played are falling down the grid in the physical version of the game, the bottom-most free field of a column has to be found:
bottom_most :: Grid -> Int -> Int -> Int bottom_most g v c = length (takeWhile (\x -> x == v) col) - 1 where col = get_column g c
The lowest free position is found by extracting a subsequent list of a given
v, which can be handed in as an argument. (The value 0 has to be used
for this particular use case by the caller.) The built-in function
is used to extract a list based on a lambda expression: Elements are taken from
the column as long as the lambda expression holds true. The bottom-most position
of a column with the given value
v is simply the length of the extracted sub
list minus one (indexes are zero-based). Again, the
get_column function is
used to get access to the fields of a particular column.
apply_move can be implemented as follows:
apply_move g c p = replace_value g r c p where r = bottom_most g 0 c
Another function is needed:
replace_value, which creates a new grid based on
the existing grid
g, by setting the player's stone value
p to the coordinate
(r,c). (The row coordinate is figured out using
bottom_most, as shown
replace_move is implemented as follows:
replace_value :: Grid -> Int -> Int -> Stone -> Grid replace_value g r c p = take r g ++ [new_row] ++ drop (r + 1) g where new_row = replace_row_value (g !! r) c p
Given the row index
r, the first
r rows are taken. (This excludes the row
to be transformed, because the index is zero-based.) The row at index
new_row in a further step. The remaining rows are extracted from
the existing grid by dropping the first
r + 1 rows from it. Those three
components are concatenated to a new grid using the
new_row looks like the old row at index
r, expect that a single value
c (the column) has to be replaced with the player's value
replace_row_value performs this transformation:
replace_row_value :: Row -> Int -> Stone -> Row replace_row_value r c p = take c r ++ [p] ++ drop (c+1) r
The same logic using
drop can be implemented for the column's
fields like for the grid's rows before. The empty field at column index
simply be replaced by a list solely consisting of the player's stone value
List concatenation is used again to produce the tranformed column.
A move can be applied as follows:
> g = new_grid 6 7 > g1 = apply_move g 3 1 > g1 [[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,1,0,0,0]] > g2 = apply_move g1 4 2 > g2 [[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,1,2,0,0]]
apply_move could also be invoking
is_valid_move for validation. But this
task should be left for the client to be implemented later on.
Detecting a Win
Figuring out whether or not a player's most recent move leads to a win is the hardest part of this program, no matter what implementation language is used. (However, I didn't try Prolog yet for this.) Let's analyze the problem.
First, what do we know? The player with a number (1 or 2) just picked a column (between 0 and 5 in our 6x7 grid). A stone was set in the bottom-most empty field of that column. The actual row where the stone landed in is unknown. However, this information can be found out: it is the top-most row of the chosen column holding the player's stone value. All the fields above must be empty.
Second, what do we need to find out? Starting from the coordinates (given column, row figured out as described above), there are three possibilities to build a row of four values: horizontal, vertical, and diagonal lines. A horizontal line is a row, and a vertical row is a column. Diagonal lines can occur in two directions: ascending or descending. So we actually need to account for four kinds of rows, which need to be extracted from the row/column coordinates.
Third, once the horizontal, the vertical, and the two diagonal lines going through the player's stone most recently set are established, a simple check can be done: Does the line, which can be represented as a list, contain a list of four of the player's stones? If that's the case, the player just won the game.
Let's implement that algorithm in a top-down manner!
is_win expects a grid, a column, and a player's stone value, and
returns a boolean value indicating if the player just won the game:
is_win :: Grid -> Int -> Stone -> Bool is_win g c p = horizontal_win g row p || vertical_win g c p || diagonal_win g row c p where row = top_most g p c
Three predicate functions
handle the three different shapes of winning rows. To check for a vertical win,
the row is irrelevant. For the other wins, the row where the player's stone just
landed in is figured out using the
top_most :: Grid -> Stone -> Int -> Int top_most g v c = length (takeWhile (\x -> x /= v) col) where col = get_column g c
This function expects a grid, a player's stone value, a column, and returns the
top-most row containing the player's stone. Going through the column from top to
bottom, values are read into a list as long as they are not equal to the
player's stone value. The length of that list is the row coordinate of the
player's top-most stone in that column. Again, the column is extracted using the
get_column function explained further above.
Vertical and Horizontal Win
A vertical and horizontal winning row can be detected in the same manner. The only difference is that the former works on columns, and the latter on rows:
horizontal_win :: Grid -> Int -> Stone -> Bool horizontal_win g r p = contained fiar (g !! r) where fiar = [p | _ <- [1..4]] vertical_win :: Grid -> Int -> Stone -> Bool vertical_win g c p = contained fiar (get_column g c) where fiar = [p | _ <- [1..4]]
In both cases, a grid, an index (row or column, respectively), and a player's
stone value is expected. The boolean return value indicates whether or not the
row or column contains a sub-list consisting of four of the player's stone
fiar, which is built using a list comprehension.
For the horizontal win, the row can be directly accessed from the grid using the
row index (
g !! r). For the vertical win, the
get_column function is used
contained is the tricky part. This function checks whether or not
a smaller list (first argument) is part of a larger list (second argument). A
possible implementation looks as follows:
contained :: Eq a => [a] -> [a] -> Bool contained   = True contained  ys = True contained xs  = False contained (x:xs) (y:ys) | x == y = and [x == y | (x,y) <- zip xs ys] && length xs <= length ys || contained (x:xs) ys | otherwise = contained (x:xs) ys
The lists processed can be of any type that supports the comparison operator
Eq a). A boolean value is returned indicating whether or not the first list
is contained in the second list. The function is implemented using pattern
matching, which covers the following cases:
- An empty list is contained in another empty list (first base case).
- An empty list is contained in any non-empty list (second base case).
- A non-empty list is not contained in an empty list (negative base case).
- A non-emtpy list is possibly contained in another non-empty list (complex case).
The «possibly» in the fourth case can be resolved as follows: If the first
elements of the two lists do match, the remainders of the two lists need to be
checked for a match. A list comprehension zipping those tails together and
comparing the corresponding elements creates a list of booleans indicating
matches. If all those booleans are
True, the first list must be contained in
the second list, if the second list is at least as long as the first list.
(Notice that the
zip function only picks values until the shorter of the two
zipped lists is exhausted. The length check ensures that the comparison of the
lists does not end prematurely.)
otherwise case is processed when the two list's heads do not match. In
this case, the
contained function is invoked again with the full first list
and the second's list tail: It shall be checked whether or not the first list is
contained in the second's list tail.
Detecting a diagonal win works in the same manner as detecting a horizontal or vertical win. However, there are two subtle details that make the implementation more complicated:
First, there are two kinds of diagonal lines: ascending and descending. This can be handled by implementing two different functions.
Second, extracting a diagonal line as a list from the two-dimensional grid is much more complicated than extracting a horizontal line (row) or a vertical line (column).
Let's start with the
diagonal_win function, which accounts for both winning
rows in ascending or descending order:
diagonal_win :: Grid -> Int -> Int -> Stone -> Bool diagonal_win g r c p = contained fiar (diag_asc g r c) || contained fiar (diag_desc g r c) where fiar = [p | _ <- [1..4]]
The function expects a grid, both row and column indication, and the player's stone value. As always, a boolean value indicating a win is returned. A win is detected, if the list of four player's stone values is contained in either the ascending or the descending diagonal line.
Those lines are extracted from the grid using the
functions, respectively. The two functions look quite similar, but have subtle
differences in the way they process the grid:
- An ascending row starts at the bottom of the grid, i.e. with the highest row index. It starts at the left, i.e. with the lowest column index.
- A descending row starts at the top of the grid, i.e. with the lowest row index. It also starts at the left, and, thus, with the lowest column index.
diag_asc expects a grid and both row and column indices. It
returns the ascending diagonal row containing that coordinate:
diag_asc :: Grid -> Int -> Int -> [Int] diag_asc g r c = [g !! i !! j | (i,j) <- zip rows cols] where nrows = length g ncols = length (g !! 0) offset = max (min (nrows - r - 1) (ncols - c - 1)) 0 max_row = r + offset min_col = c - offset rows = reverse [0..max_row] cols = [min_col..ncols-1]
The function is implemented using a list comprehension. The variable
i is the
j the column index. Those indices are obtained by zipping a list of
row indices (
rows) with a list of column indices (
cols). The starting and
end point of those lists are the tricky part.
Consider this grid, in which
- stands for an empty field, and the upper-case
F for the field played most recently (with the
c arguments as
indices). All the fields indicated with a lower-case
f are to be extracted for
the ascending diagonal holding the upper-case
! 0 1 2 3 4 5 6 - - - - - - f 0 - - - - - f - 1 - - - - f - - 2 - - - f - - - 3 - - F - - - - 4 ! - f - - - - - 5
The row and column indices of
F are given as 4 and 2. The starting point at
the bottom-left can be figured out by shifting the coordinates by an offset.
This offset is the smaller value of the following two differences:
rows - r - 1: the number of rows minus the row index (minus one to account for the zero-based row index)
cols - c - 1: the number of columns minus the column index (minus one; zero-based index again)
The offset is set to 0, if either difference becomes negative (boarder clipping). The offset is calculated as follows:
offset = max (min (nrows - r - 1) (ncols - c - 1)) 0 offset = max (min (6 - 4 - 1) (7 - 2 - 1)) 0 offset = max (min 1 4) 0 offset = max 1 0 offset = 1
And the starting points
min_col (bottom left) are calculated based
on the given indices of
F as follows:
max_row = r + offset max_row = 4 + 1 max_row = 5 min_col = c - offset min_col = 2 - 1 min_col = 1
The diagonal line can be drawn up to the row index 0 and the column index 6.
Here, it is possible to always use the maximum value, because the
will stop picking values once the shorter list is exhausted.
The number of rows and columns can simply be figured out using the
function applied on the grid as a whole and on a single row thereof:
nrows = length g ncols = length (g !! 0)
Notice that in order to create a list containing the falling values from
max_row down to 0 (
rows), a rising list from 0 to
max_row has to be
created and reversed:
> reverse [0..max_row] [0,1,2,3,4,5]
The other way around, an empty list would be created:
> [max_row..0] 
The somewhat easier to understand function
diag_desc is simply pasted here
without any further comments. Figuring out how it works is left to the reader.
The extensive comments above on
diag_asc certainly help for this purpose:
diag_desc :: Grid -> Int -> Int -> [Int] diag_desc g r c = [g !! i !! j | (i,j) <- zip rows cols] where offset = min r c min_row = r - offset min_col = c - offset nrows = length g ncols = length (g !! 0) rows = [min_row..nrows-1] cols = [min_col..ncols-1]
The complete board logic required to implement a basic «Four in a Row» game has been implemented in Haskell. The whole code described, plus some additional attempts to format the grid as a string, can be found on GitHub.
The linked code also defines a module
Board which exports the public interface
of the board consisting of the four building blocks discussed in this article
and its predecessor. The file
defines a couple of unit tests written in HUnit for basic verification of the
The actual board logic requires a little less than 100 SLOC. Comparable implementations I've written in Python and C only take up slightly more lines. I could have made some functions shorter, but probably not clearer with my limited knowledge of Haskell.
contained function, for example, looks a bit bulky, but actually contains
very little logic. It is possible that the negative base case could be
eradicated, because a length check is already performed in the complex case.
However, I rather have a clear statement of the base cases than saving an easy
to understand line of code.
I might revisit this code and improve it as my knowledge of Haskell improves. But the next step in my journey is to implement an interactive game based on this board, which will be the subject of an article to be published in weeks or maybe months.