sorry, forgot to cc cafe. On Fri, Jan 21, 2011 at 7:12 PM, Sebastian Fischer wrote:

Hi Daryoush,

On Fri, Jan 21, 2011 at 6:18 AM, Daryoush Mehrtash wrote:

...

I am having hard time understanding the following paragraph in "Purely functional Lazy non-deterministic programing" paper http://www.cs.rutgers.edu/~ccshan/rational/lazy-nondet.pdf

The problem with the naive monadic encoding of non-determinism is that the arguments to a constructor must be deterministic. If these arguments are themselves results of non-deterministic computations, these computations must be performed completely before we can apply the constructor to build a non-deterministic result.

Why does the argument to constructors must be deterministic?

Because of the type of the constructor. Say you want to compute a list of Ints nondeterministically (like in the paper). Than the first argument of the (:) constructurs in the result must be an Int. A nondeterministic computation that yields an Int has type (m Int) for some nondeterminism monad (for example, it has type [Int] in the list monad). That the (:) constructur is polymorphic and would allow to make a value of type [m Int], is a coincidence and does not help to make a value of type (m [Int]).

...

WHy is it that thunks are not used in this case?

Thunks do not model nondeterminism, only laziness.

Did that help you understand?

Regards, Sebastian