Working with Lists

At this point you might be thinking it would be nice to create a method to draw polygons rather than constructing each one by hand. There is clearly a repeating pattern to their construction and we would be able to generalise this pattern if we knew how to create a list of arbitrary size. It's time we learned more about building and manipulating lists.

The Recursive Structure of Lists

You'll recall when we introduced structural recursion over the natural numbers we said we could transform their recursive structure into any other recursive structure. We demonstrated this for concentric circles and a variety of other patterns.

Lists have a recursive structure, and one that is very similar to the structure of the natural numbers. A List is

the empty list Nil; or
a pair of an element a and a List, written a :: tail, where tail is the rest of the list.

For example, we can write out the list List(1, 2, 3, 4) in its "long" form as

1 :: 2 :: 3 :: 4 :: Nil
// res0: List[Int] = List(1, 2, 3, 4)

Notice the similarity to the natural numbers. Earlier we noted we can expand the structure of a natural number so we could write, say, 3 as 1 + 1 + 1 + 0. If we replace + with :: and 0 with Nil we get the List 1 :: 1 :: 1 :: Nil.

What does this mean? It means we can easily transform a natural number into a List using our familiar tool of structural recursionFootnote free-monoid. Here's a very simple example, which given a number builds a list of that length containing the String "Hi".

def sayHi(length: Int): List[String] =
  length match {
    case 0 => Nil
    case n => "Hi" :: sayHi(n - 1)
  }

sayHi(5)
// res1: List[String] = List("Hi", "Hi", "Hi", "Hi", "Hi")

The code here is transforming:

0 to Nil, for the base case; and

n (which, remember, we think of as 1 + m) to "Hi" :: sayHi(n - 1), transforming 1 to "Hi", + to ::, and recursing as usual on m (which is n - 1).

[free-monoid]

This connection goes deeper. We can abstract the idea of things that can be "added" into a concept called a monoid, and a list represents a particular type of monoid called the free monoid. We aren't going to work with this abstraction in Creative Scala but you're encouraged to explore on your own!

This recursive structure also means we can transform lists into other recursive structures, such a natural number, different lists, chessboards, and so on. Here we increment every element in a list---that is, transform a list to a list---using structural recursion.

def increment(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd + 1) :: increment(tl)
  }

increment(List(1, 2, 3))
// res2: List[Int] = List(2, 3, 4)

Here we sum the elements of a list of integers---that is, transform a list to a natural number---using structural recursion.

def sum(list: List[Int]): Int =
  list match {
    case Nil => 0
    case hd :: tl => hd + sum(tl)
  }

sum(List(1, 2, 3))
// res3: Int = 6

Notice when we take a List apart with pattern matching we use the same hd :: tl syntax we use when we construct it. This is an intentional symmetry.

Type Variables

What about finding the length of a list? We know we can use our standard tool of structural recursion to write the method. Here's the code to calculate the length of a List[Int].

def length(list: List[Int]): Int =
  list match {
    case Nil => 0
    case hd :: tl => 1 + length(tl)
  }

Note that we don't do anything with the elements of the list---we don't really care about their type. Using the same code skeleton can just as easily calculate the length of a List[Int] as a List[HairyYak] but we don't currently know how to write down the type of a list where we don't care about the type of the elements.

Scala lets us write methods that can work with any type, by using what is called a type variable. A type variable is written in square brackets like [A] and comes after the method name and before the parameter list. A type variable can stand in for any specific type, and we can use it in the parameter list or result type to indicate some type that we don't know up front. For example, here's how we can write length so it works with lists of any type.

def length[A](list: List[A]): Int =
  list match {
    case Nil => 0
    case hd :: tl => 1 + length(tl)
  }

Structural Recursion over a List {-}

A List of elements of type A is:

the empty list Nil; or
an element a of type A and a tail of type List[A]: a :: tail

The structural recursion skeleton for transforming list of type List[A] to some type B has shape

def doSomething[A,B](list: List[A]): B =
  list match {
    case Nil => ??? // Base case of type B here
    case hd :: tl => f(hd, doSomething(tl))
  }

where f is a problem specific method combining hd and the result of the recursive call to produce something of type B. </div>

Exercises {-}

Building Lists {-}

In these exercises we get some experience constructing lists using structural recursion on the natural numbers.

