-------------------------------------------------------------------------
-- Example for the use of set functions as described in the paper
-- Sergio Antoy, Michael Hanus:
-- Set Functions for Functional Logic Programming
-- Proc. 11th International ACM SIGPLAN Conference on Principles and Practice
-- of Declarative Programming (PPDP'09), pp. 73-82, 2009
{-# OPTIONS_FRONTEND -Wno-overlapping #-}
import Control.SetFunctions
-------------------------------------------------------------------------
-- Example: compute a flight itinerary between two cities
-- The cities:
data City = Portland | Frankfurt | Amsterdam | Hamburg
deriving (Eq,Ord)
-- The flight numbers:
data FlightNumber = LH469 | NWA92 | LH10 | KL1783
deriving (Eq,Ord)
(:.) :: Int -> Int -> (Int,Int)
x :. y = (x,y)
-- The flights and their durations:
flight :: (FlightNumber, City, City, (Int,Int))
flight = (LH469, Portland, Frankfurt, 10:.15)
flight = (NWA92, Portland, Amsterdam, 10:.00)
flight = (LH10, Frankfurt,Hamburg, 1:.00)
flight = (KL1783,Amsterdam,Hamburg, 1:.52)
-- We consider itineraries with at most one intermediate stop:
itinerary :: City -> City -> [FlightNumber]
itinerary orig dest
| flight =:= (num,orig,dest,len)
= [num]
where num, len free
itinerary orig dest
| flight =:= (num1,orig,x,len1)
& flight =:= (num2,x,dest,len2)
= [num1,num2]
where num1, len1, num2, len2, x free
duration :: [FlightNumber] -> Int
duration = foldr (+) 0 . map flightToMinutes
flightToMinutes :: FlightNumber -> Int
flightToMinutes fnum | flight =:= (fnum,unknown,unknown,h:.m)
= h*60+m
where h,m free
-- Returns an itinerary with a shortest flight time.
-- Purely declarative specification: an itinerary is the shortest if there is
-- no shorter itinerary.
shortestItin :: City -> City -> [FlightNumber]
shortestItin s e
| isEmpty (set1 shorterItinThan (duration it))
= it
where
it = itinerary s e
shorterItinThan itduration | duration its < itduration = its
where its = itinerary s e
goal1 :: [FlightNumber]
goal1 = shortestItin Portland Hamburg --> [LH469,LH10]
-- Returns an itinerary with a shortest flight time.
-- Implemented by selecting the shortest path from all pathes.
shortestItinSelect :: City -> City -> [FlightNumber]
shortestItinSelect s e =
minValueBy shorter (set2 itinerary s e)
where
shorter it1 it2 = compare (duration it1) (duration it2)
goal2 :: [FlightNumber]
goal2 = shortestItinSelect Portland Hamburg --> [LH469,LH10]
main :: [FlightNumber]
main = goal1