# Transforming Sequences

We've seen that using structural recursion we can create and transform lists. This pattern is simple to use and to understand, but it requires we write the same skeleton time and again. In this section we'll learn that we can replace structural recursion in some cases by using a method on `List` called `map`. We'll also see that other useful datatypes provide this method and we can use it as a common interface for manipulating sequences.

### Transforming the Elements of a List

In the previous section we saw several examples where we transformed one list to another. For example, we incremented the elements of a list with the following code.

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

increment(List(1, 2, 3))
// res0: List[Int] = List(2, 2, 3)``````

In this example the structure of the list doesn't change. If we start with three elements we end with three elements. We can abstract this pattern in a method called `map`. If we have a list with elements of type `A`, we pass `map` a function of type `A => B` and we get back a list with elements of type `B`. For example, we can implement `increment` using `map` with the function `x => x + 1`.

``````def increment(list: List[Int]): List[Int] =
list.map(x => x + 1)

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

Each element is transformed by the function we pass to `map`, in this case `x => x + 1`. With `map` we can transform the elements, but we cannot change the number of elements in the list.

We find a graphical notation helps with understanding `map`. If we had some type `Circle` we can draw a `List[Circle]` as a box containing a circle, as shown in Figure sequences:circle-box. Now we can draw an equation for `map` as in Figure sequences:map. If you prefer symbols instead of pictures, the picture is showing that `List[Circle].map(Circle => Triangle) = List[Triangle]`. One feature of the graphical representation is it nicely illustrates that `map` cannot create a new "box", which represents the structure of the list---or more concretely the number of elements and their order. The graphical drawing of `map` exactly illustrates what holds at the type level for `map`. If we prefer we can write it down symbolically:

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

The left hand side of the equation has the type of the list we map and the function we use to do the mapping. The right hand is the type of the result. We can perform algebra with this representation, substituting in concrete types from our program.

### Transforming Sequences of Numbers

We have also written a lot of methods that transform a natural number to a list. We briefly discussed how we can represent a natural number as a list. `3` is equivalent to `1 + 1 + 1 + 0`, which in turn we could represent as `List(1, 1, 1)`. So what? Well, it means we could write a lot of the methods that accepts natural numbers as methods that worked on lists.

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

fill(3, "Hi")
// res3: List[String] = List("Hi", "Hi", "Hi")``````

we could write

``````def fill[A](n: List[Int], a: A): List[A] =
n.map(x => a)

fill(List(1, 1, 1), "Hi")
// res5: List[String] = List("Hi", "Hi", "Hi")``````

The implementation of this version of `fill` is more convenient to write, but it is much less convenient for the user to call it with `List(1, 1, ,1)` than just writing `3`.

If we want to work with sequences of numbers we are better off using `Ranges`. We can create these using the `until` method of `Int`.

``````0 until 10
// res6: Range = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)``````

`Ranges` have a `by` method that allows us to change the step between consecutive elements of the range:

``````0 until 10 by 2
// res7: Range = Range(0, 2, 4, 6, 8)``````

`Ranges` also have a `map` method just like `List`

``````(0 until 3) map (x => x + 1)
// res8: IndexedSeq[Int] = Vector(1, 2, 3)``````

You'll notice the result has type `IndexedSeq` and is implemented as a `Vector`---two types we haven't seen yet. We can treat an `IndexedSeq` much like a `List`, but for simplicity we can convert a `Range` or an `IndexedSeq` to a `List` using the `toList` method.

``````(0 until 7).toList
// res9: List[Int] = List(0, 1, 2, 3, 4, 5, 6)
(0 until 3).map(x => x + 1).toList
// res10: List[Int] = List(1, 2, 3)``````

With `Ranges` in our toolbox we can write `fill` as

``````def fill[A](n: Int, a: A): List[A] =
(0 until n).toList.map(x => a)

fill(3, "Hi")
// res12: List[String] = List("Hi", "Hi", "Hi")``````

### Ranges over Doubles

If we try to create a `Range` over `Double` we get an error.

``````0.0 to 10.0 by 1.0
// error:
// value to is not a member of Double
// def ascending(n: Int): List[Int] =
//    ^
// error:
// Line is indented too far to the left, or a `}` is missing
// error:
// Line is indented too far to the left, or a `}` is missing
// error:
// Line is indented too far to the left, or a `}` is missing
// error:
// Line is indented too far to the left, or a `}` is missing
// error:
// Line is indented too far to the left, or a `}` is missing
// def double(list: List[Int]): List[Int] =
//                                         ^
// error:
// Line is indented too far to the left, or a `}` is missing
//
// ^``````

