Archive

Archive for September, 2010

Prefix Trees in Haskell

September 13, 2010 1 comment

As part of an interview, I was recently challenged to define a data type to represent prefix trees, along with lookup and insert functions. I was allowed to use any language of my choice, so decided to use Haskell. This blog post will introduce what a prefix tree is, and then cover my implementation. There may well be better implementations of prefix trees, but I was quite pleased with the functional representation that I ended up using.

Prefix Trees
The best way to define a prefix tree may well be with the aid of the following small diagram:

A Sample Prefix Tree

It is a data structure that stores values associated with certain keys. The key is used to traverse a branch of the tree. Not all nodes of the tree have to contain data, and in this instance, a key is only associated with a single piece of data. For example, in the diagram above, the prefixes (which form the keys) are the lower case letters on each branch, and the data is represented by the capital letters at (some of) the nodes.

In this highlighted example, the key “a” has no data associated with it, the key “ab” is associated with the data ‘N’, the key “abc” has no data associated with it, and the key “abcd” is associated with the data ‘X’.

The Key "abcd" Highlighted

Haskell

The first thing to decide is the types that represent the keys and data in the tree. In fact, we can make this definition polymorphic, and use any arbitrary data types for each of these. However, we’ll see later that we need to be able to compare the elements that form a key in order to define the insert function. A key is then formed by a list of the relevant key data type.

type Key a = [a]

So the key “abcd” used in the example above would have the type: Key Char

Now we can define the actual type that forms the prefix tree. A tree can simply be thought of as a node which may contain some data, along with a function which takes the next prefix and returns the tree below that point (if there is any further tree below that point).

data PFTree a b = Node (Maybe b) (a -> Maybe (PFTree a b))

With this definition we can now define an empty tree. That is, a tree with no data at the root node, and for which any prefix returns no sub tree.

initialTree :: PFTree a b
initialTree = Node Nothing (\_ -> Nothing)

So, we’ve now defined the tree data type, but we want to be able to define the lookup and insert functions. The lookup function is used to see whether a given key has any data associated with it, within the given prefix tree.

lookup :: Key a -> PFTree a b -> Maybe b

If we have got to the end of a key, then the data associated with the current node is the data we are looking up (even if it is Nothing).

lookup [] (Node b _) = b

If we haven’t reached the end of a key, then we need to see whether the relevant sub tree exists, and if it does, we need to lookup the rest of the key within the subtree.

lookup (x:xs) (Node b f) = case f x of
                           Nothing -> Nothing
                           Just pt -> lookup xs pt

The code for the insert function is also very similar. It is used to insert data associated to a given key, into a given prefix tree. However, we now need that the type of the keys fulfils the Eq typeclass, or in other words it defines the function (==) :: a -> a -> Bool that checks for equality between two members of the type.

insert :: Eq a => Key a -> b -> PFTree a b -> PFTree a b

If we have traversed the tree up to the end of the given key, then we have reached the node at which we wish to insert the given data. In this instance, we just swap the new data for whatever was previously in the tree at the current node.

insert [] b (Node _ f) = Node (Just b) f

If we haven’t reached the end of the key, then we are in one of two situations. Either the next prefix will evaluate to Nothing and we can just construct the subtree with the remaining key and an empty tree, or we have to insert the data recursively into the subtree with the remaining key. In either case, we construct the relevant function using the equality function.

