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

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

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

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

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

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

---

入門

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

これを素直に記述すれば，下記のようなforを使ったスタイルになります．(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やメンバー変数が無いの？」に答えてみる①をご覧ください．)

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

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

データフロー的思考

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

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

def function do
  Enum.map(Enum.map(data, func1), func2)
end

(Enum.mapの説明は後述)

|>を使った場合は

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

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

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

他にもmap/reduceを採用するメリットがあります．

• 可読性がよくなる
• 並列プログラミング処理系「Hastega」の恩恵を受けられる(予定)
  • ZEAM開発ログ: Elixir マクロ + LLVM で超並列プログラミング処理系を研究開発中

再帰/逐次アクセス -> map/reduce

代表的なハマるパターンというか条件は

この条件に当てはまってしまった方がすでに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

@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処理の回数を把握しましょう．

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

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

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:アキュムレータに蓄積します．

iex>Enum.reduce([1, 2, 3, 4], fn x, acc -> x * acc end)
24

(参照「Enum- Elixir v1.8.1(HexDocs)」)

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

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

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

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

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に変えます．

  @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

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

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

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

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

逐次アクセスも消す

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

例

iex> Enum.map([1, 2, 3], fn x -> x * 2 end)
[2, 4, 6]

そこで困るのが，2つ以上のコレクション型を同時に回す場合です．
今回だと，行列Aの行を決めた後， 行列AとベクトルBを同時に参照することになります．

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

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

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

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

 @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とも書けます．

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のリストの仕様をまとめてみた」で「ループは再帰で」と書いていたので修正しました．参考にされた方いましたらお詫びします．)