[Haskell-cafe] How to implement `amb' operator?

Brandon Michael Moore brandon at its.caltech.edu
Wed Apr 7 07:04:49 EDT 2004

Keith is talking about a "comitted choice" style of nondeterminism, where
one of the arguments is picked and the computation continues from there.

If you want a computation with backtracking, or a list of all possibly
results then you should use the list monad, or another monad that supports

The tutorial "All About Monads" has a nice discussion of the list monad in
section two, another example ("StateT with List") in section three, and
it's a good introduction to monads overall, if you need one.

If you wanted to pick x from 1 2 3 and y from 3 4 5 so that x squared
equals y you could write

results :: [(Int,Int)]
results = do x <- [1,2,3]
             y <- [3,4,5]
             guard $ x^2 == y
             return (x,y)

then results will be [(2,4)].


On Wed, 7 Apr 2004, Keith Wansbrough wrote:

> > Hi,
> >   I think it's good idea to compute non-deterministic problems with the `amb'
> > operator, just as in LISP/scheme. But how to implement it in haskell?
> Do you mean "evaluate e1 and e2, and return the result of whichever
> returns first"?
> Probably best to do this using threads.
> --KW 8-)
> --
> Keith Wansbrough <kw217 at cl.cam.ac.uk>
> http://www.cl.cam.ac.uk/users/kw217/
> University of Cambridge Computer Laboratory.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list