Very slow guards in my monadic random implementation (haskell)

Question

Hi! I was tried to write one random number generator implementation, based on number class. I also add there Monad and MonadPlus instance.

What mean "MonadPlus" and why I add this instance? Because of I want to use guards like here:

--  test.hs       --

import RandomMonad
import Control.Monad
import System.Random 

x = Rand (randomR (1 ::Integer, 3)) ::Rand StdGen Integer

y = do
 a <-x
 guard (a /=2) 
 guard (a /=1)
 return a

here comes RandomMonad.hs file contents:

-- RandomMonad.hs --

module RandomMonad where
import Control.Monad
import System.Random 
import Data.List 
data RandomGen g => Rand g a = Rand (g ->(a,g))  | RandZero

instance (Show g, RandomGen g) => Monad (Rand g)
 where
 return x = Rand (\g ->(x,g))
 (RandZero)>>= _ = RandZero

 (Rand argTransformer)>>=(parametricRandom) =  Rand funTransformer 
  where 
  funTransformer g | isZero x = funTransformer g1
                   | otherwise = (getRandom x g1,getGen x g1)
   where
   x = parametricRandom val
   (val,g1) = argTransformer g
   isZero RandZero = True
   isZero _ = False

instance (Show g, RandomGen g) => MonadPlus (Rand g)
 where
 mzero = RandZero
 RandZero `mplus` x = x
 x `mplus` RandZero = x
 x `mplus` y = x 

getRandom :: RandomGen g => Rand g a ->g ->a
getRandom (Rand f) g = (fst (f g)) 
getGen :: RandomGen g => Rand g a ->g -> g
getGen (Rand f) g = snd (f g)

when I run ghci interpreter, and give following command

getRandom y (mkStdGen 2000000000)

I can see memory overflow on my computer (1G). It's not expected, and if I delete one guard, it works very fast. Why in this case it works too slow?

What I do wrong?

Answer 1

Your definition of (>>=) is certainly wrong, but I cannot point to where because it is so complicated! Instead I will explain why it cannot be defined correctly using an example. Consider:

Rand (\g -> (42,g)) >>= const mzero

We need to get that 42 out, so we need a g. The place to get the g is from the return value of the bind, so the answer is definitely:

Rand (\g -> ...)

For some ..., responsible for returning a (b,g) pair. Now that we have 42, we can evaluate const mzero 42 and find that we have RandZero But where are we going to get that b? It is nowhere (in fact, so nowhere in this example that it can be any type whatsoever, since the type of the expression is forall b. Rand b).

What is the purpose of RandZero for your monad? Are you just trying to make StateT g Maybe? My guess is that you are. In that case, you might have more luck trying to implement this type:

newtype Rand g a = Rand (g -> Maybe (a, g))

Answer 2

If I understand your "monad" correctly, (>>=) fails to be associative. Try defining

y' = do a <- do a' <- x
                guard (a' /= 2)
                return a'
        guard (a /= 1)
        return a

to check whether this is the case. Effectively, your backtracking strategy can only undo the last step, not the entire computation.