Очень медленная охрана в моей монадической случайной реализации (haskell) - PullRequest
Новая
       22

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

1 голос
/ 01 апреля 2010

Я пытался написать одну реализацию генератора случайных чисел, основанную на классе чисел. Я также добавляю туда 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)

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

Что я делаю не так?

Ответы [ 2 ]

3 голосов
/ 01 апреля 2010

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

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

Нам нужно вывести это 42, поэтому нам нужно g. Место, где можно получить 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))
1 голос
/ 01 апреля 2010

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

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

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

...