The programmer that controls the `traverse`, controls the code.

class: center, middle

# The programmer that controls the `traverse`, controls the code.

Scala Matsuri 2023 2023/04/15<br>
@gakuzzzz

<div class="translation">
    traverse を制する者はコードを制す
</div>

---
class: left, top

## Who am I

* Manabu NAKAMURA
* Twitter: [@gakuzzzz](https://twitter.com/gakuzzzz)
* Tech to Value Co.,Ltd. CEO
* Alp, Inc. Tech Lead

<div class="translation">
    自己紹介: 中村 学 / Twitter: @gakuzzzz<br/>
    株式会社Tech to Value 代表 / アルプ株式会社 テックリード
</div>
    
---
class: left, top

## Note

The Scala code in this slide uses version 3.2.2.

It uses [cats](https://typelevel.org/cats/) and assumes that the following imports have been written for all sample code.

```Scala
import cats._
import cats.data._
import cats.syntax.all._
```

<div class="translation">
    このスライドにおける Scala コードは version 3.2.2 を利用しています。<br/>
    また cats を利用しており、全てのサンプルコードには上記 import が行われている前提です。
</div>

---
class: left, top

## the Iterator pattern

Loops are an important component of programs.

<div class="translation">
    プログラムを構成する重要な要素としてループがあります。
</div>

---
class: left, top

## the Iterator pattern

Loops are an important component of programs.

Among them, loop processing to iterate over data structures such as collections is frequently used.

<div class="translation">
    中でもコレクションなどのデータ構造に対し<br>その要素をイテレートするループ処理は頻出します。
</div>

---
class: left, top

## the Iterator pattern

Loops are an important component of programs.

Among them, loop processing to iterate over data structures such as collections is frequently used.

It is patterned as the Iterator pattern in the GoF design patterns (Gamma et al., 1995).

<div class="translation">
    GoFのデザインパターンにおいてもイテレータパターンとしてパターン化されています。
</div>

---
class: left, top

## the Iterator pattern

Nowadays, many major languages have a special syntax for the Iterator pattern.

```typescript
// JavaScript / TypeScript
const list = [1, 2, 3, 4, 5];
for (const value of list) {
    console.log(value);
}
```

<div class="translation">
    多くのメジャーな言語でイテレータパターンを特別扱いした構文が用意されています。
</div>

---
class: left, top

## the Iterator pattern

Nowadays, many major languages have a special syntax for the Iterator pattern.

```java17
// Java
var list = List.of(1, 2, 3, 4, 5);
for (var value : list) {
    System.out.println(value);
}
```

<div class="translation">
    多くのメジャーな言語でイテレータパターンを特別扱いした構文が用意されています。
</div>

---
class: left, top

## the Iterator pattern

Nowadays, many major languages have a special syntax for the Iterator pattern.

```python
# Python
list = [1, 2, 3, 4, 5]
for value in list:
    println(value)
```

<div class="translation">
    多くのメジャーな言語でイテレータパターンを特別扱いした構文が用意されています。
</div>

---
class: left, top

## Higher order functions

On the other hand, many major languages now support higher-order functions.

<div class="translation">
    一方、現在のメジャーな言語の多くでは高階関数がサポートされるようになり、
</div>

---
class: left, top

## Higher order functions

On the other hand, many major languages now support higher-order functions.

For simple iterations, it is common to use higher-order functions such as `map` and `filter`.

<div class="translation">
    単純なイテレーションに関しては map や filter といった<br>高階関数が使われる事も一般的になってきました。
</div>

---
class: left, top

## Higher order functions

On the other hand, many major languages now support higher-order functions.

For simple iterations, it is common to use higher-order functions such as `map` and `filter`.

```typescript
// JavaScript / TypeScript
const list   = [1, 2, 3, 4, 5];
const result = list.map(i => i * 2);
```

<div class="translation">
    単純なイテレーションに関しては map や filter といった<br>高階関数が使われる事も一般的になってきました。
</div>

---
class: left, top

## Higher order functions

On the other hand, many major languages now support higher-order functions.

For simple iterations, it is common to use higher-order functions such as `map` and `filter`.

```java17
// Java
var list   = List.of(1, 2, 3, 4, 5);
var result = list.stream().map(x -> x * 2).toList();
```

<div class="translation">
    単純なイテレーションに関しては map や filter といった<br>高階関数が使われる事も一般的になってきました。
</div>

---
class: left, top

## Higher order functions

On the other hand, many major languages now support higher-order functions.

For simple iterations, it is common to use higher-order functions such as `map` and `filter`.

```python
# Python
list   = [1, 2, 3, 4, 5]
result = list(map(lambda i: i * 2, list))
```

<div class="translation">
    単純なイテレーションに関しては map や filter といった<br>高階関数が使われる事も一般的になってきました。
</div>

---
class: left, top

## Complex Iteration

However, there are still many situations where the loop syntax is used for complex iterations.

<div class="translation">
    しかしながら、複雑なイテレーションについては<br>
    まだループ構文が使われる状況が多い様です。
</div>

---
class: left, top

## Complex Iteration

However, there are still many situations where the loop syntax is used for complex iterations.

for example: Using `break`, Depending previous and next elements, Returning multiple results.

<div class="translation">
  break が必要だったり、前後の要素に依存したり、<br>
  複数の値を返す必要があったりなど
</div>

---
class: left, top

## Complex Iteration

Such loops are difficult to write tests, and are difficult to tune the performance by using parallel loops.

<div class="translation">
    こういったループはそのままではテストが書きづらかったり<br>並列ループによる高速化が難しかったりします。
</div>

---
class: left, top

## the `traverse`

In fact, there is a higher-order function that can express all of the same content 
about the loop process that can be written by the Iterator pattern.

<div class="translation">
  実はこの the Iterator pattern によって書くことができるループ処理について、<br/>
  同じ内容を全て表現する事ができる高階関数が存在しています。
</div>

---
class: left, top

## the `traverse`

In fact, there is a higher-order function that can express all of the same content 
about the loop process that can be written by the Iterator pattern.

That is the `traverse`.

<div class="translation">
  それが traverse です。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

Now let's look at the definition of `traverse`.

<div class="translation">
  まずは traverse の定義を見てみましょう。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

Now let's look at the definition of `traverse`.

The `traverse` method can be defined for various data structures, 
here we define it as an extension method of `List` as an example.

<div class="translation">
  traverse メソッドは 色々なデータ構造で定義できるのですが、<br/>
  ここでは例として List の拡張メソッドとして定義しましょう。
</div>
---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

Now let's look at the definition of `traverse`.

The `traverse` method can be defined for various data structures, 
here we define it as an extension method of `List` as an example.

This is a little difficult, but let's look at them in order.

<div class="translation">
  いきなりちょっと難しい定義が出てきましたが、順番に見ていきましょう。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [`A`](self: List[`A`]) with {
  def traverse[G[_]: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

First, `List` has a type parameter `A` that indicates the type of its own elements.

<div class="translation">
  まず List は自身が持つ要素の型を示す A という型パラメータを持っています。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[`G`[_]: Applicative, `B`](f: (A) => G[B]): G[List[B]]
}
```

And the `traverse` method introduces two type parameters, `G` and `B`.

<div class="translation">
  そして traverse メソッドでは G と B という二つの型パラメータを導入しています。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[`G[_]`: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

`G` is `G[_]`, which also represents a type that takes one type parameter.

<div class="translation">
  G は G[_] となっており、これも型パラメータを一つとる型を表します。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[`G[_]`: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

`G` is `G[_]`, which also represents a type that takes one type parameter.

For example, we can assign `List`, `Option`, or `Either[String, *]` to `G[_]`.

<div class="translation">
  例えば List とか Option とか Either[String, *] とかを G[_] に指定することができます。
</div>
---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]`: Applicative`, B](f: (A) => G[B]): G[List[B]]
}
```

In addition, `G[_]` has a constraint, requiring a typeclass of `Applicative`.

<div class="translation">
  さらに G[_] には制約がついており、Applicative の型クラスを要求しています。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]`: Applicative`, B](f: (A) => G[B]): G[List[B]]
}
```

In addition, `G[_]` has a constraint, requiring a typeclass of `Applicative`.

We will talk about what is `Applicative` later.

<div class="translation">
  Applicative については後ほどまた触れますので、<br/>
  ここではそういうものがあるんだーくらいに思って頂ければ。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: `(A) => G[B]`): G[List[B]]
}
```

