0

There is much said about 'nondeterminism' in Haskell: The list monad and the Amb monad call themselves nondeterministic.

But these functions just model nondeterminism - they (deterministically) generate all possible outcomes.

How would one write a truly nondeterministic choice in Haskell?

By this I mean a function of type

nondeterministicChoice :: a -> a -> IO a

where the compiler is unconstrained in whether to return the first or second argument (using the same logic it uses, for example, to choose whether to recalculate or memoize a thunk). Especially interesting would be if the resulting a could be lazy.

Ari Fordsham
  • 2,437
  • 7
  • 28
  • 1
    Same way you handle e.g. random number generation. Presumably there is something like /dev/random or an equivalent on your OS. You are in the IO monad so you can read it and proceed from there. – n. m. could be an AI Aug 05 '21 at 09:31
  • Even if the compiler is unconstrained, at run time this `nondeterministicChoice`, if it exists, would always make the same choice, unless you would involve some kind of random number generation as @n.1.8e9-where's-my-sharem. suggests. – Noughtmare Aug 05 '21 at 09:54
  • I'm not looking to make a *random* choice - I want to free the compiler to make a choice, i.e. if one is memoized and one is not. I guess the point is moot if the compiler has no logic to take advantage of this, unless it can reuse something from pure evaluation. It's okay if it's the same result from one run of the binary to he next. – Ari Fordsham Aug 05 '21 at 10:16
  • 2
    The main non-determinism is lazy evaluation: the compiler doesn't guarantee in which sequence thunks are reduced; different releases might reduce the same program in different sequences. That isn't observable from within the program, but you can see it in memory footprint or garbage collection. – AntC Aug 05 '21 at 10:18
  • 'That isn't observable from within the program' - you *can* observe this - https://stackoverflow.com/questions/28687384/test-if-a-value-has-been-evaluated-to-weak-head-normal-form?noredirect=1&lq=1 – Ari Fordsham Aug 05 '21 at 10:28
  • If you want a race you can use [`amb`](https://hackage.haskell.org/package/unamb-0.2.5/docs/Data-Unamb.html#v:amb). It evaluates both arguments in parallel and yields the first to complete. Of course this will often be *more* expensive in total CPU time than evaluating either one of them alone, but elapsed time should be less on average, if that's what you care about. – amalloy Aug 05 '21 at 10:32
  • @amalloy good find! That's the `amb` function from the `Unamb` package, not the `Amb` monad. – Ari Fordsham Aug 05 '21 at 10:34
  • 1
    "I want to free the compiler to make a choice". "The compiler" only interprets programs. It doesn't make choices of its own. Everything the program does is encoded in the program itself. If you want *the program* to make a choice, you need to code it up. A program that e.g. always makes the first choice is as good as any. So is a program that makes a random choice assisted by some external RNG. So is a program that looks inside its own run-time data and selects a thunk that for some arbitrary reason it likes more than the other. – n. m. could be an AI Aug 05 '21 at 11:06
  • The compiler chooses i.e. whether to read a memoized thunk or reevaluate. Much else of what you said is similar to my answer - feel free to edit if you think something needs clarifying. – Ari Fordsham Aug 05 '21 at 11:09
  • "The compiler chooses". It is not true, the compiler has no free will, it does what it was programmed to do. "The compiler chooses" seems to be an inaccurate way of saying "I cannot predict what it does". It is irrelevant anyway. "The compiler" when used this way is just an external source of pseudorandom events for your program, just like /dev/random. – n. m. could be an AI Aug 05 '21 at 11:20
  • You might be interested in a library by Edward Kmett [*speculative*](https://hackage.haskell.org/package/speculation) that provides speculative execution in parallel – Iceland_jack Aug 05 '21 at 12:02
  • Have you seen the probability monad? https://hackage.haskell.org/package/probability-0.2.7/docs/Numeric-Probability-Distribution.html That may be what you are looking for. – Paul Johnson Aug 06 '21 at 19:43

1 Answers1

1

I think the answer is - the question as asked is pointless. There's no point simply freeing the compiler do things like this, because it doesn't know what to do with it. There is (currently) no logic in the compiler that will decide which of the arguments is better to use.

However, you could code up this function to, i.e. choose an argument that has already been evaluated, using the evaluated function from https://stackoverflow.com/a/28701687/12153248:

nondeterministicChoice :: a -> a -> IO a
nondeterministicChoice a b = do
  a' <-evaluated a
  if a'
    then return a
    else return b
Ari Fordsham
  • 2,437
  • 7
  • 28