Introduction

The code below is a lightly modified version of an example in chapter 9 of the fine “Purescript by Example” book1.

module Example.ManyRect where						
									
import Prelude								
									
import Control.Monad.Eff (Eff, foreachE)				
import Data.Maybe (Maybe(..))						
import Graphics.Canvas (CANVAS, fillRect, setFillStyle, getContext2D,	
                       getCanvasElementById)				
import Partial.Unsafe (unsafePartial)					
import Data.Foldable (for_)						
import Data.Array ((..))						
import Data.Int (toNumber)    						
									
main :: Eff (canvas :: CANVAS) Unit					
main = void $ unsafePartial do						
  Just canvas <- getCanvasElementById "canvas"				
  ctx <- getContext2D canvas						
									
  _ <- setFillStyle "#0000FF" ctx					
									
  for_ (1..1000) (\x -> void $						
     fillRect ctx							
       { x: toNumber x, y: toNumber x, w: 100.0, h: 100.0 })		
									
  _ <- setFillStyle "#00ff00" ctx					
									
  void $ fillRect ctx { x: 0.0, y: 200.0, w: 50.0, h: 50.0 }

As you might guess, it draws 1,000 overlapping blue squares, and then a single green one.

This code works, but if you increase the number of blue squares, say to 1,000,000 then it crashes. If you’ve got a Javascript console open then you’ll see an error:

Uncaught RangeError: Maximum call stack size exceeded

Otherwise you’ll just wonder why the green square doesn’t get drawn.

Recursion

The key to understanding this problem is to realize that in many functional languages, including Purescript, loops are often implemented recursively. So, naively, each step of the loop corresponds to a subroutine call.

In Javascript the size of the call stack is limited. Inevitably, this has been discussed on Stack Overflow:

A general rule seems to be that if you’re doing lots of recursion in Purescript, you might hit a Javascript limit.

This problem isn’t new. There’s a specific term for converting the recursive calls into a loop: “tail call elimination”. Unsurprisingly, Wikipedia has a good article4 about it.

Here though, it’s hard to manipulate the code run by the Javascript engine, because it’s generated by the Purescript compiler.

A proper solution

Happily though, there is a very easy way to solve the problem. The Eff monad has a specific looping construct foreachE:

foreachE :: forall e a. Array a -> (a -> Eff e Unit) -> Eff e Unit

You’ll see that this only works if the effect returns Unit, but that’s fine here: we care about the associated action e.g. drawing a rectangle, rather than the return value.

So, to fix the program above we need only replace:

  for_ (1..1000) ...

with

  foreachE (1..1000000) ...

and we’re done!