• Choose a category
• All
• Classic-Fiction

In summary, to get the best path from Heathrow to London, we do this:

We see what the best path to the next crossroads on main road A is. The two options are going directly forward or starting at the opposite road, going forward and then crossing over. We remember the cost and the path.

We use the same method to find the best path to the next crossroads on main road B and remember that.

We see if the path to the next crossroads on A takes less time if we go from the previous A crossroads or if we go from the previous B crossroads and then cross over. We remember the quicker path. We do the same for the crossroads opposite of it.

We do this for every section until we reach the end.

Once we’ve reached the end, the quicker of the two paths that we have is our optimal path.

So, in essence, we keep one quickest path on the A road and one quickest path on the B road. When we reach the end, the quicker of those two is our path.

We now know how to figure out the quickest path by hand. If you had enough time, paper, and pencils, you could figure out the quickest path through a road system with any number of sections.

Representing the Road System in Haskell

How do we represent this road system with Haskell’s data types?

Thinking back to our solution by hand, we checked the durations of three road parts at once: the road part on the A road, its opposite part on the B road, and part C, which touches those two parts and connects them. When we were looking for the quickest path to A1 and B1, we dealt with the durations of only the first three parts, which were 50, 10, and 30. We’ll call that one section. So the road system that we use for this example can be easily represented as four sections:

50, 10, 30

5, 90, 20

40, 2, 25

10, 8, 0

It’s always good to keep our data types as simple as possible (although not any simpler!). Here’s the data type for our road system:

data Section = Section { getA :: Int, getB :: Int, getC :: Int }

deriving (Show)

type RoadSystem = [Section]

This is as simple as it gets, and I have a feeling it will work perfectly for implementing our solution.

Section is a simple algebraic data type that holds three integers for the durations of its three road parts. We introduce a type synonym as well, saying that RoadSystem is a list of sections.

Note

We could also use a triple of (Int, Int, Int) to represent a road section. Using tuples instead of making your own algebraic data types is good for some small, localized stuff, but it’s usually better to make a new type for more complex representations. It gives the type system more information about what’s what. We can use (Int, Int, Int) to represent a road section or a vector in 3D space, and we can operate on those two, but that allows us to mix them up. If we use Section and Vector data types, then we can’t accidentally add a vector to a section of a road system.

Our road system from Heathrow to London can now be represented like this:

heathrowToLondon :: RoadSystem

heathrowToLondon = [ Section 50 10 30

, Section 5 90 20

, Section 40 2 25

, Section 10 8 0

]

All we need to do now is implement the solution in Haskell.

Writing the Optimal Path Function

What should the type declaration for a function that calculates the quickest path for any given road system be? It should take a road system as a parameter and return a path. We’ll represent a path as a list as well.

Let’s introduce a Label type that’s just an enumeration of A, B, or C. We’ll also make a type synonym called Path.

data Label = A | B | C deriving (Show)

type Path = [(Label, Int)]

Our function, which we’ll call optimalPath, should have the following type:

optimalPath :: RoadSystem -> Path

If called with the road system heathrowToLondon, it should return the following path:

[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8)]

We’re going to need to walk over the list with the sections from left to right and keep the optimal path on A and optimal