I am using a PPM library to generate a square image where each white
pixel represents a prime number. The PPM library takes a function (Int -> Int -> Colour) to create the image. This interface isn't ideal but it is what I have to work with. I am convinced that using a sieve is faster than testing every pixel in the image for primality, but the (Int -> Int -> Colour) interface makes this awkward. The code below attempts to treat the list of prime numbers as a stack via global mutable state, popping the head whenever the pixel is prime. Obviously this is not idiomatic Haskell. What is the correct approach of dealing with state here? Thanks for reading. import ONeillPrimes import PPM6 import Colour import Data.IORef import System.IO.Unsafe limit = 2000 slimit = limit*limit primeList = takeWhile (<=slimit) primes p :: IORef [Int] p = unsafePerformIO (newIORef primeList) pcol n = unsafePerformIO $ do xs <- readIORef p if null xs then return black else if n == head xs then do writeIORef p (tail xs) return white else return black main = quick_ppm "foo.ppm" (\i j -> pcol ((i-1)*limit+j)) limit limit -- quick_ppm :: FilePath -> (Int -> Int -> Colour.Colour) -> Int -> Int -> IO () |
On Thu, 23 Apr 2009 00:59:37 -0500
Floptical Logic <[hidden email]> wrote: > I am using a PPM library to generate a square image where each white > pixel represents a prime number. The PPM library takes a function > (Int -> Int -> Colour) to create the image. This interface isn't > ideal but it is what I have to work with. I am convinced that using a > sieve is faster than testing every pixel in the image for primality, > but the (Int -> Int -> Colour) interface makes this awkward. The code > below attempts to treat the list of prime numbers as a stack via > global mutable state, popping the head whenever the pixel is prime. > Obviously this is not idiomatic Haskell. What is the correct approach > of dealing with state here? Thanks for reading. > > import ONeillPrimes > import PPM6 > import Colour > > import Data.IORef > import System.IO.Unsafe > > limit = 2000 > slimit = limit*limit > > primeList = takeWhile (<=slimit) primes > > p :: IORef [Int] > p = unsafePerformIO (newIORef primeList) > > pcol n = unsafePerformIO $ do > xs <- readIORef p > if null xs then return black else > if n == head xs > then do > writeIORef p (tail xs) > return white > else > return black > > main = quick_ppm "foo.ppm" (\i j -> pcol ((i-1)*limit+j)) limit limit > > -- quick_ppm :: FilePath -> (Int -> Int -> Colour.Colour) -> Int -> > Int -> IO () _______________________________________________ > Beginners mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/beginners Since Haskell is a pure language, the type (Int -> Int -> Colour) means that the result of the function will _only_ depend on its Int parameters. Not on some external state, not even on the order of execution. Using unsafePerformIO to nevertheless fit a dependency on state in such a function, like you did, is extremely dangerous. First of all, the interface to quick_ppm makes absolutely no guarantee regarding the order in which the colors of the different pixels will be evaluated; after all, it simply shouldn't matter. Second, and worse, a function such as pcol risks breaking compiler optimisations that rely on its purity. The fact that your current program actually happens to work (if it does) is simply a stroke of luck. The bottom-line is: the quick_ppm interface is simply too restrictive to implement your algorithm. You'll have to either - Find another function in the library with a more flexible type. - Drop the optimisation and search the whole primes list from the beginning every time (urk!). As for the proper use of unsafePerformIO: Referential transparency (the fact that a function, called with the same arguments, will always produce the same result) is not just a safety restriction; it's a fundamental part of the semantics of Haskell, and compilers rely heavily on it. Using unsafePerformIO to create an unpure function means breaking the language's semantics, which will result in misbehaving or segfaulting code. So that's definitely not what unsafePerformIO is for. You should instead only use it when you can _prove_ that the resulting function will actually be referentially transparent, i.e. whatever side-effects it uses are purely local and don't affect the rest of the program at all. |
In reply to this post by Floptical Logic
On Thu, Apr 23, 2009 at 7:59 AM, Floptical Logic
<[hidden email]> wrote: > I am using a PPM library to generate a square image where each white > pixel represents a prime number. ?The PPM library takes a function > (Int -> Int -> Colour) to create the image. ?This interface isn't > ideal but it is what I have to work with. ?I am convinced that using a > sieve is faster than testing every pixel in the image for primality, > but the (Int -> Int -> Colour) interface makes this awkward. Only because you're still not familiar with arrays in Haskell, this interface is absolutely not a problem : main = quick_ppm "foo.ppm" (\i j -> isPrime ((i-1)*limit+j)) limit limit where isPrime n = primeSieve ! n primeSieve :: UArray Int Bool primeSieve = accumArray (\_ _ -> True) False (0,limit*limit) $ zip primes (repeat ()) There are in fact algorithms that would directly do the sieve on an array (the classical algorithm would do nicely) but if you don't need exceedingly good performance, that will do. -- Jeda? |
On Thu, Apr 23, 2009 at 10:03 AM, Chadda? Fouch?
<[hidden email]> wrote: > > main = quick_ppm "foo.ppm" (\i j -> isPrime ((i-1)*limit+j)) limit limit > ?where > ? ?isPrime n = primeSieve ! n > ? ?primeSieve :: UArray Int Bool > ? ?primeSieve = accumArray (\_ _ -> True) False (0,limit*limit) $ zip > primes (repeat ()) > That should read as "zip (takeWhile (<= limit*limit) primes) (repeat ())" of course. -- Jeda? |
Bah! I completely forgot arrays were constant in lookup.
Thanks On Thu, Apr 23, 2009 at 3:05 AM, Chadda? Fouch? <[hidden email]> wrote: > On Thu, Apr 23, 2009 at 10:03 AM, Chadda? Fouch? > <[hidden email]> wrote: >> >> main = quick_ppm "foo.ppm" (\i j -> isPrime ((i-1)*limit+j)) limit limit >> ?where >> ? ?isPrime n = primeSieve ! n >> ? ?primeSieve :: UArray Int Bool >> ? ?primeSieve = accumArray (\_ _ -> True) False (0,limit*limit) $ zip >> primes (repeat ()) >> > > That should read as "zip (takeWhile (<= limit*limit) primes) (repeat > ())" of course. > > -- > Jeda? > |
Free forum by Nabble | Edit this page |