[Haskell-cafe] Some random newbie questions

[ross at soi.city.ac.uk]

On Thu, Jan 06, 2005 at 09:11:13AM -0800, Benjamin Pierce wrote:
> * I wrote a little program for generating Sierpinkski Carpets, and was
>   astonished to find that it runs out of heap under Hugs (with standard
>   settings -- raising the heap size with -h leads to a happier result).

This is an artifact of the graphics library you're using, which aims
at simplicity rather than efficiency.  The program appears to be quite
sequential, so one might assume that the space usage was proportional to
the depth of the recursion.  But in this library, each Window contains a
Graphics value that describes the picture it contains, and drawInWindow
just adds to that value, as well as triggering a redraw.  As a result
the space usage is proportional to the number of elements in the picture.

Since there's no benefit from using the IO monad everywhere, you might
as well construct the whole Graphics value and only call drawInWindow
once (which also means less drawing).  This way you only need to call
withColor once as well, and that's a fairly expensive operation in this
library.  This version is faster and uses less space, though still
proportional to the number of elements:

    fillSquare :: Int -> Int -> Int -> Graphics
    fillSquare x y s =
           polygon [(x,y), (x+s,y), (x+s,y+s), (x,y+s), (x,y)]

    carpet :: Int -> Int -> Int -> Graphics
    carpet x y s =
      if s < 8
      then fillSquare x y s
      else let s' = s `div` 3
        in overGraphics [
              carpet x        y        s',
              carpet (x+s')   y        s',
              carpet (x+s'*2) y        s',
              carpet x        (y+s')   s',
              carpet (x+s'*2) (y+s')   s',
              carpet x        (y+s'*2) s',
              carpet (x+s')   (y+s'*2) s',
              carpet (x+s'*2) (y+s'*2) s']

    main =
      runGraphics (
        do w <- openWindow "Carpet" (700,700)
           drawInWindow w
             (withColor Blue
                (carpet 50 50 600))
           k <- getKey w 
           closeWindow w
      )

Another alternative is to use Regions.