Charlie Harvey

Haskell — Day Three

The last day of my seven languages odyssey has been without doubt the most brain frying of all. I needed to spend about four days of fairly intense study to get close to a viable maze solver. Even now I doubt very much that its anything more than a naïve and buggy implementation. Still, the good side is that I have learned a fair bit of Haskell. And sworn a lot. I’ve still yet properly to grok the concept of a monad. I’ve not attempted the implementation of a monad in another language. Perhaps I will in the future. But I need to wait for my brain to stop bleeding first.

I note that I’m not the only programmer to have struggled with this chapter from which I take some comfort. There is a fantastic implementation by Frédéric Dumont, which I sort of half get. If you got here Googling for a solution to the maze problem, I can recommend his as better, more complete and more elegant.

HashLookup.hs

Write a function that looks up a hash table value that uses the Maybe monad. Write a hash that stores other hashes, several layers deep. Use the Maybe Monad to retrieve an element for a hash key several levels.

The major struggle here was getting some test data set up. Haskell was rather insistent on my 'hashtable' being balanced. I got bracket blindness. Once I’d worked out my data, retrieving it worked as expected. We return Nothing if the key is not defined. Otherwise, we use pattern matching to pull off the key, value and rest. If the key is the one we’re looking for then we are done and we return Just the value. Otherwise we call ourselves recursively on rest. This works inmy imagination and for my test data.module HashLookup where retrieve :: Eq a => a -> [(a, b)] -> Maybe b retrieve _ [] = Nothing retrieve key ((k,v):rest) = if key == k then Just v else retrieve key rest testData = [ ("left", [("Punk",[("Sid","Vicious")]), ("Caveman",[("Fred","Flintstone")]), ("Ex-PM",[("Gordon","Brown")]) ] ), ("right", [("Chips",[("Ketchup","Salt")]), ("Bean",[("Chilli flakes","Brown sauce")]) ] ) ]

And here that is in action[1 of 1] Compiling HashLookup ( hashlookup.hs, interpreted ) Ok, modules loaded: HashLookup. *HashLookup> retrieve "right" testData >>= retrieve "Chips" >> retrieve "Ketchup" Just "Salt" *HashLookup>

Maze.hs

Represent a maze in Haskell. You'll need a Maze type and a Node type as well as a function to return a node given its coordinates. The Node should have a list of exits to other Nodes.

Well, I wasn’t convinced that I actually needed co-ordinates for my nodes or a dedicated Maze type. My Maze is just an array of arrays of Nodes. Instead of kerfuffling around with co-ordinates, I keep a list of exits (accessible neighbouring nodes) as a part of the Node type. I’ve left the co-ordinates in there, but they aren’t used. A Node also has a name (for convenience, no more) and can be marked as being the finish of the maze with a Bool is_finish field. I found the record syntax after a long run at building exactly the functions that it makes trivial. data Node = Node { xcoord::Int, ycoord::Int, neighbours::[Node], is_finish::Bool, name::String } deriving (Show,Eq)

Now that we’ve defined a Node type, we make some Nodes. Which are our Maze. We’re really building a list in which each node can be linked 0..n times. If you look at it in a certain way. n1 = Node{ xcoord=0, ycoord=0, neighbours=[n2], is_finish=False, name="n1" } n2 = Node{ xcoord=1, ycoord=0, neighbours=[n3], is_finish=False, name="n2" } n3 = Node{ xcoord=0, ycoord=1, neighbours=[n4], is_finish=False, name="n3" } n4 = Node{ xcoord=1, ycoord=1, neighbours=[], is_finish=True, name="n4" } n5 = Node{ xcoord=1, ycoord=2, neighbours=[n4,n3], is_finish=False, name="n5" } n6 = Node{ xcoord=2, ycoord=2, neighbours=[], is_finish=False, name="n6" }

Use a List monad to solve the maze

