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

PY aquagnu at gmail.com
Mon Jan 15 08:08:20 UTC 2018

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 

  * non-deterministic
  * deterministic
  * semi-deterministic
  * multisolution

(see more about these declarations here: 

Also it has type system close to Haskell: with type-families, 
existential types, abstract types and so on, also it supports functional 
programming totally...

But, I'm sure, no problem to develop some DSL for Haskell which will 
hide some details ;)

Best regards, Paul

12.01.2018 18:26, 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
> _______________________________________________
> 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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180115/a68a7dbb/attachment.html>

More information about the Haskell-Cafe mailing list