lazy list computed using mutable state?

Question

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.

You could also use the State Monad.

Christopher King
– Christopher King

2017-02-10 13:23:42 +00:00
Commented Feb 10, 2017 at 13:23 — Christopher King
– Christopher King, Commented Feb 10, 2017 at 13:23

dfeuer · Accepted Answer · 2017-02-10 04:19:34Z

9

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

edited Feb 10, 2017 at 4:19

dfeuer

48.8k5 gold badges69 silver badges171 bronze badges

answered Jul 21, 2012 at 22:19

Joachim Breitner

25.9k7 gold badges83 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

ErikR Over a year ago

thanks! seems to do what I need, except that for some reason the first program seems to stop at sqrt n, e.g. prime 10 returns [2,3]

ErikR Over a year ago

the second example works perfectly if the first guard clause for primesFrom i is changed to | i > n = return []

dfeuer Over a year ago

In the first one, the takeWhile needs an x^2.

dfeuer Over a year ago

You may also want to move the strictToLazyST calls outside the forM_. I don't know if it would affect efficiency, but it certainly should make it clearer.

dfeuer Over a year ago

FYI, I'm going to try using this technique to implement an O'Neill sieve using an array-based priority queue—profiling suggests the functional queue is killing performance.

|

Collectives™ on Stack Overflow

lazy list computed using mutable state?

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related