Learn You a Haskell for Great Good! - Miran Lipovaca [95]
When doing the solution by hand, there was a step that we repeated over and over. It involved checking the optimal paths on A and B so far and the current section to produce the new optimal paths on A and B. For instance, at the beginning, the optimal paths were [] and [] for A and B, respectively. We examined the section Section 50 10 30 and concluded that the new optimal path to A1 was [(B,10),(C,30)] and the optimal path to B1 was [(B,10)]. If you look at this step as a function, it takes a pair of paths and a section and produces a new pair of paths. So its type is this:
roadStep :: (Path, Path) -> Section -> (Path, Path)
Let’s implement this function, because it’s bound to be useful:
roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (pathA, pathB) (Section a b c) =
let timeA = sum (map snd pathA)
timeB = sum (map snd pathB)
forwardTimeToA = timeA + a
crossTimeToA = timeB + b + c
forwardTimeToB = timeB + b
crossTimeToB = timeA + a + c
newPathToA = if forwardTimeToA <= crossTimeToA
then (A, a):pathA
else (C, c):(B, b):pathB
newPathToB = if forwardTimeToB <= crossTimeToB
then (B, b):pathB
else (C, c):(A, a):pathA
in (newPathToA, newPathToB)
What’s going on here? First, we calculate the optimal time on road A based on the best so far on A, and we do the same for B. We do sum (map snd pathA), so if pathA is something like [(A,100),(C,20)], timeA becomes 120.
forwardTimeToA is the time that it would take to get to the next crossroads on A if we went there directly from the previous crossroads on A. It equals the best time to our previous A plus the duration of the A part of the current section.
crossTimeToA is the time that it would take if we went to the next A by going forward from the previous B and then crossing over. It’s the best time to the previous B so far plus the B duration of the section plus the C duration of the section.
We determine forwardTimeToB and crossTimeToB in the same manner.
Now that we know the best way to A and B, we just need to make the new paths to A and B based on that. If it’s quicker to go to A by just going forward, we set newPathToA to be (A, a):pathA. Basically, we prepend the Label A and the section duration a to the optimal path on A so far. We say that the best path to the next A crossroads is the path to the previous A crossroads and then one section forward via A. Remember that A is just a label, whereas a has a type of Int.
Why do we prepend instead of doing pathA ++ [(A, a)]? Well, adding an element to the beginning of a list is much faster than adding it to the end. This means that the path will be the wrong way around once we fold over a list with this function, but it’s easy to reverse the list later.
If it’s quicker to get to the next A crossroads by going forward from road B and then crossing over, newPathToA is the old path to B that then goes forward and crosses to A. We do the same thing for newPathToB, except that everything is mirrored.
Finally, we return newPathToA and newPathToB in a pair.
Let’s run this function on the first section of heathrowToLondon. Because it’s the first section, the best paths on A and B parameter will be a pair of empty lists.
ghci> roadStep ([], []) (head heathrowToLondon)
([(C,30),(B,10)],[(B,10)])
Remember that the paths are reversed, so read them from right to left. From this, we can read that the best path to the next A is to start on B and then cross over to A. The best path to the next B is to just go directly forward from the starting point at B.
Note
When we do timeA = sum (map snd pathA), we’re calculating the time from the path on every step. We wouldn’t need to do that if we implemented roadStep to take and return the best times on A and B, along with the paths themselves.
Now that we have a function that takes a pair of paths and a section, and produces a new optimal path, we can easily do a left fold over a list of sections.