haskell - 如何在 Haskell 迭代中保留随机数?

我正在尝试用随机数计算增长列表。基本代码在这里:

import System.Random

randint :: IO Int
randint = randomRIO (0,1)

type Generation = [Int]

gnext :: Generation -> IO Generation
gnext g = flip (:) g <$> randint

gnext 可以更复杂。

现在以下代码按预期运行:

test1 = do
  let b0 = []
  b1 <- gnext b0
  b2 <- gnext b1
  b3 <- gnext b2
  b4 <- gnext b3
  return [b0, b1, b2, b3, b4]
ghci> test1
[[],[0],[1,0],[1,1,0],[1,1,1,0]]

我们可以看到第 n 个列表在其 cdr 部分中有第 (n-1) 个列表。

另一方面,以下代码失败了(我认为是因为懒惰的评估)。

test2 = sequence $ take 5 $ iterate (gnext =<<) (return [])
ghci> test2
[[],[0],[0,0],[1,0,1],[1,1,1,0]]

这个结果是完全随机的。

如何通过 test2 样式重写 test1 代码?谢谢你。

回答1

sequence $ take 5 $ iterate (gnext =<<) (return []) 有什么问题?

让我们减少 iterate (gnext =<<) (return [])

iterate (gnext =<<) (return []) =>
[ return []
, gnext =<< return []
, gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< gnext =<< return []
, ...
]

接下来减少 take 5 $ iterate (gnext =<<) (return [])

take 5 $ iterate (gnext =<<) (return []) =>
[ return []
, gnext =<< return []
, gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< gnext =<< return []
]

最后,减少 sequence $ take 5 $ iterate (gnext =<<) (return [])

sequence $ take 5 $ iterate (gnext =<<) (return []) =>
sequence [ return []
         , gnext =<< return []
         , gnext =<< gnext =<< return []
         , gnext =<< gnext =<< gnext =<< return []
         , gnext =<< gnext =<< gnext =<< gnext =<< return []
         ]

相当于:

do
    b0 <- return []
    b1 <- gnext =<< return []
    b2 <- gnext =<< gnext =<< return []
    b3 <- gnext =<< gnext =<< gnext =<< return []
    b4 <- gnext =<< gnext =<< gnext =<< gnext =<< return []
    return [b0, b1, b2, b3, b4]

如您所见,这不是您想要的,懒惰的评估与它无关。

你可以用 state monad 解决这个问题:

gnextM :: StateT Generation IO Generation
gnextM = do
    g0 <- get
    g1 <- liftIO $ gnext g0
    put g1
    return g1

test2 = flip evalStateT [] $ sequence $ take 5 $ repeat gnextM

或者:

gnextM :: StateT [Generation] IO ()                                         
gnextM = do                                                                 
    b0 <- gets head                                                         
    b1 <- liftIO $ gnext b0                                                 
    modify (b1:)                                                            

runGen :: StateT [Generation] IO a -> Generation -> IO [Generation]         
runGen gnext s = execStateT gnext [s]                                       
                                                                        
test2 = flip runGen [] $ replicateM 5 gnextM

取决于你想要什么。

回答2

以下代码失败(我认为是因为延迟评估)。

这并不是因为懒惰的评估。在 test1 中,您共享所有动作的结果链,而在 test2 中,您只共享动作本身,然后将它们排序在一起,它们的结果是不相关的:

test2 = sequence (take 5 actions)
  where
    actions
      = (return [])
      : [(gnext =<< a) | a <- actions]
test2 = sequence
  [ return []
  , gnext =<< return []
  , gnext =<< gnext =<< return []
  , gnext =<< gnext =<< gnext =<< return []
  , gnext =<< gnext =<< gnext =<< gnext =<< return []
  ]

所以问题是 sequence (take 5 actions) 没有表达你想要的关系,这更像是 fmap (take 5) (sequence actions)。不幸的是,这根本不会产生结果,因为 sequence 中的 sequence 太严格了:它会在产生结果之前尝试消耗 actions 的无限流。

相反,当您提前知道长度时,通常使用诸如 tails <$> replicateM 5 randint 之类的模式,如果不知道长度,则使用诸如 unfoldrM 之类的组合符:

test = unfoldrM step (b0, 5)
  where
    b0 = []
    step (b, i)
      | i == 0 = pure Nothing
      | otherwise = do
        b' <- gnext b
        pure (Just (b', (b', i - 1)))

-- Available in ‘monad-loops’ or as below.
unfoldrM
  :: (Monad m)
  => (a -> m (Maybe (b, a))) -> a -> m [b]
unfoldrM f = go
  where
    go a = do
      m <- f a
      case m of
        Just (b, a') -> do
          bs <- go a'
          pure (b : bs)
        Nothing -> pure []

相似文章