[Haskell-cafe] Are constructors strict?
jac at informatik.uni-kiel.de
Fri Jan 21 09:06:39 CET 2011
On 20.01.2011, at 22:18, 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? WHy
> is it that thunks are not used in this case?
If you use a monadic model for non-determinism in Haskell you use the
standard constructors provided by Haskell and the bind operator to
apply it to a non-deterministic (monadic) value. For example, consider
the non-deterministic value coin defined as follows.
coin :: MonadPlus m => m Bool
coin = False `mplus` True
To apply the constructor Just to this value you use the bind operator
test :: MonadPlus m => m (Maybe Bool)
test = coin >>= return . Just
If you now consider the following definition.
loop = MonadPlus m => m Bool
loop = loop
If we apply Just to loop as follows
test2 :: MonadPlus m => m (Maybe Bool)
test2 = loop >>= return . Just
the evaluation of test2 does not terminate because >>= has to evaluate
loop. But this does not correctly reflect the behaviour in a
functional logic language like Curry. For example, if you have a
function that checks whether the outermost constructor of test2 is
Just, the test is supposed to be successful. In the naive model for
non-determinism this is not the case.
More information about the Haskell-Cafe