I've recently found myself solving a lot of 2D matrix search problems. A typical approach looks like the skeleton below, which searches for a word along 4-directionally connected paths in a 2D array:
data State = S { word :: String, coord :: Coord } deriving (Eq, Ord, Read, Show)
data Coord = C Int Int deriving (Eq, Ord, Read, Show)
dfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
coordMap :: [[a]] -> Map Coord a
cardinals :: Coord -> [Coord]
neighbors :: Map Coord Char -> State -> [State]
solution :: [[Char]] -> String -> Bool
solution board w = any found . search . states w $ board
where
search = dfsOnN coord (neighbors vals)
found = (== "") . word
vals = coordMap board
The DFS function with signature
dfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
takes a projection function, which sends states to representations suitable for a visited set, and a successors function, which computes neighbors in the graph.
My trouble is the successors function. As you can tell from the type signature of neighbors, I usually map locations to values and perform lookups on neighboring coordinates to get successors. But this strikes me as a very roundabout way to do things. If we're always given our matrix as a list of lists, the list already "knows" what stuff is nearby, since it's sequential.
In many problems like these, the only reason we translate to coordinates/indices at all is to perform the index arithmetic to get neighbors. The coordinates themselves are completely superfluous to the problem. We also have to bother with lookups that can fail and do Maybe handling if we use something like a Map Coord Char, but this should also be unnecessary. The list of lists already "knows" where its bounds are, and we throw this information away when we translate to coordinates.
Question: Is there a concise way to implement a fast, total a -> [a] neighbors function for 2D matrix problems that doesn't use coordinates?
Constraints:
base, containers, unordered-containers, fgl, heaps, etc.)!!, head, maximum, etc.O(log n).Why the specific constraints? Simply because I already know how to solve it without these constraints. I'm interested in finding a principled approach to these sorts of problems which will work well for competitive programming when a large custom template library is not allowed.
Ideas towards a solution: I wonder if something like a 2D zipper could work.
Note: I asked a question whose title is similar here, but these are quite unrelated, as a value of type [[NonEmpty a]] or similar is not "compatible" with a DFS function like the one above. It appears as though there is no nice way to grab a value from the list of neighbors of a cell and then in O(1) be able to grab its neighbors in turn, because this would require us to index back into the list in the correct location, but we've thrown all information about location away in this representation.
Sure, just use neighbors from this grand-linked answer. Then you can write
neighborMap :: Ord a => [[a]] -> Map a [a]
neighborMap ss = M.fromListWith [(k, [v]) | (k, v) <- neighbors ss]
-- OR, to save 11 tokens at the cost of sanity
neighborMap = M.fromListWith . fmap (fmap pure) . neighbors
It might not meet your "concise" requirement, I guess, weighing in somewhere around 200 tokens if you include type signatures. Then again I'm a bit surprised that you can do what you say in 100 tokens; I count almost 70 just in the declarations of State, Coord, coordMap, cardinals, and neighbors in the code you posted, which is most of your budget used up before you even start writing function implementations.
You can avoid Maybes in your lookup by using M.findWithDefault []. (I have sometimes wished for a newtype wrapper around Map that handled such things a bit more gracefully, with e.g. fromList :: Monoid v => [(k, v)] -> MonoidMap k v and lookup :: Monoid v => k -> MonoidMap k v -> v. The total-map package gets partway there with its (!), but its fromList analogues often aren't quite as nice as I'd like.)