3

Given a set [1,2,3] the power set is unique. Why do we say it's non deterministic? Consider another example

[1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)  

Why is this function non-deterministic?

If I consider \ch -> return (n,ch) as the second function where is the first?

And if the first function is

\n -> ['a','b'] >>= \ch -> return (n,ch)  

Why is it evaluation from right to left.

Shouldn't it be \n -> (function)?

And what function is this (['a','b'] >>= \ch -> return (n,ch))?

If it's left to right It can't evaluate the second \ch function without using the first part ['a','b'] which doesn't have to do anything with 'n' parameter.

2
  • List are not sets, I suspect that's the cause of confusion here. Powerset as such is perfectly deterministic, and list operations are deterministic too, but since there's no 1:1 correspondence between lists and sets represented by them, a "powerset" implementation by lists isn't quite well-specified. Jan 21, 2015 at 12:02
  • 9
    Who says it's non-deterministic? I ask because either they are wrong or you have misunderstood their intention. We commonly say the list monad allows us to model non-determinism – that doesn't mean the result of our computations are non-deterministic all the time – quite the opposite. Lists allow us to model non-determinism deterministically. By representing a single value with a list of possible values, and treating it as sort of a single value, we can pretend we are working with single values when in fact we are working with all possible combinations of values.
    – kqr
    Jan 21, 2015 at 12:19

1 Answer 1

12

The reason why the term non-determinism is sometimes used when talking about the list monad is because of denotational semantics. When giving semantics to non-deterministic languages it is common to use the power domain. This domain can be approximated in Haskell using lists. Since the use of monads in Haskell comes from their use in denotational semantics, some of the terms used in that field have been carried over even though they may or may not make sense in their new context.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.