[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
More information about the Haskell-Cafe
mailing list