[Haskell-cafe] Non-deterministic (stochastic?) function/expression types in Haskell?

[Benjamin Redelings]

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