Rand monad 的无限递归

Question

我有这个工作程序：

import Control.Monad.Random

data Tree = Node Tree Tree Tree Tree
          | Leaf Bool
          deriving (Show)

randomTree' :: (RandomGen a) => Int -> Rand a Tree
randomTree' 0 = do
  r <- getRandom
  return $ Leaf r

randomTree' depth = do
  let d = depth-1
  a <- randomTree' d
  b <- randomTree' d
  c <- randomTree' d
  d <- randomTree' d
  r <- getRandom
  if r
    then return $ Node a b c d
    else randomTree' 0

randomTree1 :: Int -> Tree
randomTree1 seed = evalRand (randomTree' 4) (mkStdGen seed)

main = print $ randomTree1 1

但我不完全理解为什么这个其他版本失败并填满了我所有的 RAM（有 thunk？）：

randomTree'' :: (RandomGen a) => Int -> Rand a Tree
randomTree'' depth = do
  let d = depth-1
  a <- randomTree'' d
  b <- randomTree'' d
  c <- randomTree'' d
  d <- randomTree'' d

  r1 <- getRandom
  r2 <- getRandom
  if depth > 0 && r1
    then return $ Node a b c d
    else return $ Leaf r2

多亏了懒惰，a b c 和 d 不应该只在需要时才评估吗？

谢谢！

Answer 1

不幸的是，不，懒惰在这里帮不了你：通过计算的随机种子增加了一个数据依赖性，可以消除任何可能的懒惰。

具体来说：您检查通过调用 getRandom 计算得出的 r1 是否为 True。要知道这一点，必须发现在调用 getRandom 时使用哪个种子；要知道使用哪个种子，必须首先对递归调用 randomTree'' 所需的种子进行修改。由于在基本情况下递归调用永远不会触底，它们只会消耗越来越多的 RAM，直到您的计算机出现故障。糟透了！

Rand monad 的无限递归

Infinite recursion with the Rand monad

monads

haskell

lazy-evaluation