-- Simulation of the Prolog shell with different search strategies:
-- print a list of solved goals:
printloop [] = putStrLn "no"
printloop (a:as) = browse a >>
putStr " ? " >>
getLine >>=
evalAnswer as
where
evalAnswer as ln =
if ln==";"
then putChar '\n' >> printloop as
else if ln==""
then putChar '\n' >> putStrLn "yes"
else putStrLn "(\";\" for more choices, otherwise ): " >>
getLine >>= evalAnswer as
-- Standard Prolog with depth-first search:
prolog g = printloop (solveAll g)
-- Prolog with breadth-first search:
prolog_bfs g = printloop (bfs g)
-- Prolog with depth-bounded search:
prolog_depth n g = printloop (allbounded n g)
-- Prolog with iterative deepening search:
prolog_id n g = printloop (all_id n g)
append [] ys = ys
append (x:xs) ys = x : append xs ys
goal = prolog \(l1,l2) -> append l1 l2 =:= [0,1]
-- breadth-first search:
bfs g = trygoals [g]
where
trygoals [] = []
trygoals (g:gs) = splitgoals (map try (g:gs)) []
splitgoals [] ugs = trygoals ugs
splitgoals ([]:gs) ugs = splitgoals gs ugs
splitgoals ([g]:gs) ugs = g:(splitgoals gs ugs)
splitgoals ((g1:g2:g3s):gs) ugs = splitgoals gs (ugs++g1:g2:g3s)
-- depth-first search with depth bound:
allbounded n g = if n>0 then evalall (try g) else []
where
evalall [] = []
evalall [g] = [g]
evalall (g1:g2:gs) = concat (map (allbounded (n-1)) (g1:g2:gs))
-- iterative deepening search:
all_id n g = depthLoop n n (toDepthN n n g) False
where
depthLoop n m [] True = depthLoop (n+m) m
(toDepthN (n+m) m g) False
depthLoop _ _ [] False = []
depthLoop n m ([]:gs) recomp = depthLoop n m gs recomp
depthLoop n m ([g1]:gs) recomp = g1:(depthLoop n m gs recomp)
depthLoop n m ((_:_:_):gs) _ = depthLoop n m gs True
toDepthN n m g = collect (try g)
where
collect [] = [[]]
collect [g] = if n>m then [[]]
else [[g]]
collect(g1:g2:gs) = if n==1
then [g1:g2:gs]
else concat (map (toDepthN (n-1) m) (g1:g2:gs))
-- Examples:
p (_:xs) = p xs
p [] = success
g1 = prolog \x -> p x
g2 = prolog_bfs \x -> p x
g3 = prolog_depth 10 \x -> p x
g4 = prolog_id 5 \x -> p x