Non-determinism, backtracking and Monads
Derek Elkins
ddarius@hotpop.com
Wed, 11 Jun 2003 14:04:35 -0400
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).