There are two ways around this. We can use an equivalent `Range` over `Int`. In this case we could just write

``0 to 10 by 1``

We can use the `.toInt` method to convert a `Double` to an `Int` if needed.

Alternatively we can write a `Range` using `BigDecimal`.

``````import scala.math.BigDecimal
BigDecimal(0.0) to 10.0 by 1.0``````

`BigDecimal` has methods `doubleValue` and `intValue` to get `Double` and `Int` values respectively.

``````BigDecimal(10.0).doubleValue()
// res16: Double = 10.0
BigDecimal(10.0).intValue()
// res17: Int = 10``````

#### Exercises {-}

##### Ranges, Lists, and map {-}

Using our new tools, reimplement the following methods.

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

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

<div class="solution"> We can just `map` over a `Range` to achieve this.

``````def ones(n: Int): List[Int] =
(0 until n).toList.map(x => 1)

ones(3)
// res20: 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)
// res21: List[Int] = List()
descending(3)
// res22: List[Int] = List(3, 2, 1)``````

<div class="solution"> We can use a `Range` but we have to set the step size or the range will be empty.

``````def descending(n: Int): List[Int] =
(n until 0 by -1).toList

descending(0)
// res24: List[Int] = List()
descending(3)
// res25: 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)
// res26: List[Int] = List()
ascending(3)
// res27: List[Int] = List(1, 2, 3)``````

<div class="solution"> Again we can use a `Range` but we need to take care to start at `0` and increment the elements by `1` so we have the correct number of elements.

``````def ascending(n: Int): List[Int] =
(0 until n).toList.map(x => x + 1)

ascending(0)
// res29: List[Int] = List()
ascending(3)
// res30: List[Int] = List(1, 2, 3)``````

</div>

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

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

<div class="solution"> This is a straightforward application of `map`.

``````def double(list: List[Int]): List[Int] =
list map (x => x * 2)

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

</div>

##### Polygons, Again! {-}

Using our new tools, rewrite the `polygon` method from the previous section.

<div class="solution"> Here's one possible implementation. Much easier to read than the previous implementation!

``````def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
import Point._
import PathElement._

val step = (Angle.one / sides).toDegrees.toInt
val path =
(0 to 360 by step).toList.map{ deg =>
lineTo(polar(size, initialRotation + deg.degrees))
}

Image.closedPath(moveTo(polar(size, initialRotation)) :: path)
}``````

</div>

##### Challenge Exercise: Beyond Map {-}

Can we use `map` to replace all uses of structural recursion? If not, can you characterise the problems that we can't implement with `map` but can implement with general structural recursion over lists?

<div class="solution"> We've seen many examples that we cannot implement with `map`: the methods `product`, `sum`, `find`, and more in the previous section cannot be implemented with `map`.

In abstract, methods implemented with map obey the following equation:

``List[A] map A => B = List[B]``

If the result is not of type `List[B]` we cannot implement it with `map`. For example, methods like `product` and `sum` transform `List[Int]` to `Int` and so cannot be implemented with `map`.

`Map` transforms the elements of a list, but cannot change the number of elements in the result. Even if a method fits the equation for `map` above it cannot be implemented with `map` if it requires changing the number of elements in the list. </div>

### Tools with Ranges

We've seen the `until` method to construct `Ranges`, and the `by` method to change the increment in a `Range`. There is one more method that will be useful to know about: `to`. This constructs a `Range` like `until` but the `Range` includes the endpoint. Compare

``````1 until 5
// res37: Range = Range(1, 2, 3, 4)
1 to 5
// res38: Inclusive = Range(1, 2, 3, 4, 5)``````

In technical terms, the `Range` constructed with `until` is a half-open interval, while the range constructed with `to` is an open interval.

#### Exercises {-}

##### Using Open Intervals {-}

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. Hint: use `to`

``````ascending(0)
// res39: List[Int] = List()
ascending(3)
// res40: List[Int] = List(1, 2, 3)``````

<div class="solution"> Now that we now about `to` this is trivial to implement.

``````def ascending(n: Int): List[Int] =
(1 to n).toList

ascending(0)
// res42: List[Int] = List()
ascending(3)
// res43: List[Int] = List(1, 2, 3)``````

</div>

My God, It's Full of Stars!→