It then takes as its argument "a function that takes an element type `A` and returns a `B` wrapped in a `G`".

<div class="translation">
  「要素型の A を受け取り G に包まれた B を返す関数」を引数として受け取ります。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: `(A) => G[B]`): G[List[B]]
}
```

It then takes as its argument "a function that takes an element type `A` and returns a `B` wrapped in a `G`".

For example, if the instance is of type `List[String]`, 
then `A` becomes `String` and functions of type `String => Option[Int]` are accepted as arguments.

<div class="translation">
  例えば List[String] 型のインスタンスだったとしたら、<br>
  A が String になり、String => Option[Int] 型の関数などが引数として渡せます。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: (A) => G[B]): `G[List[B]]`
}
```

The result is `List[B]` wrapped in `G`.

<div class="translation">
  結果として G に包まれた List[B] が返されます。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

Let's look at an example of actual use.

<div class="translation">
  実際に利用例を見てみましょう。
</div>

---
class: left, top

## `traverse` of `List`

```scala
extension [A](self: List[A]) with {
  def traverse[G[_]: Applicative, B](f: (A) => G[B]): G[List[B]]
}
```

Let's look at an example of actual use.

The above definition is just a hypothetical example, 
Using cats we can be used as an instance method of `List` as if it were defined as such.

