Shortest Path (BFS) through a maze
General Comments


mkEdges



I would probably just call this function edges.  mk (which I assume is short for make) has an imperative ring to it.


bfsPathLength :: Int -&gt; Index -&gt; [State] -&gt; Int



You are forcing users of bfsPathLength to pass an initial state.  This forces them to be aware of the internal details of the algorithm, which is not a good design.  You could get rid of the [State] parameter and have bfsPathLength delegate to a helper function that takes the initial state.  Public interfaces should never expose details that aren't necessary.


bfsReachableLocations :: Int -&gt; [(Int, Index)] -&gt; [Index] -&gt; Int 




What's the purpose of this function?  It doesn't appear to be used for computation of the actual answer to the riddle.  If it's for debugging purposes, you should add a comment that says so (be sure to include what it actually does, and why it's useful for debugging as well).
Also, once again you force users to incorporate knowledge about the internal state of the algorithm.


Performance

You perform a linear search for nodes in the queue and the visited set.  You should use a more appropriate datastructure, such as a set, that can do the search in \$O(\log{n})\$, or even \$O(1)\$, time.

Abstraction


Consider separating the graph generation from the search algorithm.  This will allow you to use BFS search to solve other problems.  You have some options here, including:


Turn mkEdges into a parameter to the search function.
Use a typeclass.


For example, if you turn mkEdges into a parameter (and remove the internal state parameter), bfsPathLength might have the following type signature:

bfsPathLength :: (a -&gt; [a]) -&gt; a -&gt; Int 
bfsPathLength edgeGenerator goalLocation = ...

You should parameterize the start location:

bfsPathLength :: (a -&gt; [a]) -&gt; a -&gt; a -&gt; Int
bfsPathLength edgeGnerator startLocation goalLocation = ...

It seems like it would be useful to be able to find the actual path in most cases, rather than just the length:

bfsPath :: (a -&gt; [a]) -&gt; a -&gt; [a]


Then you can write bfsPathLength as follows:

bfsPathLength :: (a -&gt; [a]) -&gt; a -&gt; a-&gt; Int
bfsPathLength edgeGenerator startLocation = length . (bfsPath edgeGenerator startLocation)