Here's a toy problem:
A (roguelike) 2D map consists of square cells which each have a material (rock or air).
Each cell has four boundaries (N, S, E and W). Each boundary is shared by two cells.
A boundary can optionally contain a "wall feature" only if one side is rock and the other air.
(Wall features could be levers, pictures, buttons, etc.)
What Algebraic Data Type design could have a place to store a wall feature only when one side is rock and the other air? i.e. the data structure cannot represent a wall feature on a boundary between two air cells or two rock cells.
One approach I've tried is XORing a chess-board pattern over the cell values, reversing changes and non-changed.
I keep getting myself in knots over the fact there are multiple equivalent routes between cells - SSW is the same as SWS (the 1D version of this question is trivial).
(I recognise that the ADT representation will not be particularly 'queriable'.)
Update with Failed Attempt:
Call the East boundaries E and the South boundaries S. Let each boundary be either Same
or Diff Feature
. The problem with this approach is that it lets inconsistent routes exist, such as:
E<0,0> Same
S<1,0> Same
S<0,0> Same
E<0,1> Diff
Is there a mathematical name for saying that different routes must aggregate to the same total?
You could say that Same was 1 and Diff was -1 and that product along every route between any two cells must be equal (either 1 or -1).
I have no idea if this is possible at all with traditional ADTs, but you can do it with GADTs. This has a map infinite in one dimension, and finite in the other: