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

Benjamin Redelings benjamin.redelings at gmail.com
Fri Jan 12 16:26:42 UTC 2018

```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
```