1import qualified Data.Map.Strict as Map
2import qualified Data.Set as Set
3
4type Pos = (Int, Int)
5type Grid = Map.Map Pos Char  -- '.' = open, '#' = wall
6
7-- Parse a string grid into a Map
8parseGrid :: [String] -> Grid
9parseGrid rows = Map.fromList
10    [ ((r, c), ch)
11| (r, row) <- zip [0..] rows , (c, ch)  <- zip [0..] row ] exampleGrid :: [String] exampleGrid = [ ".#..." , "..#.." , "###.." , "....#" , ".#..." ] ``` ## BFS for Unweighted Grid BFS explores all cells at distance d before any at distance d+1, guaranteeing the shortest path on an unweighted grid: ```haskell import Data.Sequence (Seq, ( | >), ViewL(..)) import qualified Data.Sequence as Seq bfs :: Grid -> Pos -> Pos -> Maybe [Pos] bfs grid start goal = go (Seq.singleton (start, [start])) Set.empty where go queue visited | Seq.null queue = Nothing | pos == goal    = Just (reverse path) | pos `Set.member` visited = go rest visited | otherwise = go (foldl ( | >) rest newEntries) visited' where ((pos, path) :< rest) = Seq.viewl queue  -- Dequeue front visited' = Set.insert pos visited neighbors = getNeighbors grid pos newEntries = [ (n, n : path) | n <- neighbors , not (n `Set.member` visited') ] getNeighbors :: Grid -> Pos -> [Pos] getNeighbors grid (r, c) = [ pos |
12| --- | --- | --- | --- | --- | --- | --- | --- |
13| BFS | Unweighted | Yes | O(V + E) |
14| Dijkstra | Weighted | Yes | O((V + E) log V) |
15| A\* | Weighted + heuristic | Yes (admissible h) | O((V + E) log V) |
16| DFS | Any | No | O(V + E) |
17
18## Common Pitfalls
19
20* **Using lists as queues**: Haskell lists are efficient for stack (LIFO) operations but O(n) for queue (FIFO) operations. Use `Data.Sequence` for BFS queues — it provides O(1) amortized enqueue and dequeue.
21* **Forgetting the visited set**: Without tracking visited nodes, BFS and A\* will loop infinitely on grids with cycles (which all grids have, since you can go back and forth between adjacent cells).
22* **Manhattan heuristic on diagonal grids**: The Manhattan distance heuristic (`|dx| + |dy|`) is only admissible for 4-directional movement. For 8-directional movement (with diagonals), use Chebyshev distance (`max(|dx|, |dy|)`).
23* **Lazy evaluation and space leaks**: Haskell's lazy evaluation can cause unevaluated thunks to accumulate in the priority queue. Use `Data.Map.Strict` and `seq` or `BangPatterns` to force evaluation where needed.
24* **Immutable data structure overhead**: Persistent `Set` and `Map` operations are O(log n) vs O(1) for mutable hash sets. For very large grids, this can matter. Consider `Data.HashSet` from the `unordered-containers` package for better constants.
25
26## Summary
27
28* Use BFS with `Data.Sequence` for shortest path on unweighted grids — guaranteed optimal
29* Use A\* with Manhattan distance heuristic for faster search on large grids
30* Represent the grid as `Data.Map.Strict (Int, Int) Char` for efficient lookup
31* Track visited cells with `Data.Set` to avoid revisiting
32* Use `Data.Sequence` (not lists) as the BFS queue for O(1) enqueue/dequeue
33* Visualize paths by overlaying `*` on the original grid