田舎で並行処理の夢を見る

試したこと、需要がないかもしれないけど細々とアウトプットしてます

【モジュールとの比較】Elixirで無名関数を使って再帰処理を記述する方法

無名関数では再帰処理が難しい

Elixir再帰関数を記述しようと思った際には、defmodule Fooと定義して、そのモジュール内部にdef barのように関数を定義して、パターンマッチもしくは、分岐処理によって再帰関数を処理するのが一般的。

defmodule Sample do
  def sum([], acc), do: acc
  def sum([head | tail], acc) do
    sum(tail, acc+head)
  end
end

Sample.sum([1,2,3], 0)
|> IO.puts()
# 6

しかし、わざわざモジュールに定義したくない時、対して使い回す予定もなく、1回きりの再帰処理が書きたい場合には上記のようにモジュールを定義して、再帰関数を記述するという方法は煩わしいとも言える。とすると、使い切りの関数として候補にあがるのは無名関数ということになる。
しかしながら、工夫なしに記述した無名関数では再帰処理を行うことが出来ない。それはなぜか。以下のコードを元に話を進める。

sum_ = fn lst, acc -> 
  case lst do
    [] -> acc
    [head | tail] -> sum_.(tail, acc+head) # <- ここでerror
  end
end

sum_.([1,2,3], 0)

実行結果

warning: variable "sum_func" does not exist and is being expanded to "sum_func()", please use parentheses to remove the ambiguity or change the variable name
  Main.exs:4

このerrorから読み取るに4行目に記述しているsum_.(tail, acc+head)が実行不可能であるということ。それはなぜかというと、sum_/2関数のスコープが無名関数の内部からは参照出来ないからということになる。つまり、Elixirの無名関数は自身を自身で参照することが出来ないということになる。それに対してモジュールに定義された関数は自身のスコープを参照可能ということになっている。

ということで一工夫

色々と試行錯誤して以下の形に落ち着いた。レシピとしては無名関数の内部で別の無名関数を定義して、その無名関数自身を引数に渡して、再帰的に呼び出すことで先ほどのスコープ対象外になる問題を解決した。全く勉強したことがないが、ラムダ計算の分野からの知恵を借りた。

sum_ = fn arg_lst ->
  # 自分自身を引数に受け取ることでスコープ問題を解消
  sub_sum = fn lst, acc, own_func ->
    case lst do
      # 終了条件を記述
      [] -> acc
      # 自分自身を呼び出し、引数にも自分自身を渡す
      [head | tail] -> own_func.(tail, acc+head, own_func)
    end
  end
  # 内部で定義した無名関数を実行
  sub_sum.(arg_lst, 0, sub_sum)
end

# ついでにアキュムレーターを内部化
sum_.([1,2,3])
|> IO.puts()
# 6

無名関数の内部で別の無名関数を定義して、その無名関数自体を、その無名関数の引数に渡すという頭がおかしくなりそうな一手間を加えることで無名関数でも再帰処理を行うことが出来る。合計値を求めるだけのシンプルな処理なので可読性は何とか保てているが、より複雑な処理を行うとなると、無名関数での再帰処理には首を傾げることになる。コードの行数もシンプルにしようとしているのに行数が増えてしまっている。

「使うな!」とまでは言わないが、趣味用であり、チーム開発での使用は避けるべきだと感じた。こういうの好きだけど。せっかく覚えた知識なので、いくつかサンプルを記述した。モジュールとの比較もしているので可読性の悪さを感じてみてほしい。

サンプル

リストの各要素をN倍に

無名関数ver

n_times = fn n, lst -> 
  sub_n_times = fn lst, acc, own_func ->
    case lst do
        [] -> acc
        [head | tail] -> own_func.(tail, acc ++ [head * n], own_func)
    end
  end
  sub_n_times.(lst, [], sub_n_times)
end

n_times.(2, [1,2,3])
|> IO.inspect()
# [2, 4, 6]

モジュールver

defmodule Sample do
  def n_times(p, lst) do
    _n_times(lst, p, [])
  end
  defp _n_times([], _, acc), do: acc
  defp _n_times([head | tail], p, acc) do
    _n_times(tail, p, acc ++ [head * p])
  end
end

Sample.n_times(2, [1,2,3])
|> IO.inspect()
# [2, 4, 6]

というかEnum.map/2で良いのでは説。

enum_map_ver = fn p, lst ->
  Enum.map(lst, fn n -> n * p end)
end

enum_map_ver.(2, [1,2,3])
|> IO.inspect()
# [2, 4, 6]

クイックソート

以前の記事で記述したクイックソート(先頭要素をpivotとして取得するversion)を無名関数の再帰処理を用いてリライトしてみた。書いた感想といてはモジュールの方が楽だなというのが正直な感想。書き切った時は嬉しいが、後に見返してみるとそれぞれの関数の引数のスコープがどこまで参照可能なのかが分かりにくく、やはり可読性に欠ける。

無名関数ver

quick_sort = fn base_lst -> 
  append = fn sorted_lst, pivot ->
    sub_append = fn lst, acc, own_func -> 
      case lst do
        [] -> acc ++ [pivot]
        [head | tail] -> 
          if pivot > head do
            own_func.(tail, acc ++ [head], own_func)
          else
            acc ++ [pivot, head] ++ tail
          end
      end
    end
    sub_append.(sorted_lst, [], sub_append)
  end
  Enum.reduce(base_lst, [], fn p, acc -> 
    append.(acc, p)
  end)
end

quick_sort.([8,2,6,5,7,3,1,4,9])
|> IO.inspect()
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

モジュールver

defmodule Algo do
  def quick_sort(lst), do: _quick_sort(lst, [])
  defp _quick_sort([], accum), do: accum
  defp _quick_sort([head | tail], accum) do
    res = append(head, accum, [])
    _quick_sort(tail, res)
  end
  def append(num, [], accum), do: accum ++ [num]
  def append(num, [head | tail], accum) do
    case num > head do
      true -> append(num, tail, accum ++ [head])
      false -> accum ++ [num] ++ [head] ++ tail
    end
  end
end

おまけ

こんな風に記述しても無名関数で再帰処理を行うことが出来るが、使用者に対して、引数に無名関数を渡すことを意識させる必要があるため、ナンセンスだとは思うが、分かっていて使うのであれば、コード量は減るので悪くはないと思う。

sum_ = fn lst, acc, func -> 
  case lst do
    [] -> acc
    [head | tail] -> func.(tail, acc+head, func)
  end
end

sum_.([1,2,3], 0, sum_)
|> IO.puts()
# 6

参考文献