doing state right

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

doing state right

Floptical Logic
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 ()
Reply | Threaded
Open this post in threaded view
|

doing state right

Quentin Moser
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.
Reply | Threaded
Open this post in threaded view
|

doing state right

Chaddaï Fouché
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?
Reply | Threaded
Open this post in threaded view
|

doing state right

Chaddaï Fouché
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?
Reply | Threaded
Open this post in threaded view
|

doing state right

Floptical Logic
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?
>