Write a method called ones that accepts an Int n and returns a List[Int] with length n and every element 1. For example

ones(3)
// res5: List[Int] = List(1, 1, 1)

<div class="solution"> It's structural recursion over the natural numbers!

def ones(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => 1 :: ones(n - 1)
  }

ones(3)
// res7: List[Int] = List(1, 1, 1)

</div>

Write a method descending that accepts an natural number n and returns a List[Int] containing the natural numbers from n to 1 or the empty list if n is zero. For example

descending(0)
// res8: List[Int] = List()
descending(3)
// res9: List[Int] = List(3, 2, 1)

<div class="solution"> Once more, we can employ structural recursion over the natural numbers.

def descending(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => n :: descending(n - 1)
  }

descending(0)
// res11: List[Int] = List()
descending(3)
// res12: List[Int] = List(3, 2, 1)

</div>

Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero.

ascending(0)
// res13: List[Int] = List()
ascending(3)
// res14: List[Int] = List(1, 2, 3)

<div class="solution"> It's structural recursion over the natural numbers, but this time with an internal accumulator.

def ascending(n: Int): List[Int] = {
  def iter(n: Int, counter: Int): List[Int] =
    n match {
      case 0 => Nil
      case n => counter :: iter(n - 1, counter + 1)
    }

  iter(n, 1)
}

ascending(0)
// res16: List[Int] = List()
ascending(3)
// res17: List[Int] = List(1, 2, 3)

</div>

Create a method fill that accepts a natural number n and an element a of type A and constructs a list of length n where all elements are a.

fill(3, "Hi")
// res18: List[String] = List("Hi", "Hi", "Hi")
fill(3, Color.blue)
// res19: List[Color] = List(
//   RGBA(
//     r = UnsignedByte(value = -128),
//     g = UnsignedByte(value = -128),
//     b = UnsignedByte(value = 127),
//     a = Normalized(get = 1.0)
//   ),
//   RGBA(
//     r = UnsignedByte(value = -128),
//     g = UnsignedByte(value = -128),
//     b = UnsignedByte(value = 127),
//     a = Normalized(get = 1.0)
//   ),
//   RGBA(
//     r = UnsignedByte(value = -128),
//     g = UnsignedByte(value = -128),
//     b = UnsignedByte(value = 127),
//     a = Normalized(get = 1.0)
//   )
// )

<div class="solution"> In this exercise we're asking you to use a type variable. Otherwise it is the same pattern as before.

def fill[A](n: Int, a: A): List[A] =
  n match {
    case 0 => Nil
    case n => a :: fill(n-1, a)
  }

fill(3, "Hi")
// res21: List[String] = List("Hi", "Hi", "Hi")
fill(3, Color.blue)
// res22: List[Color] = List(
//   RGBA(
//     r = UnsignedByte(value = -128),
//     g = UnsignedByte(value = -128),
//     b = UnsignedByte(value = 127),
//     a = Normalized(get = 1.0)
//   ),
//   RGBA(
//     r = UnsignedByte(value = -128),
//     g = UnsignedByte(value = -128),
//     b = UnsignedByte(value = 127),
//     a = Normalized(get = 1.0)
//   ),
//   RGBA(
//     r = UnsignedByte(value = -128),
//     g = UnsignedByte(value = -128),
//     b = UnsignedByte(value = 127),
//     a = Normalized(get = 1.0)
//   )
// )

</div>

Transforming Lists {-}

In these exercises we practice the other side of list manipulation---transforming lists into elements of other types (and sometimes, into different lists).

Write a method double that accepts a List[Int] and returns a list with each element doubled.

double(List(1, 2, 3))
// res23: List[Int] = List(2, 4, 6)
double(List(4, 9, 16))
// res24: List[Int] = List(8, 18, 32)

<div class="solution"> This is a structural recursion over a list, building a list at each step. The destructuring of the input is mirrored by the construction of the output.

def double(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd * 2) :: double(tl)
  }

double(List(1, 2, 3))
// res26: List[Int] = List(2, 4, 6)
double(List(4, 9, 16))
// res27: List[Int] = List(8, 18, 32)

</div>

Write a method product that accepts a List[Int] and calculates the product of all the elements.

product(Nil)
// res28: Int = 1
product(List(1,2,3))
// res29: Int = 6