<div class="translation">
  上記の定義はあくまで仮定の例ですが、 <br>
  cats を使うとあたかもこのような定義がされてるかのように<br>
  List のインスタンスメソッドとして使う事ができます。
</div>

---
class: left, top

## `traverse` of `List`

If `Some` is returned for all elements,

```scala
val list: List[String] = List("1", "2", "3", "4", "5")

val result: Option[List[Int]] = list.traverse(_.toIntOption)
println(result)
```

<div class="translation">
  全ての要素で Some を返した場合、
</div>

---
class: left, top

## `traverse` of `List`

If `Some` is returned for all elements,

```scala
val list: List[String] = List("1", "2", "3", "4", "5")

val result: Option[List[Int]] = list.traverse(_.toIntOption)
println(result)
```

the result is a `List` wrapped in `Some`.

```scala
Some(List(1, 2, 3, 4, 5))
```

<div class="translation">
  結果は Some で包まれた List が返されます。
</div>

---
class: left, top

## `traverse` of `List`

If there is an element that is `None` on the way,

```scala
val list: List[String] = List("1", "2", `"aaa"`, "4", "5")

val result: Option[List[Int]] = list.traverse(_.toIntOption)
println(result)
```

<div class="translation">
  途中 None になる要素が存在した場合、
</div>

---
class: left, top

## `traverse` of `List`

If there is an element that is `None` on the way,

```scala
val list: List[String] = List("1", "2", `"aaa"`, "4", "5")

val result: Option[List[Int]] = list.traverse(_.toIntOption)
println(result)
```

the result is `None`.

```scala
None
```

<div class="translation">
  結果は None が返されます。
</div>

---
class: left, top

## the `traverse`

```scala
val list: List[String] = List("1", "2", "3", "4", "5")

val result: Option[List[Int]] = list.traverse(_.toIntOption)
println(result)
```

```scala
Some(List(1, 2, 3, 4, 5))
```

In short, a `traverse` method is an operation that takes a function that returns an element as some `Applicative` value and keeps the original structure as an `Applicative` value.

<div class="translation">
  要するに traverse メソッドは、「要素を何かしらの Applicative な値にして返す関数」<br>
  を引数にとり Applicative な値として元の構造を保つ操作、と言えます。
</div>

---
class: left, top

## `Applicative`

It is difficult to understand what is meant by "a function that returns an element as some `Applicative` value" and keeps the original structure as an `Applicative` value," isn't it?

<div class="translation">
  「要素を何かしらの Applicative な値にして返す関数」を引数にとり<br>
  Applicative な値として元の構造を保つ操作、と言われても何が何やらですよね？
</div>

---
class: left, top

