haskell - 使用严格的 monad 操作无限列表

Question

我有一个函数f :: [a] -> b对无限列表进行操作(例如 take 5 、 takeWhile (< 100) . scanl (+) 0 等)。我想向此函数提供由严格的单子(monad)操作生成的值(例如 randomIO )。

来自this question ，我了解到repeat和sequence技巧方法不适用于严格的 monad，如下例所示:

import Control.Monad.Identity

take 5 <$> sequence (repeat $ return 1) :: Identity [Int]
-- returns `Identity [1,1,1,1,1]`
-- works because Identity is non-strict

take 5 <$> sequence (repeat $ return 1) :: IO [Int]
 -- returns `*** Exception: stack overflow`
 -- does not work because IO is strict

因此，我考虑在单子(monad)上下文“内部”使用该函数。我受到了这个启发circular programming example并尝试过:

let loop = do
       x <- return 1
       (_, xs) <- loop
       return (take 5 xs, x:xs)
in  fst loop :: Identity [Int]
-- Overflows the stack

和

import Control.Monad.Fix

fst <$> mfix (\(_, xs) -> do
   x <- return 1
   return (take 5 xs, x:xs)) :: Identity [Int]
-- Overflows the stack

甚至

{-# LANGUAGE RecursiveDo #-}
import System.Random

loop' = mdo
   (xs', xs) <- loop xs
   return xs'
where loop xs = do
      x <- randomIO
      return (take 5 xs, x:xs)

print $ loop'
-- Returns a list of 5 identical values

但是这些都不起作用。我还尝试了Conduit即使在 Identity 中也不起作用的方法案例:

import Conduit

runConduitPure $ yieldMany [1..] .| sinkList >>= return . take 5

因此我想知道:

1. 为什么上述“循环”方法都不起作用？

2. 如果存在不涉及 unsafeInterleaveIO 的解决方案。 (也许iteratee秒，Arrow秒？)

Answer 1

I am using randomIO here just for simplicity of the examples. In practice, I would like to process messages received via sockets

如果没有unsafeInterleaveIO，这是不可能的。最终的问题是 IO 操作必须按顺序排列。虽然引用透明值的评估顺序并不重要，但 IO 操作的评估顺序可能会重要。如果你想要一个通过套接字接收到的所有消息的惰性无限列表，你必须事先通知 Haskell 在 IO 操作序列中适合的位置(除非你使用 unsafeInterleaveIO) >).

您正在寻找的 Arrow 抽象称为 ArrowLoop ，但它也存在严格单子(monad)的右紧缩定律问题。

乍一看，它可能看起来像 MonadFix (通过 mdo 或 mfix 体现)也是一个解决方案，但深入挖掘一下 shows that fixIO has problems ，就像 来自 ArrowLoop 的循环。

但是，有时 IO 操作必须依次运行的限制有点过分，这就是 unsafeInterleaveIO 的用途。引用 docs

unsafeInterleaveIO allows IO computation to be deferred lazily. When passed a value of type IO a, the IO will only be performed when the value of the a is demanded.

<小时/>

现在，即使您明确表示您不想要一个unsafeInterleaveIO解决方案，因为我希望能够说服您这是可行的方法，在这里它是:

interweavingRepeatM :: IO a -> IO [a]
interweavingRepeatM action = unsafeInterleaveIO ((:) <$> action <*> interweavingRepeatM action)

这是随机数的工作:

ghci> import System.Random
ghci> sourceOfRandomness <- interweavingRepeatM randomIO :: IO [Integer]
ghci> take 10 sourceOfRandomness
[-2002742716261662204,7803971943047671004,-8395318556488893887,-7372674153585794391,5906750628663631621,6428130029392850107,6453903217221537923,-8966011929671667536,6419977320189968675,-1842456468700051776]