Switch to random

[lehins]

Based on top of #68, so it might make sense to merge that one first to reduce the diff

This PR removes usage of random-source completely in favor of new random interface.

There are some rough edges, but I wanted to at least take care of the hardest part of it.

Running the benchmarks showed a factor x2 improvement for some and loss of performance by approximately the same factor for some of the others. I did not dive into details much, but it will be good to investigate those in a little more detail. I suspect we can get performance improvements all across a board with some more work.

Overall however, IMHO, this whole change was not as hard as I expected it would be and new random interface just fell right in place.

[idontgetoutmuch]

This https://github.com/haskell-numerics/random-fu#usage needs to be changed to clarify that you will need this instance

instance (s ~ PrimState m, PrimMonad m) => StatefulGen (MWC.Gen s) m where

Do you concur? I can create a PR for this.

[idontgetoutmuch]

One more thought: I was disappointed that this change didn't improve performance. MWC has its own distributions and I thought I had benchmarked these against random-fu and found MWC better. I will perform this experiment again and report back.

[idontgetoutmuch]

Running the benchmarks showed a factor x2 improvement for some and loss of performance by approximately the same factor for some of the others.

I just re-read this so probably my performance comparison was at fault - I will try again.

[lehins]

One more thought: I was disappointed that this change didn't improve performance. MWC has its own distributions and I thought I had benchmarked these against random-fu and found MWC better. I will perform this experiment again and report back.

I suspect that ghc is failing to inline something and adding manual pragmas could improve the performance.

There was a lot of benchmarks, and I thought you have more experience with specific parts of the code that are being benchmarked to know what could be at fault.

My goal for this PR was essentially to make it work and optimize later.

... needs to be changed to clarify that you will need this instance... Do you concur?

It does need the instance, but if mwc-random-0.15 is being used it will be available automatically. So maybe just mentioning the minimum version is sufficient.

[lehins]

Nothing to do with this PR but I don't understand the usage of the Prompt monad which seems something like a free monad - I thought free monads existed so you could interpret things in a variety of ways. And by the way monadprompt does not have a github repo. One for the future.

PromptT and MonadPrompt are quite interesting. I have a general idea on how they work, but not nearly enough to explain any sort of theory behind it or how it relates to the concept of free monads.

[int-e]

My take on MonadPrompt is: The prompt monad is a free monad but with a more convenient programming interface in the context of designing EDSLs. It also predates free monads as far as the Haskell community is concerned. See comparison of prompt and free monads for details.

[lehins]

Oh yeah. Prompt is almost the same as a Church encoded free monad F:

newtype Prompt p r = Prompt {
    runP :: forall b . (r -> b) -> (forall a . p a -> (a -> b) -> b) -> b
}

vs

newtype F f a = F { runF :: forall r. (a -> r) -> (f r -> r) -> r }

[int-e]

Oh yeah. Prompt is almost the same as a Church encoded free monad F: [...]

Note that Ryan Ingram's original formulation was a tree:

data Prompt (p :: * -> *) :: (* -> *) where
    PromptDone :: result -> Prompt p result
    -- a is the type needed to continue the computation
    Prompt :: p a -> (a -> Prompt p result) -> Prompt p result

The CPS (or codensity) transformation was done later to cure the quadratic slowdown with left-associative (I think) uses of bind. Of course it also made the type harder to understand.

[idontgetoutmuch]

I am seeing only performance gains so far

[idontgetoutmuch]

I'll produce charts for all the benchmarks in the next few days.

[idontgetoutmuch]

[lehins]

Hell yeah! :100: