# Changing an element in a list when a predicate holds

My current project is a Settlers of Catan server in Haskell. I often manage to achieve my goals within Haskell, but the code is getting messier as the project grows.

My question is about the placeBuilding :: Board -> Building -> VertexCoordinate -> Board function that places a building on the board at a specified VertexCoordinate.

Board has a property vertices :: [Vertex], and Vertex is contains a property vertex_coordinate :: ((Int, Int), Int)

My question is about three different attempts for this function:

First of all, would you do anything different in any of the attempts?

For my first attempt I first found the vertex_index of [Vertex] that the building should be placed on, and then with the lens package I change it. This feels natural to me, but it looks rather ugly, especially because of the way I have to deal with the fromMaybe, for which I now make the assumption that the supplied VertexCoordinate must exist.

-- ATTEMPT 1
-- Return a board with the supplied building placed at the supplied coordinate
placeBuilding :: Board -> Building -> VertexCoordinate -> Board
placeBuilding board building coord = board {vertices = vertices'}
where v_index = fromMaybe 0 $findIndex (\v -> vertex_coordinate v == coord) (vertices board) vertices' = vertices board & element v_index .~ Vertex coord (Just building)  Now the second and third are kind of similar. Is one better than the other? Personally, I think the third is the most readable. -- ATTEMPT 2 -- Return a board with the supplied building placed at the supplied coordinate placeBuilding2 :: Board -> Building -> VertexCoordinate -> Board placeBuilding2 board building coord = board {vertices = vertices'} where vertices' = map (\v -> if vertex_coordinate v == coord then Vertex coord (Just building) else v) (vertices board) -- ATTEMPT 3 -- Return a board with the supplied building placed at the supplied coordinate placeBuilding3 :: Board -> Building -> VertexCoordinate -> Board placeBuilding3 board building coord = board {vertices = map placeIfAtCoord$ vertices board}
where placeIfAtCoord v | vertex_coordinate v == coord = Vertex coord (Just building)
| otherwise                    = v

• Have you thought about using a map to map coordinates to buildings? i.e. vertices :: Board -> Map VertexCoordinate Building? If this is not viable for some reason, then your 3rd attempt is the most readable to me. Apr 8 at 22:22
• @Andrew Hmm, so bascially store the vertices/buildings as their lookup variable (i.e. vertexcoordinate). Would I store that in Board (alongside or instead of the current vertices?)? Or would it just be another function that, given a Board, returns the map, which I can then use? Apr 9 at 6:40
• If vertices are always identified by their coordinate, then a mapping from coordinates to vertices makes sense to me. Then there's no need to store the vertices separately, you can use elems :: Map k a -> [a] to get a list of these, if needed. I think having it as a member of the Board is fine, since then Haskell will generate a function vertices :: Board -> Map VertexCoordinate Building for you. Apr 9 at 10:06

I'm not super familiar with Catan, having played it only once in my life and not even to completion, but a grid's a grid, and hex grids can be modeled using three axes instead of the usual two. The data structure you're searching for is an Array. (Or a Vector, if you wanna get fancy with mutability.)

Before I get to the demo, just a few notes on your various versions. #1 lies, if there's no match it just returns the first element in the array. The right thing to do is crash, or if you're feeling nice you can make your return value a Maybe Board. Returning the wrong thing is a good way to end up with subtle bugs that corrupt your data which you still just have to track down later, crashes get fixed. All your versions clobber any building that was already in that coordinate, which I have no idea if that's a thing that you do in Catan or not but I'm going to assume it's an illegal move.

These sorts of problems are easy to lose in the line noise when you haven't modeled your data correctly. One dimensional linked lists are great, but they're not the solution to everything. So, on to Arrays. You find them in the “array” package, which is part of the Haskell 2010 standard so you can expect it to be present in all modern compilers (GHC, GHC, and uh... GHC).

I've no idea what your vertex_coordinate :: ((Int, Int), Int) is supposed to represent (aside, use camelCase for your Haskell names, and did you intentionally choose a 2-tuple containing a 2-tuple over just using a 3-tuple?) but hexagonal grids are easy, especially hexagonally shaped ones like the Catan board is. Instead of just x- and y-coordinates, you use x-, y- and z-coordinates representing ↗, ↖, and ↓. Now the trick is to recognize that the axes aren't independent like in the Cartesian plane, they actually have a relation. Try drawing out a grid and figuring out what that is.

Hint:

Remember that the origin is at $$\(0,0,0)\$$.

Solution:

Using the arrows as given above for the positive direction of each axis, you'll notice that $$\x + y + z = 0\$$.

Now if I remember correctly Catan boards have a radius of 2, so we'll make an empty board.

type Coordinate = (Int, Int, Int)
type Board = Array Coordinate (Maybe Building)

emptyBoard :: Board
emptyBoard = listArray ((-2, -2, -2), (2, 2, 2)) (repeat Nothing)


And then write a place function that maintains the game logic.

placeBuilding :: Board -> Coordinate -> Building -> Either String Board
placeBuilding board coord@(x, y, z) building
| x + y + z /= 0 = Left "Invalid coordinate"
| not (inRange (bounds board) coord) = Left "Coordinate out of range"
| otherwise = case board ! coord of
Just _ -> Left "Coordinate occupied"
Nothing -> Right \$ board // [(coord, Just building)]

• Thank you for the insights. I model my face-coordinates as an x and y coordinate. And then for each face I have a left and a right vertex. So the vertex coordinate is modeled as ((x, y), Left) for example. Is using either for these types of error messages a good way to work? How do you propogate them, since the chain of functions that calls placebuilding can become quite long. Jun 24 at 16:18