How To Draw A Fractal Tree By Hand

A fractal tree drawn with PureScript

Last week, I attended Mathias Brandewinder's F# (and Clojure) dojo in Copenhagen, and had great fun drawing a fractal tree in F# together with other attendees. Afterwards, I started thinking that it'd be fairly easy to port the F# code to Haskell, but then I reconsidered. The combination of Haskell, Windows, and drawing sounded intimidating. This seemed a good opportunity to take PureScript for a spin, because that would enable me to draw the tree on an HTML canvas.

In case you're wondering, a fractal tree is simply a tree that branches infinitely in (I suppose) a deterministic fashion. Here's an example of the output of the code of this article:

$A symmetric fractal tree.$

This is my first attempt at PureScript, and I think I spent between five and ten hours in total. Most of them I used to figure out how to install PureScript, how to set up a development environment, and so on. All in all I found the process pleasing.

While it's a separate, independent language, PureScript is clearly a descendant of Haskell, and the syntax is similar.

Separating data from effects #

In functional programming, you routinely separate data from effects. Instead of trying to both draw and calculate branches of a tree in a single operation, you figure out how to first define a fractal tree as data, and then subsequently you can draw it.

A generic binary tree is a staple of functional programming. Here's one way to do it:

          dataTree a=Leaf a|Node a (Tree a) (Tree a)

Such a tree is either a leaf node with a generically typed value, or an (intermediate) node with a value and two branches, which are themselves (sub)trees.

In a sense, this definition is an approximation, because a 'real' fractal tree has no leafs. In Haskell you can easily define infinite trees, because Haskell is lazily evaluated. PureScript, on the other hand, is eagerly evaluated, so infinite recursion would require jumping through some hoops, and I don't think it's important in this exercise.

While the above tree type can contain values of any type, in this exercise, it should contain line segments. One way to do this is to define a Line record type:

          dataLine=Line {x ::Number,y ::Number,angle ::Number,length ::Number,width ::Number }

This is a type with five labelled values, all of them numbers. x and y are coordinates for the origin of the line, angle defines the angle (measured in radians) from the origin, and length the length of the line. In a similarly obvious vein, width denotes the width of the line, although this data element has no impact on the calculation of the tree. It's purely a display concern.

Given the first four numbers in a Line value, you can calculate the endpoint of a line:

          endpoint :: forall r.   { x::Number          , y::Number          , angle::Number          , length::Number| r }->TupleNumberNumber          endpoint line=-- Flip the y value because Canvas coordinate system points down from upper          -- left corner          Tuple          (line.x+ line.length* cos line.angle)     (-(-line.y+ line.length* sin line.angle))

This may look more intimidating than it really is. The first seven lines are simply the (optional) type declaration; ignore that for a minute. The function itself is a one-liner, although I've formatted it on several lines in order to stay within an 80 characters line width. It simply performs a bit of trigonometry in order to find the endpoint of a line with an origin, angle, and length. As the code comment states, it negates the y value because the HTML canvas coordinate system points down instead of up (larger y values are further towards the bottom of the screen than smaller values).

The function calculates a new set of coordinates for the endpoint, and returns them as a tuple. In PureScript, tuples are explicit and created with the Tuple data constructor.

In general, as far as I can tell, you have less need of tuples in PureScript, because instead, you have row type polymorphism. This is still a new concept to me, but as far as I can tell, it's a sort of static duck typing. You can see it in the type declaration of the endpoint function. The function takes a line argument, the type of which is any record type that contains x, y, angle, and length labels of the Number type. For instance, as you'll soon see, you can pass a Line value to the endpoint function.

Creating branches #

In a fractal tree, you calculate two branches for any given branch. Typically, in order to draw a pretty picture, you make the sub-branches smaller than the parent branch. You also incline each branch an angle from the parent branch. While you can hard-code the values for these operations, you can also pass them as arguments. In order to prevent an explosion of primitive function arguments, I collected all such parameters in a single data type:

          dataFractalParameters=FractalParameters {leftAngle ::Number,rightAngle ::Number,shrinkFactor ::Number }

This is a record type similar to the Line type you've already seen.

When you have a FractalParameters value and a (parent) line, you can calculate its branches:

          createBranches ::FractalParameters->Line->TupleLineLine          createBranches (FractalParameters p) (Line line)=Tuple left rightwhereTuple x y= endpoint line     left=Line {       x: x,       y: y,       angle: pi* (line.angle/ pi+ p.leftAngle),       length: (line.length* p.shrinkFactor),       width: (line.width* p.shrinkFactor) }     right=Line {       x: x,       y: y,       angle: pi* (line.angle/ pi- p.rightAngle),       length: (line.length* p.shrinkFactor),       width: (line.width* p.shrinkFactor) }

