我想大体上弄清楚如何在惰性列表的计算中使用可变状态。
例如,这是使用可变数组(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 数组,该 bool 数组表示哪些数字是质数。有没有办法使用这种方法来创建这些素数的惰性列表?这就像在
yield i
语句之后添加writeArray
一样。 最佳答案
为实现惰性而对程序进行的最小修改可能是切换到惰性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