GIML: Catching Buses
Diversion: Where to change on the buses
We can represent a "bus route" by a pair, the "service number" and the "route list" which gives the places served by that bus route. Taking the number 4 bus as an example:
<![CDATA[val routeList4 = ["Princes Street", "Haymarket",
"Craiglockhart"];
val busRoute4 = (4,routeList4);
]]>We can represent some of Edinburgh's buses using the list stops, a more complete list may be found in /home/student/general/ml/buses :
<![CDATA[val stops = [busRoute4,
(10,["Princes Street","Tollcross","Craiglockhart"]),
(23,["Trinity","Tollcross","Morningside"])];
]]>Using this data we can construct the function numbersFrom, which gives a list of buses servicing a given location and placesTo giving a list of places served by a given bus.
Constructing numbersFrom:
We note that an expression such as (member "Haymarket") is a function which might be applied to a "route list" giving true if Haymarket is in the list.
<![CDATA[member "Haymarket" routeList4
]]>This evaluates to true. We can use a partially evaluated member function as the condition of a filter thus obtaining a list of "bus routes" required. As the available list is a list of "bus routes" rather than "route lists" we must apply snd before applying the condition
<![CDATA[filter ((member "Tollcross")o snd) stops
]]>Gives us just those members of stops for which Tollcross is in the route list. We wish to extract the "service number" from each of these. Hence
<![CDATA[fun numbersFrom p = map fst (filter ((member p)o snd) stops);
]]>Constructing placesTo:
We wish to filter only those "bus routes" with a matching number. To look for the 10:
<![CDATA[filter ((fn x=>x=10) o fst)stops
]]>We can now extract the second component giving a list of lists which we flatten:
<![CDATA[fun placesTo n = flatten(map snd (filter((fn x=>x=n)o fst)
stops))
]]>Do it yourself
Construct functions which tell you which buses can get you from A to B without changing, or with one change. Prove or disprove the "Two bus conjecture" which states that you can get from anywhere to anywhere on two buses.
More bus data available here.