Recursion is a powerful and subtle concept. A great way to gain an intuition of its structure is to visualise different patterns of recursion with graphics. In this chapter, we will use a simplified interface to the vector graphics library Rasterific to generate recursive images.
Rasterific is included and ready to use in Haskell for Mac. No further installation is required.
To use Rasterific with a different Haskell system, please install it by executing
cabal install Rasterific in a command line shell.
Previous examples already used a
Point type to represent points in a 2-dimensional plane as a pair of floating point values denoting the point's x- and y-coordinates:
type Point = (Float, Float)
On top of that, we use two new definitions,
Path, which represent a line as a pair of the start point and end point as well as a path as a list of arbitrarily many points:
type Line = (Point, Point) type Path = [Point]
Furthermore, a colour consists of four values, specifying the red, green, blue, and alpha (opacity) components of that colour — also known as an RGBA colour representation. The individual component values should be between 0 and 255. Bigger values and smaller values are interpreted modulo 256.
-- Quadruple of red, green, blue, and opacity component. -- These values should all be between 0 and 255. type Colour = (Int, Int, Int, Int)
To simplify the use of colours, we predefine constant values for some basic colours. (We can combine multiple type signatures using the same type into one by listing all value or function names, separated by commas, and then, writing the type only once.)
white, black, blue, red, green, lightgreen, orange, magenta :: Colour
Finally, we regard a picture as a list of pairs of
type Picture = [(Colour, Path)]
drawPicture, applied to a
Picture value, draws this picture on a black canvas of size 800x800, where the origin
(0,0) is located at the left most, upmost corner, and
(800, 800) at the right most, lower most corner.
To get you started, we provide a Haskell for Mac project including all of the above type definitions together with an implementation of
drawPicture: Fractals.hsproj. This project includes two Haskell modules:
Fractals. The former contains the graphics definitions for you to use. The latter is where you can add code while working through this chapter.
Fractals.hsproj in Haskell for Mac and proceed as in the screencasts.
Run GHCi inside the
Fractals.hsproj directory after downloading and unpacking. Then, load the
Fractals module. To visualise your drawings, you need to write them to disk as a PNG image file. To do so, use the writePng function as follows:
writePng FILENAME (drawPicture LINEWIDTH PICTURE)
As a first, simple example we define the paths
house :: Path house = [(300, 750), (300, 450), (270, 450), (500, 200), (730, 450), (700, 450), (700, 750)] door :: Path door = [(420, 750), (420, 550), (580, 550), (580, 750)]
and then call
drawPicture 2.0 [(lightgreen, house), (red, door)]
where the first argument,
2.0, specifies the line width. It will display this picture.
In the following screencast, we incrementally construct the house in a playground and experiment with a few different colours.
Creating pictures by explicitly enumerating all the coordinates is tedious, though — instead, we want to write functions which do the work for us.
The spiral picture below is seemingly more complex than the one above, but actually takes a lot less effort to produce! The reason for this becomes clear, once we look at the picture more closely: it is composed of a set of lines, all originating at the same point. They differ in length, orientation, and colour, with the outer lines less and less opaque, but these changes clearly follow a simple pattern. This is good news, because it means once we identify the pattern, we can write a program that takes a line as argument and creates the picture.
A function —let's call it
spiralRays— drawing this spiral pattern needs to be able to perform three operations repeatedly, each of which we can implement as separate functions:
rotateLine :: Float -> Line -> Line: rotate a line at its origin by a given angle.
scaleLine :: Float -> Line -> Line: change the length of a line.
fade :: Colour -> Colour: decrease the opacity of a colour.
A caller of the
spiralRays function should be able to specify the number of lines in the picture, the initial line, and the initial colour (we could generalise it to also accept the rotation angle and scale factor as parameters, but let's keep it simple for now). The function
spiralRays itself is a recursive function following the list generator pattern that we discussed in Recursion: If
spiralRays is called with a first argument of
0, it returns an empty list. Called with a first argument greater than 0, it returns the current line as the first element of the result list, and as tail, the result of the recursive call on
n - 1, with a faded colour, and a rotated and scaled line:
spiralRays :: Int -> Colour -> Line -> Picture spiralRays n colour line@(p1, p2) | n <= 0 =  | otherwise = (colour, [p1, p2]) : spiralRays (n - 1) newColour newLine where newColour = fade colour newLine = scaleLine 1.02 (rotateLine (pi / 40) line)
The third argument pattern of
spiralRays uses an
@-pattern (pronounced, “at pattern”). Here, we are using
line@(p1, p2), which at once binds the variable
line to the third argument and the two variables
p2 to the first and second component of the pair that represents the line. This is convenient as we want to refer to the line as whole (as
line in the calculation of
newLine), but also to its components
p2 when constructing the path of length two for the first picture
Now, that we discussed the overall recursive structure, let us look at the three functions
fade in turn.
Rotation. Dusting off our school geometry knowledge (or doing a quick web search) tells us that rotating a line
((0, 0), (x, y)) by a given angle
alpha around the origin results in a line
(0, 0), (x', y')) where
Writing out the matrix-vector multiplication, we get
x' = x * cos alpha - y * sin alpha y' = x * sin alpha + y * cos alpha
which leads to the following Haskell program
rotateLine :: Float -> Line -> Line rotateLine alpha ((0, 0), (x, y)) = ((0, 0), (x', y')) where x' = x * cos alpha - y * sin alpha y' = x * sin alpha + y * cos alpha
In general, though, we want to rotate lines that do not start at the origin
(0, 0). Nevertheless, we want to perform the rotation around the first point of the line (i.e., its starting point). We achieve this by first moving the line to the origin (by subtracting the
y1-values of the starting point), then rotating the resulting line using the above calculation, and finally, moving the rotated line back to its original starting point. Overall, we get
rotateLine :: Float -> Line -> Line rotateLine alpha ((x1, y1), (x2, y2)) = ((x1, y1), (x' + x1, y' + y1)) where x0 = x2 - x1 y0 = y2 - y1 x' = x0 * cos alpha - y0 * sin alpha y' = x0 * sin alpha + y0 * cos alpha
Scaling. To scale a line by a given factor, we also shift it to start at the origin
(0, 0), then multiply the
y2-values of the endpoint of the shifted line with the scaling factor, and finally, shift the line back to its actual starting point:
scaleLine :: Float -> Line -> Line scaleLine factor ((x1, y1), (x2, y2)) = ((x1, y1), (x' + x1, y' + y1)) where x0 = x2 - x1 y0 = y2 - y1 x' = factor * x0 y' = factor * y0
fade function simply substracts
1 from the opacity component of the colour:
fade :: Colour -> Colour fade (redC, greenC, blueC, opacityC) = (redC, greenC, blueC, opacityC - 1)
Generalising. To keep matters simple, our implementation started with a constant angle and scale factor. Let's generalise this now. We can approach this in two ways. Firstly, we can pass the two additional arguments on to the recursive calls:
spiralRays :: Float -> Float -> Int -> Colour -> Line -> Picture spiralRays angle scaleFactor n colour line@(p1, p2) | n <= 0 =  | otherwise = (colour, [p1, p2]) : spiralRays angle scaleFactor (n - 1) newColour newLine where newColour = fade colour newLine = scaleLine scaleFactor (rotateLine angle line)
However, since these two parameters stay constant during the recursion, another, more elegant option, is to define a local function that performs the recursion and which doesn't explicitly pass the angle and scale factor as arguments:
spiralRays :: Float -> Float -> Int -> Colour -> Line -> Picture spiralRays angle scaleFactor n colour line = spiralRays' n colour line where spiralRays' n colour line@(p1, p2) | n <= 0 =  | otherwise = (colour, [p1, p2]) : spiralRays' (n-1) newColour newLine where newColour = fade colour newLine = scaleLine scaleFactor (rotateLine angle line)
By changing colour, angle, and scaling factor, we can generate many different pictures with this one recursive function.
The following screencast illustrates the use of the
spiralRays and will give you an idea of the possible variations.
The orange spiral at the beginning of the section was generated by modifying the calculation of the
newColour by calling the
fade function in the calculation of
newColour only on every third recursive step, where
mod calculates the remainder of division on integral numbers — i.e., we used
newColour = if (n `mod` 3 == 0) then fade colour else colour
All images so far used integer fractions of
pi for the rotation angle. By using other fractions, we can achieve a whole range of different effects:
You can add more interesting colour effects by replacing the
fade function with other colour manipulation operations — for example, one which gradually cycles through the colour spectrum. Or you can slowly increase or decrease the rotation angle - even with this simple function, we have a huge number of possibilities to produce all kind of interesting effects. The following screencasts demonstrates some colour effects by modifying
If we change our
spiralRay function, such that, instead of all lines having the same starting point, each lines starting point is the end point of the previous line, we get a spiral shaped path. To this end, we need another helper function,
connectLine. It takes two lines and moves the second line's starting point to the end point of the first, without changing the length or orientation of the line:
connectLine :: Line -> Line -> Line connectLine (_, pE) line2 = startLineFrom pE line2
Here we use a bit of new Haskell syntax: the underscore (
_) in the pattern for the first line is a so-called anonymous variable: since we don't use that component of the line, we don't need to come up with a name for it; instead, we can just call it
_. We can use anonymous variables repeatedly within the same pattern. In addition to the convenience, this notation also increases the readability of the code, as an anonymous variable signals to the reader that the result of the function does not depend on that part of the input.
connectLine defers the actual work to
startLineFrom (where we use an
startLineFrom :: Point -> Line -> Line startLineFrom startPoint@(x0, y0) ((xS, yS), (xE, yE)) = (startPoint, ((x0 + xE - xS, y0 + yE - yS)))
Now we already have everything in place to implement the new
spiral function. For now, it returns just a single
Path, not a
Picture, and hence, is independent of the colour choice:
spiral :: Float -> Float -> Int -> Line -> Path spiral angle scaleFactor n line = spiral' n line where spiral' n line@(p1, p2) | n <= 0 =  | otherwise = p1 : spiral' (n - 1) newLine where newLine = connectLine line (scaleLine scaleFactor (rotateLine angle line))
spiralRays, this function produces regular looking spirals for angles which are integer fractions of
It produces more chaotic patterns for other angles.
For a scaling factor of one (that is, the lines are all the same length) and angles that are integer fractions of
pi, the resulting path is simply a polygon, so we can define a polygon function in terms of
polygon :: Int -> Line -> Path polygon n line | n > 2 = spiral rotationAngle 1 (n + 1) line where rotationAngle = (2 * pi) / (fromIntegral n)
To generate even more varied spirals, we could generalise
spiral to change the angle in each recursive step by a given factor (instead of using a constant angle), or we could generate multi-coloured spirals. The latter change would require, though, that we pair each line as a path with a colour, instead of returning the spiral as one single path. The following screencasts illustrates a few of the possible variations.
Fractals are patterns which keeps repeating themselves in the same or similar forms. Fractal-like patterns can be found in nature, for example, the florets of cauliflower, or the leaves of a fern.
Koch-snowflakes (after the Swedish mathematician Helge von Koch) are one of the simplest examples of such patterns. They are constructed by starting from an equilateral triangle, and then, in each iteration, adding an equilateral triangle of a third of the size of the previous one the middle of each line, and then, removing the line that the new triangle and the base line share.
In pictures, we proceed as illustrated in the following display.
The third, fourth and fifth recursive step add triangle bumps to all
4 * 48, and
4 * 4 * 48 lines, respectively — as illustrated in the next three images.
As the size of each line is reduced by a third in each recursive step, we can hardly make out the individual lines anymore after five recursive steps.
It is apparent from the shape of the Koch snowflakes that the sequence of operations applied to each line in each recursive step is always the same. So, let's have a closer look at those operations. We start with a line from a point
pS to a point
We need to chop this line into three equal parts to get the base line of the equilateral triangle that we want to construct. Since we already implemented the function
scaleLine, we can use it to get the first base point of this triangle,
p1, which is the end point of the scaled line
l1. To get the third point of the small triangle, we can connect
l1 with itself, (or alternatively, we could have scaled the original line by two thirds).
Here, we use
@-patterns as well as anonymous variables to bind the lines to variables
l2, and at the same time extract the end points of both lines,
Now, all we need to do is to find the missing point of the new triangle, the “peak” of the triangle. Again, we can use a function that we already implemented, namely
rotateLine. We rotate the second line,
l2, clockwise by 5/6th of a full rotation (which corresponds to 5/3π radians).
The only component of the rotated line that we are interested in is the end point,
p2, which we extract by pattern matching.
Now we have got all the ingredients for implementing the recursive construction of one of the three parts of a Koch snowflake (each part corresponds to one line of the initial equilateral triangle).
kochLine :: Int -> Point -> Point -> Path kochLine n pS pE | n <= 0 =  | otherwise = [pS] ++ kochLine (n - 1) pS p1 ++ kochLine (n - 1) p1 p2 ++ kochLine (n - 1) p2 p3 ++ kochLine (n - 1) p3 pE ++ [pE] where l1@(_, p1) = scaleLine (1 / 3) (pS, pE) l2@(_, p3) = connectLine l1 l1 (_, p2) = rotateLine (5 / 3 * pi) $ l2
Note how we use pattern matching on the results of invoking the functions
rotateLine in the
where bindings. As long as we know that pattern matching is successful, we can use pattern matching in
where bindings in exactly the same way as we use it for function arguments. The three
where bindings of
kochLine produce the three points
p3 of the triangle that we need to impose on the line specified by the start and end points
pE passed as arguments to
kochLine — just as illustrated by the three diagrams in the preceding section. We, then, recursively use
kochLine on all four lines that we get from imposing one triangle bump on the line from
This use of recursion is interesting as it is our first function that recursively calls itself multiple times in a single recursive step. Specifically,
kochLine uses fourway recursion whereas we only defined singly recursive functions in Recursion.
To produce the complete snowflake, all that remains is to combine three Koch lines to get the entire Koch snowflake. To this end, we recycle the
polygon function to construct the initial equilateral triangle given the recursive depth and the base line:
kochFlake :: Int -> Line -> Path kochFlake n line = kochLine n p1 p2 ++ kochLine n p2 p3 ++ kochLine n p3 p1 where [p1, p2, p3, _] = polygon 3 line
We again decompose the result of
polygon using pattern matching in a
where binding. When testing the function, please be aware that the number of recursive calls grows very quickly: a recursive depth of n, leads to 3 * 4n invocations of
Just as we generated vaguely snowflake-like looking diagrams using recursion in the previous section, we are now going to generate plant-like shapes, called Pythagorean trees.
Can you guess the geometric pattern used to construct these trees? If not, consider the first steps of constructing the first of the three trees displayed above.
The tree consists of a sequences of squares, stacked onto each other. This results in a surprisingly soft, organic looking structure. The triangles formed by the red lines define a Pythagorean triple of squares: the area of the base square is the sum of the areas of the two squares added in the following iteration. The trees only differ in which triangle was used to calculate the size and orientation of the squares in each step.
We can construct right-angled triangles with a base line
b, by drawing a circle with centre
m right in the middle of that line, and radius that is the distance from
Any point on that circle forms a right angled triangle with
b. We can use this fact to calculate the coordinates of the points in our tree path.
We start building our tree given the base
line. First, we calculate the points of the square using the previously defined
polygon function. The last point is the same as the first, so we are not interested in it and bind it to the anonymous variable (
As next step, we need to construct a right angled triangle with hypotenuse
(p3, p4) — the hypotenuse is the longest side of the right angled triangle. We can do that by first scaling the line
(p3, p4) by
0.5, resulting in a line from
p3 to the middle of the line. To construct the circle, we flip the direction of that line (by swapping the end points around) with a new function
Now, we rotate the line
r by any angle between zero and Pi to get the third point of a right angled triangle. Here, we use
0.7 * pi, which happens to be the angle used to construct the first example tree.
(p4, p5) and
(p5, p3) then form the base lines for the next iteration of the recursive construction of the tree:
In our program, we don't want to hard code the rotation angle, and rather pass it in as parameter. Combining all these steps into a recursive function, we get
fractalTree :: Float -> Int -> Line -> Path fractalTree factor n line = fractalTree' n line where fractalTree' 0 line =  fractalTree' n line = [p1, p4] ++ fractalTree' (n-1) (p4, p5) ++ fractalTree' (n-1) (p5, p3) ++ [p3, p2] where -- flip direction of line flipLine :: Line -> Line flipLine (pS, pE) = (pE, pS) [p1,p2,p3,p4,_] = polygon 4 line r = flipLine (scaleLine 0.5 (p3, p4)) (_, p5) = rotateLine (factor * pi) r
The structure of this function is not unlike that of
kochLine with a bit of
kochFlake mixed in by way of using
polygon to get the corners of a polygon (although, we are using a square here and used a equilateral triangle in
fractalTree only is binary recursive —i.e., it contains two recursive calls— whereas
kochLine was four-way recursive.
If we pass
n equals one to
fractalTree, it returns the three upper lines of the square, as the recursive call with
n == 0 returns an empty path. The second and third example tree at the beginning of this section were generated with a variation of this function which changed the rotation factor to
1 - factor in every third and fifth iteration, respectively. The following screencast demonstrates how to achieve these variations in code.
There are many other possible variations — for example, using triangles that are not right-angled as the basis, cycling through a range of different factors, or adding colour effects. Here, to close this chapter, a small selection of these variations.
If you want to save yourself copying the code from this chapter in pieces, here is a version of the
Fractals module with all definitions that we discussed: Fractals.hs. Just copy its contents into the module with the same name in the Haskell project,
Fractals.hsproj, that you downloaded at the beginning of this chapter.
Implement a function
colouredFTree :: Float -> Int -> Colour -> Line -> Picture that elaborates on
fractalTree by accepting the colour of the tree as an additional argument.
colouredFTree by using the
fade function, which we discussed in the context of spiral rays, to incrementally alter the colour in each recursive step.
colouredFTree further by implementing and using
factor as demonstrated in the last screencast.