I took the approach of ugly brute force. Mostly because I have yet fully to grok the Haskell syntax, and doing anything more elegant results in a litany of type failures. The first function is named all_exits though it might perhaps better be called all paths. It recursively builds up a big list of all the nodes that we can get to from this node. -- Given a starting node, recursively list that node and all the exit -- nodes of that node, and all the exit nodes of the exit nodes of the -- node and so on all_exits node acc | neighbours node == [] = [node] | otherwise = do n <- neighbours node; let { nextLot = all_exits n acc }; (node:nextLot)

If you’re with me so far then what I am counting on is that the first sublist that ends in the finishing node is a solution to the maze. That should be the case in a directed graph. We will go into an infinite recursion if we have nodes that point to each other like n1 pointing to n2 which points to n1 and n3. The solve function displays just the first solution, not the best solution. -- If we get a finish node, return the preceding nodes and that node -- Otherwise this algorithim ain't solving it, so pass back the empty -- list solve start_node = let (pathNodes,finishNodes) = break (\n -> is_finish n == True ) $ all_exits start_node [] in if length finishNodes < 1 then -- we didn't get a solution [] else pathNodes++[head finishNodes]

There are a couple of imports required for the code above. Putting everything together we getmodule Maze where import Data.List import Control.Monad data Node = Node { xcoord::Int, ycoord::Int, neighbours::[Node], is_finish::Bool, name::String } deriving (Show,Eq) n1 = Node{ xcoord=0, ycoord=0, neighbours=[n2], is_finish=False, name="n1" } n2 = Node{ xcoord=1, ycoord=0, neighbours=[n3], is_finish=False, name="n2" } n3 = Node{ xcoord=0, ycoord=1, neighbours=[n4], is_finish=False, name="n3" } n4 = Node{ xcoord=1, ycoord=1, neighbours=[], is_finish=True, name="n4" } n5 = Node{ xcoord=1, ycoord=2, neighbours=[n4,n3], is_finish=False, name="n5" } n6 = Node{ xcoord=2, ycoord=2, neighbours=[], is_finish=False, name="n6" } -- Given a starting node, recursively list that node and all the exit -- nodes of that node, and all the exit nodes of the exit nodes of the -- node and so on all_exits node acc | neighbours node == [] = [node] | otherwise = do n <- neighbours node; let { nextLot = all_exits n acc }; (node:nextLot) -- If we get a finish node, return the preceding nodes and that node -- Otherwise this algorithim ain't solving it, so pass back the empty -- list solve start_node = let (pathNodes,finishNodes) = break (\n -> is_finish n == True ) $ all_exits start_node [] in if length finishNodes < 1 then -- we didn't get a solution [] else pathNodes++[head finishNodes]

We can test this out in the GHCi REPL. We’ll test first with Node n1 as the start point. We should see that report a path from n1->n2->n3->n4 . Just to check that we’re good for when we’re already at the finish we will also test n4. And to see what happens when we go to an unconnected Node we will also try n6 (we hope for an empty list for that one).*Maze> :l maze.hs [1 of 1] Compiling Maze ( maze.hs, interpreted ) Ok, modules loaded: Maze. *Maze> map (name) $ solve n1 ["n1","n2","n3","n4"] *Maze> map (name) $ solve n4 ["n4"] *Maze> map (name) $ solve n6 [] *Maze> Well that’s good enough for now, and that is also me done for my final Seven Languages excercise. I intend to do a wrapping up post later on, but now it is time for a celebrationary beer. Huzzah!


Comments

  • Be respectful. You may want to read the comment guidelines before posting.
  • You can use Markdown syntax to format your comments. You can only use level 5 and 6 headings.
  • You can add class="your language" to code blocks to help highlight.js highlight them correctly.

Privacy note: This form will forward your IP address, user agent and referrer to the Akismet, StopForumSpam and Botscout spam filtering services. I don’t log these details. Those services will. I do log everything you type into the form. Full privacy statement.