Branching Structures

<div class="callout callout-info"> In addition to the standard imports given at the start of the chapter, in this section we're assuming the following:

import doodle.turtle._
import doodle.turtle.Instruction._

</div>

Using the branch turtle instruction we can explore some shapes that are difficult to create without it. The branch instruction takes a List[Instruction]. It saves the current state of the turtle (it's location and heading), draws the given instructions, and returns the turtle to the saved state.

Consider the code below, which creates the image in Figure turtles:y. This is easy to draw with a branching turtle, but quite involved to create with just a path.

val y = Turtle.draw(List(
          forward(100),
          branch(turn(45.degrees), forward(100)),
          branch(turn(-45.degrees), forward(100)))
        )
// y: Image = OpenPath(
//   path = OpenPath(
//     reversed = List(
//       MoveTo(to = Cartesian(x = 100.0, y = 0.0)),
//       LineTo(to = Cartesian(x = 170.71067811865476, y = -70.71067811865474)),
//       MoveTo(to = Cartesian(x = 100.0, y = 0.0)),
//       LineTo(to = Cartesian(x = 170.71067811865476, y = 70.71067811865474)),
//       LineTo(to = Cartesian(x = 100.0, y = 0.0)),
//       MoveTo(to = Cartesian(x = 0.0, y = 0.0))
//     )
//   )
// )

An image that is easy to create with a branching turtle, and comparatively difficult to create without.

Using branching we can model some forms of biological growth, producing, for example, images of plants as in Figure turtles:plant. One particular model is known as an L-system. An L-system has consists of two parts:

A specific example of this process is shown in Figure turtles:branches. The figure on the left hand side is the seed. The rewrite rules are:

Modelling the growth of a plant using rewrite rules.

Concretely, we can write these rules as a transformation on Instruction assuming that we use NoOp to represent a bud.

val stepSize = 10
// stepSize: Int = 10

def rule(i: Instruction): List[Instruction] =
  i match {
    case Forward(_) => List(forward(stepSize), forward(stepSize))
    case NoOp => 
      List(branch(turn(45.degrees), forward(stepSize), noop), 
           branch(turn(-45.degrees), forward(stepSize), noop))
    case other => List(other)
  }

Note how we used pattern matching on Instruction, like we have on the other algebraic data types---natural numbers and List---we've seen so far. By importing doodle.turtle.Instruction._ we can access all the patterns for Instruction, which are

As a function, rule has type Instruction => List[Instruction], as we're potentially transforming each instruction into several instructions (as we do in the case of Forward). Now how can we actually apply this rule to a List[Instruction] to create a List[Instruction] (for example, applying it to List[noop])? Can we use map?

<div class="solution"> In this case map is not the right solution, as the types tell us. Remember the type equation for map is

List[A] map (A => B) = List[B]

If - we have List[Instruction]; and - we map a function Instruction => List[Instruction]; then - we'll get a List[List[Instruction]]

as we can see from the type equation.

Our turtle doesn't know how to draw List[List[Instruction]] so this won't work. </div>

There is a method flatten on List, which will convert a List[List[A]] to List[A]. We could use a combination of map and flatten but we have a better solution. This pattern comes up enough---and in different contexts which we'll see later---that there is a method just to handle it. The method is called flatMap.

The type equation for flatMap is

List[A] flatMap (A => List[B]) = List[B]

and this is illustrated graphically in Figure turtles:flatMap. We can see that flatMap has the right type to combine rule with List[Instruction] to create a rewritten List[Instruction].

The type equation for flatMap illustrated graphically.

When discussing map we said that it doesn't allow us to change the number of elements in the List. Graphically, we can't create a new "box" using map. With flatMap we can change the box, in the case lists meaning we can change the number of elements in the list.

Exercises {-}

Double {-}

Using flatMap, write a method double that transforms a List to a List where every element appears twice. For example

double(List(1, 2, 3))
// res0: List[Int] = List(1, 1, 2, 2, 3, 3)
double(List("do", "ray", "me"))
// res1: List[String] = List("do", "do", "ray", "ray", "me", "me")

<div class="solution"> There are two points to this:

def double[A](in: List[A]): List[A] =
  in.flatMap { x => List(x, x) }

</div>

Or Nothing {-}

Using flatMap, write a method nothing that transforms a List to the empty List. For example

nothing(List(1, 2, 3))
// res3: List[Int] = List()
nothing(List("do", "ray", "me"))
// res4: List[String] = List()

<div class="solution"> We could easily write this method as

def nothing[A](in: List[A]): List[A] =
  List() // or List.empty or Nil

but the point of this exercise is to get more familiarity with using flatMap. With flatMap we can write the method as

def nothing[A](in: List[A]): List[A] =
  in.flatMap { x => List.empty }

</div>

Rewriting the Rules {-}

Write a method rewrite with signature

def rewrite(instructions: List[Instruction], 
            rule: Instruction => List[Instruction]): List[Instruction] =
  ???

This method should apply rule to rewrite every instruction in instructions, except for branches which you'll need to handle specially. If you encounter a branch you should rewrite all the instructions inside the branch but leave the branch alone.

Note: You'll need to pass a List[Instruction] to branch, while branch itself accepts zero or more instructions (so-called varargs). To convert the List[Instruction] into a form that branch will accept, follow the parameter with :_* like so

val instructions = List(turn(45.degrees), forward(10))
// instructions: List[Instruction] = List(
//   Turn(angle = Angle(0.7853981633974483)),
//   Forward(distance = 10.0)
// )
branch(instructions:_*)
// res8: Branch = Branch(
//   instructions = List(
//     Turn(angle = Angle(0.7853981633974483)),
//     Forward(distance = 10.0)
//   )
// )

<div class="solution"> There are two parts to this:

The latter is an example of structural recursion, though a slighlty more complex pattern than we've seen before.

def rewrite(instructions: List[Instruction], rule: Instruction => List[Instruction]): List[Instruction] =
  instructions.flatMap { i =>
    i match {
      case Branch(i) =>
        List(branch(rewrite(i, rule):_*))
      case other =>
        rule(other)
    }
  }

</div>

Your Own L-System {-}

We're now ready to create a complete L-system. Using rewrite from above, create a method iterate with signature

def iterate(steps: Int,
            seed: List[Instruction], 
            rule: Instruction => List[Instruction]): List[Instruction] =
  ???

This should recursively apply rule to seed for steps iterations.

<div class="solution"> This is just a simple structural recursion of the natural numbers, with all the hard work done by rewrite.

def iterate(steps: Int, 
            seed: List[Instruction], 
            rule: Instruction => List[Instruction]): List[Instruction] =
  steps match {
    case 0 => seed
    case n => iterate(n - 1, rewrite(seed, rule), rule)
  }

</div>

Plants and Other Creations {-}

Create the pictures shown in Figure turtles:branching and Figure turtles-koch-curve using your L-system implementation.

Five iterations of the simple branching L-system.

Five iterations of the Koch curve, a fractal that is simple to create with an L-System.