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))
//     )
//   )
// )

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:

• an initial seed to start the growth; and
• rewrite rules, which specify how the growth occurs.

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:

• each straight line doubles in size; and
• a bud (the diamond at the end of a line) grows into two branches that end with buds.

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

• Forward(distance), where distance is a Double;
• Turn(angle), where angle is an Angle;
• NoOp; and
• Branch(instructions), where instructions is a List[Instruction].

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].

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:

• recognising how to use flatMap; and
• remembering how to use type variables.

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:

• recognising that we need to use flatMap, for reasons discussed above; and
• realising that we need to recursively call rewrite to process the contents of a branch.

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.