May I suggest a third route that has the advantages of both your approaches. The backside is of course that it takes a bit of work. My suggestion is to do an effect analysis of your curry programs to identify the purely functional parts and compile them directly to pure Haskell. The rest of the programs can run in a monad. This approach should be more robust than relying on unsafePerformIO. It is also very much in the spirit of your slogan.
Thank you for the suggestion. We were thinking along the lines of identifying "the purely functional parts and compile them directly to pure Haskell" as a possibility of optimization (with some code duplication). But if the "rest of the programs can run in a monad" the question is: How much of the example program I submitted would you classify as "purely functional"? Actually, most of it is purely functional apart from the (?) - operator. But I do not see a way to make use of this. If, however, the whole program is classified as "non-functional" then this is definitely not in the spirit of the slogan. One effect we like very much about our implementation is that all expressions which do not depend on non-deterministic values are shared across the whole search. Note, that this dependence is a dynamic property. If the code of programs like the example was monadic, I do not see how not to loose this property. Thanks again! Bernd