Representing map constraints as a ADT

Question

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).

Answer 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:

{-# LANGUAGE GADTs #-}


data Nil
type AirEnd = AirCell Nil
type RockEnd = RockCell Nil

data AirCell next
data RockCell next

data WallFeature = Lever | Picture | Buttons | Etc ()
type Wall = Maybe WallFeature


data RogueStrip contents neighbour where

  AirEnd_ngbAir :: RogueStrip AirEnd AirEnd
  AirEnd_ngbRock :: Wall -> RogueStrip AirEnd RockEnd
  RockEnd_ngbAir :: Wall -> RogueStrip RockEnd AirEnd
  RockEnd_ngbRock :: RogueStrip RockEnd RockEnd

  AirCons_nextAir_ngbAir ::
          RogueStrip          (AirCell next')           neighbourNext
       -> RogueStrip (AirCell (AirCell next')) (AirCell neighbourNext)
  AirCons_nextAir_ngbRock :: Wall ->
          RogueStrip          (AirCell next')            neighbourNext
       -> RogueStrip (AirCell (AirCell next')) (RockCell neighbourNext)
  AirCons_nextRock_ngbAir :: Wall ->
          RogueStrip          (RockCell next')           neighbourNext
       -> RogueStrip (AirCell (RockCell next')) (AirCell neighbourNext)
  AirCons_nextRock_ngbRock :: Wall -> Wall ->
          RogueStrip          (RockCell next')            neighbourNext
       -> RogueStrip (AirCell (RockCell next')) (RockCell neighbourNext)
  RockCons_nextAir_ngbAir :: Wall -> Wall ->
          RogueStrip           (AirCell next')           neighbourNext
       -> RogueStrip (RockCell (AirCell next')) (AirCell neighbourNext)
  RockCons_nextAir_ngbRock :: Wall ->
          RogueStrip           (AirCell next')            neighbourNext
       -> RogueStrip (RockCell (AirCell next')) (RockCell neighbourNext)
  RockCons_nextRock_ngbAir :: Wall ->
          RogueStrip           (RockCell next')           neighbourNext
       -> RogueStrip (RockCell (RockCell next')) (AirCell neighbourNext)
  RockCons_nextRock_ngbRock ::
          RogueStrip           (RockCell next')            neighbourNext
       -> RogueStrip (RockCell (RockCell next')) (RockCell neighbourNext)


data RogueSList topStrip where
  StripCons :: RogueStrip topStrip nextStrip -> RogueSList nextStrip
                                             -> RogueSList topStrip

data RogueMap where
  RogueMap :: RogueSList top -> RogueMap