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: 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 : 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. 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 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 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: filter ((fn x=>x=10) o fst)stops We can now extract the second component giving a list of lists which we flatten: 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.