Haskell：懒惰的Control.Monad.ST.Lazy` monad有多懒？ [英] Haskell: How lazy is the lazy `Control.Monad.ST.Lazy` monad?

问题描述

我一直在试验严格和懒惰的 ST 单子，我不明白每个单子的懒惰程度。
例如，使用懒惰的 Control.Monad.State.Lazy monad，我们可以这样写：

 main = print $（flip evalState）a$ do 
永远$ putb
放置c
 get 
  

这可以正常工作，并输出c。同样，严格的 Control.Monad.State.Strict 变种的相同代码将永远运行放置b并挂起。

直觉上，我期望同样的双重性可以适用于 ST monad。也就是说，给定代码：

  main = print $ S.runST $ do 
r < -  newSTRefa 
永远$ writeSTRef rb
 writeSTRef rc
 readSTRef r 
  

Control.Monad.ST.Lazy 应输出c，而 Control.Monad.ST.Strict 应该挂起。但是，它们都无限循环。我认为有一个合理的原因，比如： backwards ，引用 r 在最后一次<调用code> writeSTRef 。但它总觉得我们可以做得更好。

解决方案

懒惰 Control.Monad.ST.Lazy monad？

令人惊讶的是，它非常懒惰。但 Data.STRef.Lazy 不是。

ST.Lazy

让我们再关注另一个例子：

pre> 导入合格的Control.Monad.ST作为S
导入合格的Control.Monad.ST.Lazy作为L

平方：Monad m => ; m [Integer]
squared = mapM（return。（^ 2））[1 ..]

ok，oops :: [Integer]
ok = L.runST squared
oops = S.runST平方


即使 ok 和 oops 应该做同样的事情，我们只能得到 ok 的元素。如果我们尝试使用 head oops ，我们会失败。然而，关于 ok ，我们可以采取任意多个元素。

或者，将它们与非一元它们的行为如下：

  ok，oops :: [Integer] 
 ok'= map（^ 2 ）[1 ..] 
 oops'= let x = map（^ 2）[1 ..]有效x  -  Control.DeepSeq.force 
  

这是因为严格版本会评估所有状态操作，即使它们不是我们的结果所必需的。另一方面，延迟版本延迟了操作：

该模块提供了与Control.Monad.ST相同的接口，除了

关于 readSTRef ？

现在让我们再次关注您的示例。请注意，我们可以通过更简单的代码获得无限循环：

  main = print $ L.runST $ do 
永远$ return（）
r < -  newSTRefa
 readSTRef r 
  

如果我们在最后添加一个额外的 return ...

  main =打印$ L.runST $ do 
 forever $ return（）
r < -  newSTRefa
 readSTRef r 
返回a
  

...一切都很好。显然，在 newSTRef 或 readSTRef 中有一些严格的要求。让我们看看他们的实现：

 将合格的Data.STRef导入为ST 
 
 newSTRef = strictToLazyST。 ST.newSTRef 
 readSTRef = strictToLazyST。 ST.readSTRef 
 writeSTRef ra = strictToLazyST（ST.writeSTRef ra）
  

还有罪魁祸首。 Data.STRef.Lazy 实际上是通过 Data.STRef 实现的，它的意思是控制.Monad.ST.Strict 。 strictToLazyST 只隐藏这个细节：

  strictToLazyST :: ST.ST sa  - > ST s a 
 strictToLazyST m = ST $ \ s  - > 
  

将严格的ST计算转换为惰性计算。传递给 strictToLazyST 的严格状态线程不会被执行，直到它返回的惰性状态线程的结果被要求。

现在让我们把它们放在一起：

• main print 由懒惰 ST 计算给出的值


• 懒惰 ST 计算值由懒惰 readSTRef


• 懒惰的 readSTRef 实际上是作为一个懒惰的包装来实现的，它围绕 readSTRef


• 严格的 readSTRef 将状态评估为严格的状态


• 严格评估 forever $返回（）咬我们

所以当前 ST.Lazy 足够懒惰。 Data.STRef.Lazy 太严格了。只要 Data.STRef.Lazy 基于 strictToLazyST ，这种行为将会持续。

I have been experimenting with the strict and lazy ST monads, and I do not understand clearly the degree of laziness of each. For example, using the lazy Control.Monad.State.Lazy monad we can write:

main = print $ (flip evalState) "a" $ do
    forever $ put "b"
    put "c"
    get

This works fine and outputs "c". Dually, the same code for the strict Control.Monad.State.Strict variant will run put "b" forever, and hang.

Intuitively, I would expect the same duality to hold for the ST monads. That is, given the code:

main = print $ S.runST $ do
        r <- newSTRef "a"
        forever $ writeSTRef r "b"
        writeSTRef r "c"
        readSTRef r

Control.Monad.ST.Lazy should output "c", while Control.Monad.ST.Strict should hang. However, they both loop indefinitely. I believe that there is a valid reason for this, like: reading backwards, the reference r is not yet allocated at the time that the last writeSTRef is called. But it somehow feels like we could do better.

解决方案

How lazy is the lazy Control.Monad.ST.Lazy monad?

Surprisingly, it is perfectly lazy. But Data.STRef.Lazy isn't.

ST.Lazy is lazy

Lets focus on another example for a second:

import qualified Control.Monad.ST as S
import qualified Control.Monad.ST.Lazy as L

squared :: Monad m => m [Integer]
squared = mapM (return . (^2)) [1..]

ok, oops :: [Integer]
ok   = L.runST squared
oops = S.runST squared

Even though ok and oops should do the same, we can get only the elements of ok. If we would try to use head oops, we would fail. However, concerning ok, we can take arbitrarily many elements.

Or, to compare them to the non-monadic squared list, they behave like:

ok, oops :: [Integer]
ok'   = map (^2) [1..]
oops' = let x = map (^2) [1..] in force x -- Control.DeepSeq.force

That's because the strict version evaluates all state operations, even though they're not required for our result. On the other hand, the lazy version delays the operations:

This module presents an identical interface to Control.Monad.ST, except that the monad delays evaluation of state operations until a value depending on them is required.

What about readSTRef?

Now lets focus again on your example. Note that we can get an infinite loop with even simpler code:

main = print $ L.runST $ do
    forever $ return ()
    r <- newSTRef "a"
    readSTRef r

If we add an additional return at the end …

main = print $ L.runST $ do
    forever $ return ()
    r <- newSTRef "a"
    readSTRef r
    return "a"

… everything is fine. So apparently there's something strict in newSTRef or readSTRef. Lets have a look at their implementation:

import qualified Data.STRef as ST

newSTRef        = strictToLazyST . ST.newSTRef
readSTRef       = strictToLazyST . ST.readSTRef
writeSTRef  r a = strictToLazyST (ST.writeSTRef r a)

And there's the culprit. Data.STRef.Lazy is actually implemented via Data.STRef, which is meant for Control.Monad.ST.Strict. strictToLazyST only hides this detail:

strictToLazyST :: ST.ST s a -> ST s a
strictToLazyST m = ST $ \s ->

Convert a strict ST computation into a lazy one. The strict state thread passed to strictToLazyST is not performed until the result of the lazy state thread it returns is demanded.

Now lets put things together:

• in main, we want to print the value given by the lazy ST computation
• the lazy ST computation's value is given by a lazy readSTRef
• the lazy readSTRef is actually implemented as a lazy wrapper around the strict readSTRef
• the strict readSTRef evaluates the state as if it was a strict one
• the strict evaluation of forever $ return () bites us

So the current ST.Lazy is lazy enough. It's the Data.STRef.Lazy that's too strict. As long as Data.STRef.Lazy is based on strictToLazyST, this behavior will endure.

这篇关于Haskell：懒惰的Control.Monad.ST.Lazy` monad有多懒？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！