The createBranches function returns a tuple of Line values, one for the left branch, and one for the right branch. First, it calls endpoint with line. Notice that line is a Line value, and because Line defines x, y, angle, and length labels, it can be used as an input argument. This type-checks because of row type polymorphism.

Given the endpoint of the parent line, createBranches then creates two new Line values (left and right) with that endpoint as their origins. Both of these values are modified with the FractalParameters argument, so that they branch off to the left and the right, and also shrink in an aesthetically pleasing manner.

Creating a tree #

Now that you can calculate the branches of a line, you can create a tree using recursion:

          createTree :: Int->FractalParameters->Line->TreeLine          createTree depth p line=if depth<=0thenLeaf lineelseletTuple leftLine rightLine= createBranches p line         left= createTree (depth-1) p leftLine         right= createTree (depth-1) p rightLineinNode line left right

The createTree function takes a depth argument, which specifies the depth (or is it the height?) of the tree. The reason I called it depth is because createTree is recursive, and depth controls the depth of the recursion. If depth is zero or less, the function returns a Leaf node containing the input line.

Otherwise, it calls createBranches with the input line, and recursively calls createTree for each of these branches, but with a decremented depth. It then returns a Node containing the input line and the two sub-trees left and right.

This implementation isn't tail-recursive, but the above image was generated with a recursion depth of only 10, so running out of stack space wasn't my biggest concern.

Drawing the tree #

With the createTree function you can create a fractal tree, but it's no fun if you can't draw it. You can use the Graphics.Canvas module in order to draw on an HTML canvas. First, here's how to draw a single line:

          drawLine ::Context2D->Line->Eff (canvas ::CANVAS)Unit          drawLine ctx (Line line)=doletTuple x' y'= endpoint line   void$ strokePath ctx$do          void$ moveTo ctx line.x line.y     void$ setLineWidth line.width ctx     void$ lineTo ctx x' y'     closePath ctx

While hardly unmanageable, I was surprised that I wasn't able to find a pre-defined function that would let me draw a line. Perhaps I was looking in the wrong place.

With this helper function, you can now draw a tree using pattern matching:

          drawTree ::Context2D->TreeLine->Eff (canvas ::CANVAS)Unit          drawTree ctx (Leaf line)= drawLine ctx line drawTree ctx (Node line left right)=do          drawLine ctx line   drawTree ctx left   drawTree ctx right

If the input tree is a Leaf value, the first line matches and the function simply draws the line, using the drawLine function.

When the input tree is a Node value, the function first draws the line associated with that node, and then recursively calls itself with the left and right sub-trees.

Execution #

The drawTree function enables you to draw using a Context2D value, which you can create from an HTML canvas:

mcanvas<- getCanvasElementById"canvas"          let canvas= unsafePartial (fromJust mcanvas) ctx<- getContext2D canvas

From where does the "canvas" element come? Ultimately, PureScript compiles to JavaScript, and you can put the compiled script in an HTML file together with a canvas element:

          <          body          ><          canvasid          =          "canvas"width          =          "800"height          =          "800"          ></          canvas          ><          scriptsrc          =          "index.js"type          =          "text/javascript"          ></          script          >          </          body          >

Once you have a Context2D value, you can draw a tree. Here's the whole entry point, including the above canvas-finding code:

          main ::Eff (canvas ::CANVAS)Unit          main=do          mcanvas<- getCanvasElementById"canvas"let canvas= unsafePartial (fromJust mcanvas)   ctx<- getContext2D canvaslet trunk=Line          { x:300.0, y:600.0, angle: (pi/2.0), length:100.0, width:4.0 }let p=FractalParameters          { leftAngle:0.1, rightAngle:0.1, shrinkFactor:0.8 }let tree= createTree10 p trunk   drawTree ctx tree

After it finds the Context2D value, it hard-codes a trunk Line and a set of FractalParameters. From these, it creates a tree of size 10 and draws the tree in the beginning of this article.

You can fiddle with the parameters to your liking. For example, you can make the right angle wider than the left angle:

          let p=FractalParameters          { leftAngle:0.1, rightAngle:0.2, shrinkFactor:0.8 }

This produces an asymmetric tree:

$An asymmetric fractal tree.$

In order to compile the code, I used this command:

$ pulp browserify -t html/index.js

This compiles the PureScript code to a single index.js file, which is output to the html directory. This directory also contains the HTML file with the canvas.

You can find the entire PureScript file in this Gist.

Summary #

It was fun to try PureScript. I've been staying away from JavaScript-based development for many years now, but if I ever have to do some client-side development, I may consider it. So far, I've found that PureScript seems viable for drawing. How good it is if you need to interact with 'normal' web-pages or SPAs, I don't know (yet).

If you have some experience with Haskell, it looks like it's easy to get started with PureScript.