Seven Languages in Seven Weeks: Haskell Day 3
A few months ago, I tried my hand at Seven Languages in Seven Weeks, and it was an incredibly enlightening experience.
There was one excersize that kept me at odds for weeks though, so I thought I’d share my experience.
Haskell Day 3: Creating and writing a Maze Solver #
The excersize calls for accomplishing two tasks:

Creating a data structure for storing a maze

Write a method to solve it
I think there’s a few ways to organize the data, but I chose a format that was fairly readable:
data Exits = North  West  East  South deriving (Show, Eq)
data Node = NodePath (Int, Int) [Exits]  TerminalNode (Int, Int) deriving (Show, Eq)
type Maze = [[Node]]
testMaze :: Maze
testMaze = [
[ (NodePath (0,0) [South]), (NodePath (1, 0) []), (NodePath (2, 0) []) ],
[ (NodePath (0,1) [East]), (NodePath (1, 1) [East]), (NodePath (2, 1) [North, South]) ],
[ (NodePath (0,2) []), (NodePath (1, 2) []), (TerminalNode (2, 2)) ]
]
Basically, this creates a few types:

Exits, to deal with the directions from which one can move from the current position

Node, which consists of nodes with paths (a NodePath), and a Final node (TerminalNode).

Maze, which is simply a twodimensional array of nodes.
I think there’s liberties here as well, but I wanted to note my choice a NodePath and TerminalNode type: it seemed like creating completely different types altogether allowed me to rely on the strict type of Haskell better to solve my problems, instead of emebedding logic. But YRMV.
One big downside: putting data in structures like this made it hard to get the data I want, and also rely on the typing. Ultimately I had to create several utility methods to help me:
 getNode: Returns a node object given a maze and a position
getNode :: Maze > (Int, Int)> Node
getNode maze (x,y) = maze !! y !! x
 getExits: return all the exits for a node
getExits :: Node > [Exits]
getExits (NodePath _ exits) = exits
getExits (TerminalNode _) = []
 getPosition: return a (x,y) of the position of a node
getPosition :: Node > (Int, Int)
getPosition (NodePath (x,y) _) = (x, y)
getPosition (TerminalNode (x,y)) = (x, y)
I definitely must be doing something wrong here. The rigid typing of Haskell should allow me to take advantage of the inner data without creating accessors like this. But I’m not a Haskell expert, so I made do with what I understood.
Finally, I have all the tools I need to write my solver. Here it is:
 getNextNode: given a node, maze, and an exit, return the next node from the maze
getNextNode :: Node > Maze > Exits > Node
getNextNode node maze exit =
let (x, y) = getPosition node
in
case exit of
North > getNode maze (x, y  1)
West > getNode maze (x  1, y)
East > getNode maze (x + 1, y)
South > getNode maze (x, y + 1)
 If the element already exists in the path, we're at a dead end.
 solveRoute: returns a list of the valid routes to the exit
solveRoute :: Maze > Node > [Node] > Exits > Maybe [Node]
solveRoute maze node path exit =
let nextNode = getNextNode node maze exit
in
if (nextNode `elem` path)
then
Nothing
else
solveMaze maze nextNode (node:path)
 solveMaze: solve the maze by taking solveRoute, filtering the successful results, and taking the first one.
solveMaze :: Maze > Node > [Node] > Maybe [Node]
solveMaze maze node path =
case node of
TerminalNode _ > Just (node:path)
NodePath _ _>
let nodes = (filter (\x > x /= Nothing) (map (solveRoute maze node path) (getExits node)))
in
if (length nodes > 0)
then
head nodes
else
Nothing
This code probably seems a bit contrived. Basically here’s what solveMaze does:

delegates the logic to solveRoute if the node isn’t a terminalNode

solveRoute gets the exits for the node. it loops through them, takes the valid ones (the ones where the same position isn’t in there twice), and passes them back into solveMaze
So solveMaze and solveRoute call each other until they find a valid solution. I could have added them into the same method, but this seemed like a logical split that made the code a little easier to understand.
This works. Give it a try:
mazeStart = getNode testMaze (0, 0)
mazeSolution = solveMaze testMaze mazeStart []
One of the big issues I have with solution, however, is the fact that it doesn’t use a list monad in any way. And I’m still a bit confused as to how it comes in handy here. From my understanding, a list monad flattens a list of lists into a single list. So ultimately, my solution might not be taking advantage of the real power of Haskell. It is purely functional though, so maybe it is.
Here’s the code in full:
module Day3 where
import Data.List
 data Node = NodePath ((Int, Int), [Node])  TerminalNode (Int, Int)
data Exits = North  West  East  South deriving (Show, Eq)
data Node = NodePath (Int, Int) [Exits]  TerminalNode (Int, Int) deriving (Show, Eq)
type Maze = [[Node]]
testMaze :: Maze
testMaze = [
[ (NodePath (0,0) [South]), (NodePath (1, 0) []), (NodePath (2, 0) []) ],
[ (NodePath (0,1) [East]), (NodePath (1, 1) [East]), (NodePath (2, 1) [North, South]) ],
[ (NodePath (0,2) []), (NodePath (1, 2) []), (TerminalNode (2, 2)) ]
]
 getNode
getNode :: Maze > (Int, Int)> Node
getNode maze (x,y) = maze !! y !! x
 getExists
getExits :: Node > [Exits]
getExits (NodePath _ exits) = exits
getExits (TerminalNode _) = []
 getPosition
getPosition :: Node > (Int, Int)
getPosition (NodePath (x,y) _) = (x, y)
getPosition (TerminalNode (x,y)) = (x, y)
 getNextNode
getNextNode :: Node > Maze > Exits > Node
getNextNode node maze exit =
let (x, y) = getPosition node
in
case exit of
North > getNode maze (x, y  1)
West > getNode maze (x  1, y)
East > getNode maze (x + 1, y)
South > getNode maze (x, y + 1)
 If the element already exists in the path, we're at a dead end.
solveRoute :: Maze > Node > [Node] > Exits > Maybe [Node]
solveRoute maze node path exit =
let nextNode = getNextNode node maze exit
in
if (nextNode `elem` path)
then
Nothing
else
solveMaze maze nextNode (node:path)
 solveMaze 2
solveMaze :: Maze > Node > [Node] > Maybe [Node]
solveMaze maze node path =
case node of
TerminalNode _ > Just (node:path)
NodePath _ _>
let nodes = (filter (\x > x /= Nothing) (map (solveRoute maze node path) (getExits node)))
in
if (length nodes > 0)
then
head nodes
else
Nothing
mazeStart = getNode testMaze (0, 0)
mazeSolution = solveMaze testMaze mazeStart []