haskell - 使用可变状态计算的惰性列表？

Question

我想大致弄清楚如何在惰性列表的计算中使用可变状态。

例如，这是一个使用可变数组 ( source ) 实现的简单的 Eratosthenes 筛选:

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返回一个 bool 数组，表示哪些数字是素数。

有没有办法使用这种方法来创建这些素数的惰性列表？这就像添加一个 yield i紧跟在 writeArray 之后陈述。

Answer 1

为实现惰性而对程序进行的最小修改可能是切换到惰性 ST monad ( 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 -> 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

错误调用只是为了展示结果的真正惰性:

*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

如果要避免中间列表 Maybes ，例如，您可以使用以下代码:

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