Learn You a Haskell for Great Good! - Miran Lipovaca [96]
optimalPath :: RoadSystem -> Path
optimalPath roadSystem =
let (bestAPath, bestBPath) = foldl roadStep ([], []) roadSystem
in if sum (map snd bestAPath) <= sum (map snd bestBPath)
then reverse bestAPath
else reverse bestBPath
We left fold over roadSystem (remember that it’s a list of sections) with the starting accumulator being a pair of empty paths. The result of that fold is a pair of paths, so we pattern match on the pair to get the paths themselves. Then we check which one of these was quicker and return it. Before returning it, we also reverse it, because the optimal paths so far were reversed due to us choosing prepending over appending.
Let’s test this!
ghci> optimalPath heathrowToLondon
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]
This is the result that we were supposed to get! It differs from our expected result a bit, because there’s a step (C,0) at the end, which means that we cross over to the other road once we’re in London. But because that crossing doesn’t take any time, this is still the correct result.
Getting a Road System from the Input
We have the function that finds an optimal path, so now we just need to read a textual representation of a road system from the standard input, convert it into a type of RoadSystem, run that through our optimalPath function, and print the resulting path.
First, let’s make a function that takes a list and splits it into groups of the same size. We’ll call it groupsOf:
groupsOf :: Int -> [a] -> [[a]]
groupsOf 0 _ = undefined
groupsOf _ [] = []
groupsOf n xs = take n xs : groupsOf n (drop n xs)
For a parameter of [1..10], groupsOf 3 should result in the following:
[[1,2,3],[4,5,6],[7,8,9],[10]]
As you can see, it’s a standard recursive function. Doing groupsOf 3 [1..10] equals the following:
[1,2,3] : groupsOf 3 [4,5,6,7,8,9,10]
When the recursion is done, we get our list in groups of three. And here’s our main function, which reads from the standard input, makes a RoadSystem out of it, and prints out the shortest path:
import Data.List
main = do
contents <- getContents
let threes = groupsOf 3 (map read $ lines contents)
roadSystem = map (\[a,b,c] -> Section a b c) threes
path = optimalPath roadSystem
pathString = concat $ map (show . fst) path
pathTime = sum $ map snd path
putStrLn $ "The best path to take is: " ++ pathString
putStrLn $ "Time taken: " ++ show pathTime
First, we get all the contents from the standard input. Then we apply lines to our contents to convert something like "50\n10\n30\n ... to something cleaner, like ["50","10","30" .... We then map read over that to convert it to a list of numbers. We apply groupsOf 3 to it so that we turn it to a list of lists of length 3. We map the lambda (\[a,b,c] -> Section a b c) over that list of lists.
As you can see, the lambda just takes a list of length 3 and turns it into a section. So roadSystem is now our system of roads, and it even has the correct type: RoadSystem (or [Section]). We apply optimalPath to that, get the path and the total time in a nice textual representation, and print it out.
We save the following text in a file called paths.txt:
50
10
30
5
90
20
40
2
25
10
8
0
Then we feed it to our program like so:
$ runhaskell heathrow.hs < paths.txt
The best path to take is: BCACBBC
Time taken: 75
Works like a charm!
You can use your knowledge of the Data.Random module to generate a much longer system of roads, which you can then feed to the code we just wrote. If you get stack overflows, you can change foldl to foldl' and sum to foldl' (+) 0. Alternatively, try compiling it like this before running it:
$ ghc --make -O heathrow.hs
Including the O flag turns on optimizations that help prevent functions