--import inc_search

-- Problem taken from Horowitz/Sahni: Fundamentals of Computer Algorithms,
-- 1978, p. 187

data City = Boston | Chicago | NewYork | Miami | NewOrleans | Denver
          | SanFrancisco | LosAngeles

-- We solve this problem by the Incremental Solution pattern.

distance :: City -> City -> Int
distance eval flex
--distance Boston LosAngeles = 15000 --
distance Boston Chicago = 1500
distance Boston NewYork = 250
--distance NewYork Boston = 250 -- cycle...
distance NewYork Chicago = 1000
distance NewYork Miami = 900
distance NewYork NewOrleans = 1400
distance Miami NewOrleans = 1000
distance Chicago Denver = 1200
distance NewOrleans LosAngeles = 1700
distance Denver LosAngeles = 1000
distance Denver SanFrancisco = 800
distance SanFrancisco LosAngeles = 300

-- A partial solution is a list of cities visited so far together with
-- the corresponding total distance:
data DPath = DPath Int [City]

-- A partial solution is extended by adding a new city reachable from
-- the current city:
extendPath :: DPath -> DPath
extendPath (DPath d (c:cs)) | distance c c1 =:= d1 = DPath (d+d1) (c1:c:cs)
   where c1,d1 free

startAtBoston = DPath 0 [Boston]

reachedLosAngeles (DPath _ (c:_)) = c == LosAngeles

isShorter (DPath d1 _) (DPath d2 _) = d1<d2


-- non-deterministic search:
main1 = searchNonDet     extendPath startAtBoston reachedLosAngeles

-- depth-first search:
main2 = searchDepthFirst extendPath startAtBoston reachedLosAngeles

-- depth-first search with equivalence checking:
main3 = searchDepthFirstNoEquiv extendPath startAtBoston reachedLosAngeles
                                (\(DPath _ (c1:_)) (DPath _ (c2:_)) -> c1==c2)

-- breadth-first search:
main2a = searchBreadthFirst extendPath startAtBoston reachedLosAngeles

-- best-first search:
main4 = searchBestFirst  extendPath startAtBoston reachedLosAngeles isShorter
main4a = searchBestFirst  extendPath startAtBoston reachedLosAngeles
         (\_ _->True)

-- best first search with equivalence checking:
main5 = searchBestFirstNoEquiv extendPath startAtBoston reachedLosAngeles
                               isShorter
                               (\(DPath _ (c1:_)) (DPath _ (c2:_)) -> c1==c2)