Build Your Own Turtle

Here's the Instruction type we defined in the previous section.

sealed abstract class Instruction extends Product with Serializable
final case class Forward(distance: Double) extends Instruction
final case class Turn(angle: Angle) extends Instruction
final case class Branch(instructions: List[Instruction]) extends Instruction
final case class NoOp() extends Instruction

Now we've defined our own Instruction type, let's go one further and create our own Turtle. To complete our turtle we need to implement draw. We can start with

object Turtle {
  def draw(instructions: List[Instruction]): Image =
    ???
}

Instruction is an algebraic data type, so we know we can use structural recursion to process it. However to do so we need to also store the current state of the turtle: it's location (a Vec) and heading (an Angle). Implement a type to hold this data.

<div class="solution"> This is a product type.

final case class TurtleState(at: Vec, heading: Angle)

</div>

When we process the instructions, we will turn them into a List[PathElement], which we can later wrap with an open path to create an Image. For each instruction, the conversion will be a function of the current turtle state and the instruction, and will returnan updated state and a List[PathElement].

Implement a method process to do this job with signature

def process(state: TurtleState, instruction: Instruction): (TurtleState, List[PathElement]) =
  ???

First implement this without branching instructions. We'll return to branches in a moment.

<div class="solution"> The core pattern is a structural recursion but the details are a bit more intricate in this case than we've seen before. We need to both create the path elements and update the state.

def process(state: TurtleState, instruction: Instruction): (TurtleState, List[PathElement]) = {
  import PathElement._
  
  instruction match {
    case Forward(d) =>
      val nowAt = state.at + Vec.polar(d, state.heading)
      val element = lineTo(nowAt.toPoint)

      (state.copy(at = nowAt), List(element))
    case Turn(a) =>
      val nowHeading = state.heading + a

      (state.copy(heading = nowHeading), List())
    case Branch(i) =>
      // Ignoring for now
      (state, List())
    case NoOp() =>
      (state, List())
  }
}

</div>

Now using process write a structural recursion over List[Instruction] that converts the instructions to a List[PathElement]. Call this method iterate with signature

def iterate(state: TurtleState, instructions: List[Instruction]): List[PathElement] =
  ???

<div class="solution">

def iterate(state: TurtleState, instructions: List[Instruction]): List[PathElement] =
  instructions match {
    case Nil => 
      Nil
    case i :: is =>
      val (newState, elements) = process(state, i)
      elements ++ iterate(newState, is)
  }

</div>

Now add branching to process, using iterate as a utility.

<div class="function">

def process(state: TurtleState, instruction: Instruction): (TurtleState, List[PathElement]) = {
  import PathElement._
  
  instruction match {
    case Forward(d) =>
      val nowAt = state.at + Vec.polar(d, state.heading)
      val element = lineTo(nowAt.toPoint)

      (state.copy(at = nowAt), List(element))
    case Turn(a) =>
      val nowHeading = state.heading + a

      (state.copy(heading = nowHeading), List())
    case Branch(is) =>
     val branchedElements = iterate(state, is)
     
     (state, moveTo(state.at.toPoint) :: branchedElements)
    case NoOp() =>
      (state, List())
  }
}

</div>

Now implement draw using iterate.

<div class="solution"> Here's the complete turtle.

object Turtle {
  import Image._

  def draw(instructions: List[Instruction]): Image = {
    def iterate(state: TurtleState, instructions: List[Instruction]): List[PathElement] =
      instructions match {
        case Nil => 
          Nil
        case i :: is =>
          val (newState, elements) = process(state, i)
          elements ++ iterate(newState, is)
      }

    def process(state: TurtleState, instruction: Instruction): (TurtleState, List[PathElement]) = {
      import PathElement._
      
      instruction match {
        case Forward(d) =>
          val nowAt = state.at + Vec.polar(d, state.heading)
          val element = lineTo(nowAt.toPoint)
    
          (state.copy(at = nowAt), List(element))
        case Turn(a) =>
          val nowHeading = state.heading + a
    
          (state.copy(heading = nowHeading), List())
        case Branch(is) =>
         val branchedElements = iterate(state, is)
         
         (state, moveTo(state.at.toPoint) :: branchedElements)
        case NoOp() =>
          (state, List())
      }
    }
    
    path(OpenPath(iterate(TurtleState(Vec.zero, Angle.zero), instructions)))
  }
}

</div>

Extensions

Turtles that can make random choices can lead to more organic images. Can you implement this?