Очень медленные охранники в моей монадической случайной реализации (haskell)

Question

Я попытался написать одну генерацию случайных чисел, основанную на классе чисел. Я также добавляю экземпляр Monad и MonadPlus.

Что означает «MonadPlus» и почему я добавляю этот экземпляр? Из-за я хочу использовать охранников, как здесь:

-- 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 

здесь приходит RandomMonad.hs содержимое файла:

-- 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) 

, когда я бегу GHCI переводчика, и дать следующую команду

getRandom y (mkStdGen 2000000000) 

I может видеть переполнение памяти на моем компьютере (1G). Этого не ожидается, и если я удалю одного охранника, он работает очень быстро. Почему в этом случае он работает слишком медленно?

Что я делаю неправильно?

Answer 1

Ваше определение (>>=), конечно, неверно, но я не могу указать, где, потому что это так сложно! Вместо этого я объясню, почему он не может быть правильно определен с использованием примера. Рассмотрим:

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

Мы должны получить, что 42, так что нам нужно g. Место, чтобы получить г от значения возвращаемого затруднительное, так что ответ определенно:

Rand (\g -> ...) 

Для некоторых ..., ответственность за возвращение в (b,g) пару. Теперь, когда у нас есть 42, мы можем оценить const mzero 42 и найти, что у нас есть RandZero Но где мы собираемся получить это b? Это нигде (фактически, так нигде в этом примере, что это может быть любой тип вообще, так как тип выражения forall b. Rand b).

Какова цель RandZero для вашей монады? Вы просто пытаетесь сделать StateT g Maybe? Я предполагаю, что это так. В этом случае, вы можете иметь больше удачи пытается реализовать этот тип:

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

Answer 2

Если я понимаю, ваши «монады» правильно, (>>=) не может быть ассоциативно. Попробуйте определить

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

, чтобы проверить, действительно ли это. Эффективно, ваша стратегия возврата может только отменить последний шаг, а не весь расчет.