Think about generation of functions

[edsko]

Some references:

• https://www.reddit.com/r/haskell/comments/646k3d/comment/dg1485c
• https://hackage.haskell.org/package/QuickCheck-2.14.2/docs/Test-QuickCheck.html#g:15
• https://hackage.haskell.org/package/QuickCheck-2.14.2/docs/Test-QuickCheck-Gen-Unsafe.html#v:promote
• https://dl.acm.org/doi/10.1145/2364506.2364516
• Corresponding presentation: https://www.youtube.com/watch?v=CH8UQJiv9Q4 . Quote (around 6:00): "Many people think that when you quantify over a function -- when you generate some kind of random function -- that must already be some kind of finite table. (..) But you cannot really do that in this way, because you don't know beforehand what the function is going to be applied to". It then shows an example of a function from strings to booleans, making it evne more obvious that we should wait until we are given a value before we produce a result. Main insight: "in a terminating computation, any function is only applied a finite number of times". (The Argument class in the presentation is called Function in modern QuickCheck.)

Pretty sure that at least promote is not definable, because it relies on capturing the PRNG. Would it make sense to have an additional constructor in Gen for this...?

data Gen a where
  Pure  :: a -> Gen a
  Prim  :: Prim a -> Gen a
  Bind  :: Gen a -> (a -> Gen b) -> Gen b
  STree :: Gen SampleTree

perhaps...? How would that then shrink...?

[edsko]

Related suggestion from @phadej for a monad-law-preserving

data Freer f a where
  Pure :: a -> Freer f a
  Bind :: f b -> (b -> Freer f a) -> Freer f a

newtype Prim a = Prim (SMGen -> a)

interpret :: SMGen -> Freer Prim a -> a
interpret _ (Pure x)         = x
interpret g (Bind (Prim f) k = case split g of
  (g1, g2) -> interpret g2 (k (f g1))

Note that Prim can capture the SMGen here, which would enable us to define promote. If we can make something like this work, that would be nice, but it requires some thought.