<div class="solution"> This is a structural recursion over a list using the same pattern as sum in the examples above.

def product(list: List[Int]): Int =
  list match {
    case Nil => 1
    case hd :: tl => hd * product(tl)
  }

product(Nil)
// res31: Int = 1
product(List(1,2,3))
// res32: Int = 6

</div>

Write a method contains that accepts a List[A] and an element of type A and returns true if the list contains the element and false otherwise.

contains(List(1,2,3), 3)
// res33: Boolean = true
contains(List("one", "two", "three"), "four")
// res34: Boolean = false

<div class="solution"> Same pattern as before, but using a type variable to allow type of the elements to vary.

def contains[A](list: List[A], elt: A): Boolean =
  list match {
    case Nil => false
    case hd :: tl => (hd == elt) || contains(tl, elt)
  }

contains(List(1,2,3), 3)
// res36: Boolean = true
contains(List("one", "two", "three"), "four")
// res37: Boolean = false

</div>

Write a method first that accepts a List[A] and an element of type A and returns the first element of the list if it is not empty and otherwise returns the element of type A passed as a aprameter.

first(Nil, 4)
// res38: Int = 4
first(List(1,2,3), 4)
// res39: Int = 1

<div class="solution"> This method is similar to contains above, except we now use the type variable in the return type as well as in the parameter types.

def first[A](list: List[A], elt: A): A =
  list match {
    case Nil => elt
    case hd :: tl => hd
  }

first(Nil, 4)
// res41: Int = 4
first(List(1,2,3), 4)
// res42: Int = 1

</div>

Challenge Exercise: Reverse {-}

Write a method reverse that accepts a List[A] and reverses the list.

reverse(List(1, 2, 3))
// res43: List[Int] = List(3, 2, 1)
reverse(List("a", "b", "c"))
// res44: List[String] = List("c", "b", "a")

<div class="solution"> The trick here is to use an accumulator to hold the partially reversed list. If you managed to work this one out, congratulations---you really understand structural recursion well!

def reverse[A](list: List[A]): List[A] = {
  def iter(list: List[A], reversed: List[A]): List[A] =
    list match {
      case Nil => reversed
      case hd :: tl => iter(tl, hd :: reversed)
    }

  iter(list, Nil)
}

reverse(List(1, 2, 3))
// res46: List[Int] = List(3, 2, 1)
reverse(List("a", "b", "c"))
// res47: List[String] = List("c", "b", "a")

</div>

Polygons! {-}

At last, let's return to our example of drawing polygons. Write a method polygon that accepts the number of sides of the polygon and the starting rotation and produces a Image representing the specified regular polygon. Hint: use an internal accumulator.

Use this utility to create an interesting picture combining polygons. Our rather unimaginative example is in Figure sequences:concentric-polygons. We're sure you can do better.

Concentric polygons with pastel gradient fill.

<div class="solution"> Here's our code. Note how we factored the code into small components---though we could have taken the factoring further is we wanted to. (Can you see how? Hint: do we need to pass, say, start to every call of makeColor when it's not changing?)

import Point._
import PathElement._

def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
  def iter(n: Int, rotation: Angle): List[PathElement] =
    n match {
      case 0 =>
        Nil
      case n =>
        LineTo(polar(size, rotation * n + initialRotation)) :: iter(n - 1, rotation)
    }
  Image.path(ClosedPath(moveTo(polar(size, initialRotation)) :: iter(sides, 360.degrees / sides)))
}

def style(img: Image): Image = {
  img.
    strokeWidth(3.0).
    strokeColor(Color.mediumVioletRed).
    fillColor(Color.paleVioletRed.fadeOut(0.5.normalized))
}

def makeShape(n: Int, increment: Int): Image =
    polygon(n+2, n * increment, 0.degrees)

def makeColor(n: Int, spin: Angle, start: Color): Color =
  start.spin(spin * n)

val baseColor = Color.hsl(0.degrees, 0.7, 0.7)

def makeImage(n: Int): Image = {
  n match {
    case 0 =>
      Image.empty
    case n =>
      val shape = makeShape(n, 10)
      val color = makeColor(n, 30.degrees, baseColor)
      makeImage(n-1).on(shape.fillColor(color))
  }
}

val image = makeImage(15)

</div>

←Shapes, Sequences, and Stars My God, It's Full of Stars!→