Non-determinism, backtracking and Monads

[Derek Elkins]

On Wed, 11 Jun 2003 09:03:32 +0100
"Simon Peyton-Jones" <simonpj@microsoft.com> wrote:

> Check out "Embedding Prolog in Haskell", which explores exactly the
> topic you discuss.
> 
> 	http://citeseer.nj.nec.com/272378.html
> 
> Simon

and what can be considered a followup to that paper,

http://citeseer.nj.nec.com/claessen00typed.html

-- solve (do (x,y) <- free; append x y (s2l "abc"); 
--           liftM2 (,) (list atom x) (list atom y)) ==>
--
([],["a","b","c"]),(["a"],["b","c"]),(["a","b"],["c"]),(["a","b","c"],[
])

append :: (Unify s a, Free s a) => List s a -> List s a -> List s a ->
LP s () 
append ps qs rs = (do
    ps =:= Nil
    qs =:= rs)
  `mplus` (do
    (x,xs,ys) <- free
    ps =:= (x ::: xs)
    rs =:= (x ::: ys)
    append xs qs ys)

-- append([],L,L).
-- append([H|T],L,[H|Rest]) :- append(T,L,Rest).

powerset' xs ys = free >>= \(h,t,rest) -> p2h [
    [xs =:= Nil, ys =:= Nil],
    [xs =:= (h ::: t), powerset' t ys],
    [xs =:= (h ::: t), ys =:= (h ::: rest), powerset' t rest]]

-- powerset([],[]).
-- powerset([X|Xs],Rest) :- powerset(Xs,Rest)
-- powerset([X|Xs],[X|Rest]) :- powerset(Xs,Rest).