IFS In Haskell

Posted by alpheccar - Mar 18 2007 at 12:45 CEST

This weekend, I wanted to do some experimentations with random number generation and arrays in Haskell. So, I decided to build a small Iterated Function System (IFS) library because it is a quite standard stuff, easy and which can generate some cool pictures. And, it needs random number generation, array and speed.

If you don't know anything about IFS, just have a look at some documentation.

So, how to do that in Haskell ? First, you need a way to generate an image and save it to a file. I implemented support for the .ppm file since it is easy.

Then, you need a random number generator. The following function is generating a stream of random numbers.

randomRs

With that stream, I need to generate a new stream of linear operators. I just have to write a pick function selecting a matrix from a list based on a probability. Then, I just need to filter my stream of random numbers with that pick function. And, I am getting something like:

map (pick x) .  randomRs

where x is my list of linear operators (to be accurate : affine operators).

Then, I need to generate a random trajectory from an initial vector. The scanl function is the one to use. So, assuming I have an operator <*> acting on a vector with a matrix, then I am getting the random trajectory with:

scanl (flip (<*>)) startVector . map (pick x) .  randomRs

Then, I am dropping the first 100 point and keeping the next n ones:

take n . drop 100 . scanl (flip (<*>)) startVector . 
   map (pick x) .  randomRs

This list of points must now be written to an array and I need to count how many time each pixel is hit by that random trajectory. I am using accumArray with the (+) operator to count the hits:

accumArray (+) 0 (0,width*height) . take n . drop 100 . 
   scanl (flip (<*>)) startVector . map (pick x) .  randomRs

and I am using Data.Array.Unboxed for speed.

This array must now be converted into a list of r,g,b values. I am using the elems function to generate the list of values contained in the array and a coloring function that will transform each array value into a triple of r,g,b value. A foldr colorize does the job :

foldr colorize [] . elems . accumArray (+) 0 (0,width*height) . 
   take n . drop 100 . scanl (flip (<*>)) startVector . 
   map (pick x) .  randomRs

Finally I am writing that stream to a file using the ByteString package:

B.hPut h . B.pack . foldr colorize [] . elems  . 
   accumArray (+) 0 (0,width*height) . take n . drop 100 . 
   scanl (flip (<*>)) startVector . map (pick x) .  randomRs

So, generating an IFS picture is done in one line !

Here are two examples generated with 200000 pixels:

sierpinski :: IFS Double
sierpinski =   0.33 <?> linearIFS (scaling 0.5 0.5)
          <+>  0.33 <?> linearIFS (translation 0.5 0 * scaling 0.5 0.5)    
          <+>  0.33 <?> linearIFS (translation 0 0.5 * scaling 0.5 0.5) 

I created a small algebra to build the IFS. My IFS also have a non-linear part hence the use of linearIFS in the examples. But, I have not yet tested that non-linear part.

fern :: IFS Double
fern =  (0.01 <?> linearIFS(linear 0 0 0 0.16 0 0)
    <+> 0.08 <?> linearIFS(linear 0.2 (-0.26) 0.23 0.22 0 1.6)
    <+> 0.08 <?> linearIFS(linear (-0.15) 0.28 0.26 0.24 0 0.44)
    <+> 0.74 <?> linearIFS(linear 0.75 0.04 (-0.04) 0.85 0 1.6))

Unfortunately, the fern described by the previous code is not centered and my code is assuming that all fractal are inside the unit square. So to get the following picture, we need to change the fern definition.

To move the picture we need to act on each matrix of the IFS. The action is a conjugation one (just multiplying by the matrix would change the structure of the IFS and not act on the final picture). It can easily be done with the current API:

createPict "fern.ppm" 600 600 200000 
   (binaryColor (RGB 238 238 238) green) 
   (translation 0.5 0 <*> scaling 0.1 0.1 <*> fern)

Note that I had to format my haskell lines for the blog otherwise the lines were too longs.

You can get the code with:

darcs http://darcs.alpheccar.org/IFS

or on the hackage web site if you do not have darcs.

Tags haskell | graphics | fractal | maths