使用可变状态计算懒惰列表？ [英] lazy list computed using mutable state?

问题描述

例如，这是一个幼稚的Eratosthenes Sieve实现的使用可变数组（源）：

  import Control.Monad.ST 
导入Data.Array.ST 
导入Data.Array.Unboxed 
 import Control.Monad 
 import Data.List 
 $ b $ prime：Int  - > UArray Int Bool 
 prime n = runSTUArray $ do 
 arr < -  newArray（2，n）True :: ST s（STUArray s Int Bool）
 forM_（takeWhile（\ x  - > x * x< = n）[2..n]）$ \ i  - >> （ai）$ forM_ [i ^ 2，i ^ 2 + i .. n] $ \ j  - >时，执行
 ai<  -  readArray arr i 
。做
 writeArray arr j False 
  - 产出i ??? 
  

prime n 返回一个布尔数组，表示哪些数字是素数。

有没有办法使用这种方法创建这些素数的懒惰列表？这就好像在 writeArray 语句后添加一个 yield i 。

lazy ST monad（ hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Monad-ST-Lazy.htmlrel =nofollow noreferrer> http://hackage.haskell.org/packages/archive/base /latest/doc/html/Control-Monad-ST-Lazy.html ），此代码可以工作：

  import Control.Monad.ST.Lazy 
 import Data.Array.ST 
 import Data.Array.Unboxed 
 import Control.Monad 
 import Data.List 
 import Data.Maybe 
 
 prime :: Int  - > [Int] 
 prime n = catMaybes $ runST $ do 
 arr<  -  strictToLazyST $ newArray（2，n）True :: ST s（STUArray s Int Bool）
 forM（takeWhile \x->> x< = n）[2..n]）$ \i  - >如果我== 83然后错误达到83else返回（）
 ai<  -  strictToLazyST $ readArray arr我
如果ai 
然后做
 strictToLazyST $ forM_ [i ^ 2，i ^ 2 + i .. n] $ 
 \j  - > writeArray arr j False 
 return（Just i）
 else return Nothing 
  

错误调用只是为了演示结果的真实懒惰性质：

  * Main>素数10000 
 [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79 ***例外：达到83 
  

如果您想要避免 Maybes ，例如，您可以使用以下代码：

  import Control.Monad.ST .Lazy 
导入Data.Array.ST 
导入Data.Array.Unboxed 
导入Control.Monad 
导入Data.List 
导入Data.Functor 
 
 prime :: Int  - > [Int] 
 prime n = runST $ do 
 arr<  -  strictToLazyST $ newArray（2，n）True :: ST s（STUArray s Int Bool）
 let primesFrom i |我> n =返回[] 
 |否则= do 
 ai<  -  strictToLazyST $ readArray arr i 
 if ai then do 
 strictToLazyST $ forM_ [i ^ 2，i ^ 2 + i .. n] $ 
 \j  - > writeArray arr j False 
（i :)< $> primesFrom（i + 1）
 else primesFrom（i + 1）
 primesFrom 2 
  

I'd like to figure out in general how to use mutable state in the computation of lazy lists.

For instance, here is a naive Sieve of Eratosthenes implemented using a mutable array (source):

import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
import Data.List

prime :: Int -> UArray Int Bool
prime n = runSTUArray $ do
    arr <- newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
    forM_ ( takeWhile ( \x -> x*x <= n ) [ 2 .. n ] ) $ \i -> do
        ai <- readArray arr i
        when ( ai  ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j -> do
            writeArray arr j False
            -- yield i ???

prime n returns an array of booleans which denote which numbers are prime.

Is there a way to use this approach to create a lazy-list of those primes? It would be like adding a yield i right after the writeArray statement.

解决方案

The smallest modification of your program to achieve lazyness is probably to switch to the lazy ST monad (http://hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Monad-ST-Lazy.html), where this code would work:

import Control.Monad.ST.Lazy
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
import Data.List
import Data.Maybe

prime :: Int -> [Int]
prime n = catMaybes $ runST $ do
    arr <- strictToLazyST $ newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
    forM ( takeWhile ( \x -> x <= n ) [ 2 .. n ] ) $ \i -> do
        if i == 83 then error "Reached 83" else return ()
        ai <- strictToLazyST $ readArray arr i
        if ai
          then do
            strictToLazyST $ forM_ [ i^2 , i^2 + i .. n ] $
                 \j -> writeArray arr j False
            return (Just i)
          else return Nothing

The error call is just to demonstrate the true lazy nature of the result:

*Main> prime 10000
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79*** Exception: Reached 83

If you want to avoid the intermediate list of Maybes, you can, for example, use this code:

import Control.Monad.ST.Lazy
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
import Data.List
import Data.Functor

prime :: Int -> [Int]
prime n = runST $ do
    arr <- strictToLazyST $ newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
    let primesFrom i | i > n = return []
                     | otherwise = do
            ai <- strictToLazyST $ readArray arr i
            if ai then do
                strictToLazyST $ forM_ [ i^2 , i^2 + i .. n ] $
                   \j -> writeArray arr j False
                (i:) <$> primesFrom (i + 1)
              else primesFrom (i + 1)
    primesFrom 2

这篇关于使用可变状态计算懒惰列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！