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.