Good suggestions Daniel. If anybody else here is interested in functional logic I've added the needed Applicative and Alternative instances to Dan Doel's logict package which implements Oleg's LogicT paper and will post them on github.com/jimstutt. Wren Romano posted a list of useful links:
* http://web.cecs.pdx.edu/~mpj/thih/
* http://web.cecs.pdx.edu/~sheard/papers/generic.ps
* http://www.cs.chalmers.se/~emax/wired/documents/LP_HFL07.pdf
* http://okmij.org/ftp/papers/LogicT.pdf
* http://citeseer.ist.psu.edu/318776.html
* http://citeseer.ist.psu.edu/claessen00typed.html
* http://www.curry-language.org/

I also fixed the code in the code in the blog post Wren commented on:

http://propella.blogspot.co.uk/2009/04/prolog-in-haskell.html.