[Elixir]再帰/逐次アクセスをEnum.Map/Reduceに書き換え(本編)


どうもfukuoka.exキャストの@hisawayです．

研究の一環で「再帰で書かれた行列・ベクトル演算プログラムをEnum.map/reduceで書き換える」 ことがありました．

この過程で得られたTIPSを残します．

Elixir入門者向けの内容となっています．

(今回は簡単のために， 2x2行列と1x2ベクトルの内積に限定した行列演算コードになっています．ご了承ください．)

---

# 入門
２つの行列があったとします． (N, M)行列AとM次元ベクトルBです．これを乗算するとN次元ベクトルになりますね．

これを素直に記述すれば，下記のようなforを使ったスタイルになります．(C++の場合)

```c++
for(int i = 0; i < N; ++i){
  for(int j = 0; j < M; ++j){
    ans[i] += A[i][j] * B[j];
  }
}
```

ループは行列の合計を求めるために使っているものであって，必須のものではありません．

(詳しくは @piacere_ex さんの[「Elixirは何故whileやメンバー変数が無いの？」に答えてみる①](https://qiita.com/piacere_ex/items/11cd08c1a74694309482)をご覧ください．)

上記のようなコードからEnum.map/reduceに書き換えられるようになる手順について説明していけたらと思います．

#Elixirらしさとmap/reduce
Enum.map/reduceで書くことで得られるメリットはいくつかあります．

## データフロー的思考
メリットの1つは，パイプライン演算子`|>`を用いたデータフロー的思考が身につくことです．

`|>`を使わずに記述すると関数がネストされた形です．

```elixir
def function do
  Enum.map(Enum.map(data, func1), func2)
end
```
(Enum.mapの説明は後述)

`|>`を使った場合は

```elixir
def function do
 data |> Enum.map(func1) |> Enum.map(func2)
end
```

これを綺麗だとか美しいとか思えた人は読む価値がきっとあると思います．
また，パイプライン演算子を使うことを見据えてコードを書くと関数の設計規則が自然と統一されるというメリットがあります．

- 関数の第1引数にリストのようなコレクションを渡す
- 関数の出力は入力データの加工結果

他にもmap/reduceを採用するメリットがあります．
- 可読性がよくなる
- 並列プログラミング処理系「Hastega」の恩恵を受けられる(予定)
    - [ZEAM開発ログ: Elixir マクロ + LLVM で超並列プログラミング処理系を研究開発中](https://qiita.com/zacky1972/items/cc88260a3c93c9f71317)

# 再帰/逐次アクセス -> map/reduce
代表的なハマるパターンというか条件は

この条件に当てはまってしまった方がすでにElixir側で行列演算の再帰のコードを書いてしまったとします．

- 関数型言語を触ったことがなく，Elixirに入ってしまった人
- Elixirにはループがないと聞いて再帰で記述した人
- オブジェクト指向言語だけずっと使ってきた人(私のことです)

```elixir
defmodule Matrix do
  @moduledoc """
  Documentation for Matrix.
  """

  @doc """
  Calculate matrix

  ## Examples
      iex> Matrix.dot([[1, 2], [3, 4]], [0.1, 0.2])
      [0.5, 1.1]
  """

  @row 2
  @col 2

  def dot(a, b) do
    calculate_matrix(a, b, 0, [], 0, 0)
  end

  defp calculate_matrix(a, b, result_col, result, i, @col) do
    calculate_matrix(a, b, 0, result ++ [result_col] , i + 1, 0)
  end

  defp calculate_matrix(_, _, 0, result, @row, 0) do
    result
  end

  defp calculate_matrix(a, b, result_col, result, i, j) do
    ans = result_col + Enum.at(Enum.at(a, i), j) * Enum.at(b, j) 
    |> IO.inspect(label: "loop")

    calculate_matrix(a, b, ans, result, i, j + 1)
  end
```

## テストコードを書く
上記サンプルにはテストコードを書いていますが，もし書いていなら**速攻で書きましょう**．

やり方
1. `iex -S mix`
2. 作成した関数に入力を与えて実行
3. 実行したコードと出力結果を下記を参考にしてコピペ(行番号的なのを消す)
4. `mix test`で 0 failuresになっていればOK

```elixir
@doc """
markdownで関数の説明が書ける

## Example
      iex> Matrix.calculate_matrix_enumed1([[1, 2], [3, 4]], [0.1, 0.2])
      [0.5, 1.1]
"""
# 関数定義部と続く
```

## とにかく再帰だけを消す
ここから本題です．
逐次アクセスと再帰を一気に消すのは難しいので，少しずつ再帰だけを消す方向で進めます．
まずは，引数の性質について整理します．大きく分けて2つです．

1. 配列番号の引数 - `(i, j)`
2. 計算用の引数 - `(result_col, result)`

### 配列番号の削除
まずは配列番号だけEnum.map化します．
こうすることで， 引数のi, jを消します．

>Enum.map(enumerable, funtion)
コレクションを第1引数として渡して，コレクションの各要素に第2引数で渡された関数を適用します．そして結果をリストとして返します．

本稿で扱うコレクションは`Range`と`List`です．

インデックスは`Range`と`Enum.map`の組み合わせで実現できます．
　`Range`と`Enum.map`処理の回数を把握しましょう．

```elixir
iex(1)> 0..2 |> Enum.map(& &1)
[0, 1, 2]
```

これを踏まえた上で計算処理を除いた部分を`Range`と`Enum.map`で記述すると下記のようになります．
(#はコメント文)

```elixir
def calculate_matrix_enumed1(a, b, 0, []) do
    0..(@row-1) # 0..1
    |> Enum.map( # row loop
      fn i -> 
        0..(@col-1) # 0..1
        |> Enum.map( # col loop
          fn j -> 
            # Process
        end) # col loop
    end) # row loop
  end
```

これで関数の引数が２つ減らせました．

### 計算用の引数を消す
ここで`Enum.reduce`が登場します．消す引数はresult_colとresultです．
定義とサンプルコードを引用します
>reduce(enumerable, function)
コレクションを第1引数として渡して，コレクションの各要素に第2引数で渡された関数を適用します．第2引数で渡す関数はアリティが２つあることが条件です，関数の適用結果を第2引数の関数の引数2:アキュムレータに蓄積します．

```elixir
iex>Enum.reduce([1, 2, 3, 4], fn x, acc -> x * acc end)
24
```
(参照「[Enum- Elixir v1.8.1(HexDocs)](https://hexdocs.pm/elixir/Enum.html)」)

accはaccumulator(蓄積機)の略です．

知らない人がどれくらいの割合でいるのか．多いのか，少ないのか私にはわからないので紹介しておきます．
(私はElixir入門時には知りませんでした．)

逐次アクセス`Enum.at`を残したまま，`Enum.reduce`を適用します．
内側から順番にやっていきます．

内側の計算結果の蓄積部はこうです．

```elixir
ans = result_col + Enum.at(Enum.at(a, i), j) * Enum.at(b, j) 
      |> IO.inspect(label: "loop")

calculate_matrix(a, b, result_col + ans, result, i, j + 1)
```

演算する行列Aの行を決めたら`result_col`にその行と行列Bの演算結果を集めていきます．

これは列を回すループで積を蓄積するコードになっているので，内側の列ループ部である`Enum.map`を`Enum.reduce`に変えます．

```elixir
  @doc """
  Calculate matrix with Enum.map/reduce

  ## Examples
      iex> Matrix.calculate_matrix_enumed1([[1, 2], [3, 4]], [0.1, 0.2])
      [0.5, 1.1]
  """
  def calculate_matrix_enumed1(a, b) do
    0..(@row-1) # 0..1
    |> Enum.map( # row loop
      fn i -> 
        0..(@col-1) # 0..1
        |> Enum.reduce( # col loop
          0, # acc の初期値
          fn j, acc -> # accを追加
            acc + Enum.at(Enum.at(a, i), j) * Enum.at(b, j) 
            # labelをつけて受け取ったデータを表示，出力はそのままでデータだけ返す
            |> IO.inspect(label: "j_loop") 
        end) # col loop
    end) # row loop
  end
```

次は外側...と思いきや再帰消し終了です．

外側の計算結果の蓄積部はこうです．

```elixir
calculate_matrix(a, b, 0, result ++ [result_col] , i + 1, 0)
```

この処理は演算結果である`result_col`をリストとして保存していく処理，
つまり`Enum.map`と等価です．

## 逐次アクセスも消す
個人的にがここが一番難しいと思います．
`0..(@row-1) |> Enum.map`としている部分は， リストにアクセスするためのコードです．
直接リストを操作しているコードにはなっていません．
なので， Enum.map部をサンプルコードと同じように**直接リストを操作するように修正します**．

例

```elixir
iex> Enum.map([1, 2, 3], fn x -> x * 2 end)
[2, 4, 6]
```
そこで困るのが，2つ以上のコレクション型を同時に回す場合です．
今回だと，行列Aの行を決めた後， 行列AとベクトルBを同時に参照することになります．

こういうときは`Enum.zip`を使います．

zipは複数のコレクションを圧縮して作る関数です．出力はタプルのリストになっています．

```elixir
iex> Enum.zip([1, 2, 3], [:a, :b, :c])
[{1, :a}, {2, :b}, {3, :c}]
```

では改めてプログラムを修正します．
行列A及びベクトルBを直接操作できるように`Enum.map/Enum.zip`を適用します．

```elixir
 @doc """
  Calculate matrix with Enum.map/reduce

  ## Examples
      iex> Matrix.calculate_matrix_enumed2([[1, 2], [3, 4]], [0.1, 0.2])
      [0.5, 1.1]
  """
  def calculate_matrix_enumed2(a, b) do
    a 
    |> Enum.map( # aから1行ずつ取得
      fn a_row ->  
        Enum.zip(a_row, b) # a, bの各要素でペアを作る
        |> Enum.reduce(0, fn {a1, b1}, acc -> acc + a1 * b1 end) # ペアで乗算して保存
      end)
  end
```

お疲れ様でした．書き換え終了です．`Enum.map`の中身はまだキレイにできますが別記事でやりたいと思います．

# 補足
## mapとreduceの使い方について
`Enum.map`と`Enum.reduce`はとてもよく似ています．
その違いは演算結果をリストとして出力するか，演算結果のリストの要素合計を出力するかという違いです．
極端な話， `Enum.reduce = Enum.map |> Enum.sum`とも書けるますし，`Enum.map = Enum.reduce`とも書けます．

```elixir
iex> 0..2 |> Enum.reduce(fn x, acc -> x + acc end)
3
iex> 0..2 |> Enum.map(fn x -> x end) |> Enum.sum
3
```

## 再帰の使いどきは？
Elixirで抽象構文木(AST)を操作するメタプログラミング時に必要になります．

# まとめ
再帰/逐次アクセスが含まれたコードからmap/reduceを使ったコードに書き換える手順について説明しました．

1. テストコードを書く
2. Enum.mapで再帰を消す(逐次アクセス`Enum.at`は無視)
3. 総和を求める部分は`Enum.map`->`Enum.reduce`
4. `Enum.zip`と`Enum.map`で逐次アクセスを消す

## 追記
(私の過去記事「[Elixirのリストの仕様をまとめてみた](https://qiita.com/hisaway/items/dd25158b2a51832109c7)」で「ループは再帰で」と書いていたので修正しました．参考にされた方いましたらお詫びします．)