Access Patterns Shape Data Structures

Choosing the right data structure

In functional programming, data structures are inextricably linked to functions. Building good programs means considering how those programs use the data. Some data structures are primarily read-only while others exist to be updated. As we saw in the previous chapter, some datatypes are easier to update than others.

Designing the game of tic tac toe

Let’s take a straightforward programming problem representing a tic-tac-toe game. In case this game is unfamiliar, tic-tac-toe is a childhood favorite where two players, denoted by “X” and “O”, take turns putting their markers on a 3x3 grid. The game ends when the first player gets three in a row. We’ll be using a couple of data structures to make this game, starting with the tuple.