## `Applicative`

It is difficult to understand what is meant by "a function that returns an element as some `Applicative` value" and keeps the original structure as an `Applicative` value," isn't it?

Many of you may be wondering what an `Applicative` value is.

<div class="translation">
  そもそも Applicative な値とはなんぞや？となってる方も多いかと思います。
</div>

---
class: left, top

## `Applicative`

It is difficult to explain what `Applicative` is in this session, because it is too abstract a concept.

<div class="translation">
  あまりにも抽象的な概念のため<br>
  Applicative とは何か、をこのセッション内で判りやすく伝える事は難しいです。
</div>

---
class: left, top

## `Applicative`

It is difficult to explain what `Applicative` is in this session, because it is too abstract a concept.

Here, it is sufficient to understand that Applicative is a typeclass with the following two methods.

<div class="translation">
  ここでは以下の二つのメソッドを持った型クラスとだけ認識していただければ大丈夫です。
</div>

---
class: left, top

## `Applicative`

It is difficult to explain what `Applicative` is in this session, because it is too abstract a concept.

Here, it is sufficient to understand that Applicative is a typeclass with the following two methods.

- `pure`: It generates a value of type `G[A]` from a value of type `A`

<div class="translation">
  pure: A 型の値から G[A] 型の値を生成するメソッド
</div>

---
class: left, top

## `Applicative`

It is difficult to explain what `Applicative` is in this session, because it is too abstract a concept.

Here, it is sufficient to understand that Applicative is a typeclass with the following two methods.

- `pure`: It generates a value of type `G[A]` from a value of type `A`
- `map2`: It generates a value `G[C]` from two `G[_]` wrapped values `G[A]` and `G[B]`

<div class="translation">
  map2: G[_] に包まれた二つの値 G[A] と G[B] から、G[C] という値を生成できるメソッド
</div>

---
class: left, top

## `Applicative`

- `pure`: It generates a value of type `G[A]` from a value of type `A`
- `map2`: It generates a value `G[C]` from two `G[_]` wrapped values `G[A]` and `G[B]`

In code, In code, It is the type as follows.

```scala
trait Applicative[G[_]] {
  def pure[A](a: A): G[A]
  def map2[A, B, C](a: G[A], b: G[B])(f: (A, B) => C): G[C]
}
```

<div class="translation">
  コードで表現するとこのようなインターフェイスが実装できる型となります。
</div>

---
class: left, top

## `Applicative`

```scala
trait Applicative[G[_]] {
  def pure[A](a: A): G[A]
  def map2[A, B, C](a: G[A], b: G[B])(f: (A, B) => C): G[C]
}
```

`pure` is an operation that wraps a value.

<div class="translation">
  pure は値を包む操作ですね。
</div>

---
class: left, top

## `Applicative`

```scala
trait Applicative[G[_]] {
  def pure[A](a: A): G[A]
  def map2[A, B, C](a: G[A], b: G[B])(f: (A, B) => C): G[C]
}
```

`pure` is an operation that wraps a value.

For `Option` it is `Option.apply` and ...

```scala
given Applicative[Option] with {
  def pure[A](a: A): Option[A] = Option(a)
  ...
```

<div class="translation">
  Option であれば Option.apply ですし、
</div>

---
class: left, top

## `Applicative`

```scala
trait Applicative[G[_]] {
  def pure[A](a: A): G[A]
  def map2[A, B, C](a: G[A], b: G[B])(f: (A, B) => C): G[C]
}
```

`pure` is an operation that wraps a value.

For `Option` it is `Option.apply` and for `List` it is `List.apply`.

```scala
given Applicative[Option] with {
  def pure[A](a: A): Option[A] = Option(a)
  ...
```

```scala
given Applicative[List] with {
  def pure[A](a: A): List[A] = List(a)
  ...
```

<div class="translation">
  Option であれば Option.apply ですし、List であれば List.apply です
</div>

---
class: left, top

## `Applicative`

```scala
trait Applicative[G[_]] {
  def pure[A](a: A): G[A]
  def map2[A, B, C](a: G[A], b: G[B])(f: (A, B) => C): G[C]
}
```

`map2` is the two values version of `map`.

