Hello, Benjamin. Nature of Haskell is to treat random values under monad. Because generator returns different values on calls with the same arguments. So, no way to "declare" such function as "nondeterministic" function. Haskell is not good language for such job. But there are more suitable languages for such kind of tasks. If you prefer Haskell-like syntax, better will be to use ML family language: modern F#, Ocaml or SML, where IO will not be involved - all is under IO explicitly. But there is another good choice: Mercury. It supports (sure, because it's declarative language and is based on Prolog) special notations for computations:

• non-deterministic
• deterministic
• semi-deterministic
• multisolution

(see more about these declarations here: https://www.mercurylang.org/information/doc-release/mercury_ref/Determinism-categories.html#Determinism-categories)

Hi Oleg,

Thanks for the links!  These are quite interesting.

1. Here is one situation that occurs in evolutionary biology where I would want to have the full range of Haskell syntax available to me.  Consider a binary tree, where each tree node has an integer name in [1..num_nodes tree].  The function (parent tree n) gives the parent of node n and (root tree) gives the root node.

-- the expected value for a node is the value at its parent
   mean node tree x | node == root tree   = 0
                    | otherwise           = x!!parent tree node

-- given a tree, simulate down the tree,
   simulate_on_tree tree  = let x = [sample $ normal (mean node tree x) 1 | node <- [1..num_nodes tree]]

My understanding is that you cannot refer to the result of a computation while performing a computation, as in:

    do {x <- simulate_on_tree tree x}

Am I missing something?


On 01/11/2018 12:02 PM, Oleg Grenrus wrote:

(a) Non-determism is an effect, e.g. simple list is non-determinism monad, for small discrete distributions!

2.  Why would we want to consider non-determinism (in the sense of returning an unpredictable value) as an effect?  Certainly running a non-deterministic function does not change global state like modifying an IORef would.  I'm also thinking of functions that are (somehow) TRULY random, so they are not keeping a hidden state around somewhere.  I'm calling them "non-deterministic" instead of "random" because I want to ignore (for the moment) the probability distribution, and just say that the result is arbitrary.

3. Sampling from a normal distribution gives ONE value, and the list of possible values is .... large :-)  [i.e. it would include all Double values.]

(b) Yes. We can write effectful code "implicitly"
   - You might look into *Automatically Escaping Monads*
   - https://www.youtube.com/watch?v=wG8AErq6Bbo, slides:
http://benl.ouroborus.net/talks/2016-HIW-Escape.pdf
   - http://disciple.ouroborus.net/ or https://github.com/DDCSF/ddc

4. Interesting - I like his approach to making the box / run instructions implicit.

Interstingly, while searching for the paper, I stumbled upon Oleg
Kiselyov's  (not me) paper from
*Effects Without Monads: Non-determinism*, which is a different approach.
Maybe that's what you are looking after
http://okmij.org/ftp/tagless-final/nondet-paper.pdf

5. In this paper, it seems that non-determinism means returning ALL possible outcomes.  However, what I meant is arbitrarily choosing ONE possible outcome.  My terminology is probably being imported from statistics - is there a different word I should use here?

-BenRI
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.