insert (x:xs) b (Node mb f) = case f x of
                            Nothing -> Node mb (\x' -> if x' == x then Just (insert xs b initialTree) else f x')
                            Just pt -> Node mb (\x' -> if x' == x then Just (insert xs b pt) else f x')

Everything is now defined such that we could use the prefix trees. The insert function can be used along with the empty tree to construct arbitrary trees, and the lookup function can be used to extract data from them.

I’ll leave it as an exercise for someone to define the tree given as an example above.

Categories: FUN

GPS tracks on Snowdon

September 1, 2010 Leave a comment

The weekend just gone was the end of August bank holiday weekend (28th, 29th and 30th of August, 2010), so Karen and I decided to spend the time visiting Wales. More specifically, we decided to spend the long weekend in Llanberis, at the foot of Mount Snowdon. The journey there would be a bit of adventure on the train, having to take three trains to get from Beeston in Nottinghamshire, to Bangor in Gwynedd. The route took in the delights of a change in both Derby and Crewe. Once in Bangor, we were able to catch a bus to Llanberis, with a stop off on the way to visit Caernarfon Castle.

We stayed in a B&B style hotel (the Dol Peris hotel), which was conveniently located on the high street in Llanberis. We chose to stay in Llanberis as it is home to the Snowdon Mountain Railway, for which we had booked tickets up the mountain on the Sunday morning. Our plan was to take in the views at the summit, and then walk down the Miner’s track to Pen-y-Pass, from where we could get the Sherpa bus back around to Llanberis.

The rest of this blog post will mainly be about this day trip up and back down Snowdon, for which I took my trusty HTC Hero, and logged a GPS track of the trip. We both had an excellent weekend in Snowdonia, and would very much like to go back for more walking in the mountains. For now though, I have split the rest of this post into three sections, one for the train journey up the mountain, and one for the walk back down the Miner’s path. The final section documents the whole journey through screen shots of the GPS track displayed in Google Earth.

The Snowdon Mountain Railway

The Snowdon Mountain Railway was constructed in the late 19th Century, and was first used to take tourists to the top of Snowdon in 1896. The original complement of three steam engines has now been added to by diesel locomotives, and although SMR can’t guarantee which type of train will take you up the mountain, we were lucky enough to be taken by one of the original steam locomotives, “Wyddfa”, built in 1895. The trains are all fitted with a “pinion” which engages with the “rack” to provide traction. One thing to note is that the boilers on the steam engines are also inclined so that the firebox is always submerged in water.

Snowdon Mountain Railway "Wyddfa"

The railway is apparently the only public rack and pinion railway in use within the British isles. The track has a double rack mounted between the rails, which can be clearly seen on the photo below. Without the rack and pinion the trains wouldn’t be able to make there way over the gradients of up to 1 in 5.5 (which is approximately 18.2%) to reach the summit.

Snowdon Mountain Railway tracks

There are three passing points on the track up the mountain, where the trains ascending the mountain are able to safely pass those descending it. The steam locomotives also take the opportunity to refill with water at the half way passing point on the ascent of the mountain. The journey up the mountain took about 55 minutes, and covers a total of 4.675 miles. For people taking the return journey on the train, you get a 30 minute stop off at the top, which gives you plenty of time to walk the last 50 or so meters to the actual summit (where the triangulation point sits).

Snowdon SummitSnowdon Summit Triangulation Point

As you can see, the summit was rather covered in cloud when we got there, so our plans to take in the views were a little optimistic. However, we were able to have lunch in the new visitor centre, and prepare ourselves for the walk down. I’m pretty sure the massive Original Welsh “Oggie” that I ate was a bit excessive, but it was delicious none the less.

After an hour and a bit at the summit, hoping the clouds would clear, we decided that we should head off to find the top of the Miner’s track, and head back down the mountain.

The Miner’s Track

The Miner’s track is one of the main paths used by people ascending and descending Snowdon. Most of the information online seems to describe the ascent of the Miner’s track, so this description will differ in that it describes our descent. As mentioned previously, the top of Snowdon was completely covered in cloud when we were up there, and we would definitely recommend that you prepare yourself with plenty of warm clothes, and practical footwear if you are going to attempt this yourself.

From the very summit, you can head back down towards the visitor centre, and then start to follow the path alongside the railway. This part of the path can be very busy as all the paths on Snowdon converge into this one path as you reach the last ridge before the summit. To get to the Miner’s track you simply follow this main path until you reach the first finger stone, as pictured below.

Snowdon Finger Stone 1

At the finger stone, you take the path off to the right hand side. This path is the top of both the Miner’s track and the Pyg track, and is a steep zig-zag. For us, it was a welcome turn off the main path as this part of the path was protected from the strong winds that had been coming up from the other side of the mountain. The path is pretty easy to follow, not least because of all the other hikers. We were told that on a clear day you would be able to get a view over the lakes below, but the cloud was still reducing the visibility, and carried on to do so until we were a little lower. Eventually though, the clouds parted and we were able to see the lakes below.

Snowdon Lakes

After the big zig-zag of this path, you reach another finger stone (a little smaller than the first). This is where the Miner’s track and the Pyg track diverge from one another.

Snowdon Finger Stone 2

Again, you take the right hand path at this finger stone, as the left hand path is the Pyg track. The path from this point down to Glaslyn was often described as a steep scree scramble, but we didn’t find it too challenging, especially as the visibility had improved dramatically. The path seems well trodden, and there are stair like stones placed to help at the steepest parts.

Once you reach Glaslyn, you can carry on the path down the valley to Llyn Llydaw, but we took the time to walk a little around the lake, and look at some of the disused mining buildings that are scattered around. It is the path from here back to Pen-y-Pass for which it is named, as it is the route that the miners would have taken.

View of Snowdon from GlaslynMining Building by Glaslyn

The rest of the path down to Pen-y-Pass is very easy going as you will have already done most of the decent. The path takes in two more lakes, including an impressive causeway over Llyn Llydaw, and the smaller Llyn Teyrn.

View of Snowdon from Llyn Llydaw

Altogether, the walk took us just under 3 hours, from the summit to Pen-y-Pass (which is about 4 miles), but we were slowed by the poor visibility at the top. I don’t think an estimate of a little over 2 hours would be far out on a good day. We were glad that we hadn’t driven as the Pen-y-Pass car park is £10 for parking (for over 4 hours), and the Sherpa bus back to Llanberis was only £1.

GPS log of the trip

The three separate parts of our trip make up the three sides of the triangle that can be seen on the GPS track. That is the ascent from Llanberis to the summit on the Snowdon Mountain Railway, the descent to Pen-y-Pass on the Miner’s track, and finally the return to Llanberis on the Sherpa bus.

The most impressive view of the GPS track is of the part which forms the Miner’s track down from the summit via Glaslyn and Llyn Llydaw.

Miner's Track GPS log

Another view of the entire track, also gives a good view of the walk down to Pen-y-Pass.

GPS log view of Miner's Track

The view of the track that best shows the ascent up the Snowdon Mountain Railway also shows that the railway goes up the least steep ridge of Snowdon.

GPS log view of Snowdon Mountain Railway

The last view of the GPS log that I shall put here is from the side of the bus journey back from Pen-y-Pass to Llanberis.

GPS log view of Sherpa Bus Route

The final diagram below shows a graph of altitude by distance travelled. Somehow the scales have been turned into percentages, but these aren’t too hard to change back in to the actual values.

Altitude by Distance Travelled

The altitude corresponding to 0 Elevation is 512 feet, and is approximately the altitude of Llanberis (GPS altitude is the least accurate part of the fix), and the altitude corresponding to 100 Elevation is 3756 feet. The actual height of Snowdon is only 3560 feet (or 1085 meters), so this does give an idea of the lack in accuracy of the altitude readings taken from the GPS.

The distance travelled scale starts at the hotel in Llanberis. The journey up the Snowdon Mountain Railway is from about 5 to just over 30. The walk down the Miner’s track is from just over 30 to just under 60. The Sherpa bus back to Llanberis is from just under 60 to around 95.

Categories: GPS Logs