<div class="translation">
  では map2 とはどういう操作かというと map の二つ版の事です。
</div>

---
class: left, top

## `Applicative`

```scala
trait Applicative[G[_]] {
  def pure[A](a: A): G[A]
  def map2[A, B, C](a: G[A], b: G[B])(f: (A, B) => C): G[C]
}
```

`map2` is the two values version of `map`.

For `Option` as following and

```scala
given Applicative[Option] with {
  ...
  def map2[A, B, C](a: Option[A], b: Option[B])
       (f: (A, B) => C): Option[C] = {
    (a, b) match {
      case (Some(a), Some(b)) => Some(f(a, b))
      case _                  => None
    }
  } 
```

<div class="translation">
  Option であれば上記のようになりますし、
</div>

---
class: left, top

## `Applicative`

```scala
trait Applicative[G[_]] {
  def pure[A](a: A): G[A]
  def map2[A, B, C](a: G[A], b: G[B])(f: (A, B) => C): G[C]
}
```

`map2` is the two values version of `map`.

For `List` as following

```scala
given Applicative[List] with {
  ...
  def map2[A, B, C](a: List[A], b: List[B])
       (f: (A, B) => C): List[C] = 
    for {
      a_ <- a
      b_ <- b
    } yield f(a_, b_)
```

<div class="translation">
  List であれば上記のようになります
</div>

---
class: left, top

## `Applicative`

Compared to `map` as following

<div class="translation">
  map と比較すると次のような感じです。
</div>

---
class: left, top

## `Applicative`

Compared to `map` as following

```scala
def map[A, B](a: Option[A])(f: (A) => B): Option[B]

def map2[A, B, C](a: Option[A], b: Option[B])
  (f: (A, B) => C): Option[C]
```

<div class="translation">
  Option 版
</div>

---
class: left, top

## `Applicative`

Compared to `map` as following

```scala
def map[A, B](a: Option[A])(f: (A) => B): Option[B]

def map2[A, B, C](a: Option[A], b: Option[B])
  (f: (A, B) => C): Option[C]
```

```scala
def map[A, B](a: List[A])(f: (A) => B): List[B]

def map2[A, B, C](a: List[A], b: List[B])
  (f: (A, B) => C): List[C]
```

---
class: left, top

## `Applicative`

Compared to `map` as following

```scala
def map[A, B](a: Option[A])(f: (A) => B): Option[B]

def map2[A, B, C](a: Option[A], b: Option[B])
  (f: (A, B) => C): Option[C]
```

```scala
def map[A, B](a: List[A])(f: (A) => B): List[B]

def map2[A, B, C](a: List[A], b: List[B])
  (f: (A, B) => C): List[C]
```

While `map` returns a result from single value and one-parameter function, 
`map2` returns a result from two values and  two-parameters function.

<div class="translation">
  map は一つ値と一引数関数から結果を作るのに対し、
  <br>map2 は二つの値と二引数関数から結果をつくります。
</div>

---
class: left, top

## `Applicative`

Compared to `map` as following

```scala
def map[A, B](a: Option[A])(f: (A) => B): Option[B]

def map2[A, B, C](a: Option[A], b: Option[B])
  (f: (A, B) => C): Option[C]
```

```scala
def map[A, B](a: List[A])(f: (A) => B): List[B]

def map2[A, B, C](a: List[A], b: List[B])
  (f: (A, B) => C): List[C]
```

While `map` returns a result from single value and one-parameter function, 
`map2` returns a result from two values and  two-parameters function.

In other words, `map2` can be used to combine multiple values into a single value.

<div class="translation">
  つまり map2 が使えると、複数の値を合成して一つの値にすることができます。
</div>

---
class: left, top

## the `traverse`

The reason why `traverse` is so powerful is that it can take advantage of this `Applicative` property.

<div class="translation">
  traverse がなぜ強力なのかと言うと、この Applicative の性質を活用できるからです。
</div>

---
class: left, top

## the `traverse`

The reason why `traverse` is so powerful is that it can take advantage of this `Applicative` property.

Let's look at a concrete example.

<div class="translation">
  具体例を見てみましょう。
</div>

---
class: left, top

## the `traverse`