【Elixirのサンプルコード有り】条件に一致した時に再帰を停止する方法4つを書き比べてみた

なんでbreak_reduceみたいなのはないんだろう

配列(リスト)に対して、各要素を精査する際に、特定の条件にマッチする要素が見つかった時点で処理を停止して、Elixirであれば{:exist, value}のような値を返す関数をよく作成することがある。頻出の処理パターンではあるが、ElixirのEnumを覗いてみても該当する関数は見当たらない。

(ありそうでない)

# ※これは架空の関数です
Enum.break([1,2,3,4,5], {:ok, 0}, fn n, _ -> n == 3 end)

自分は関数プログラミングの専門家ではないが、これは関数プログラミングがデータの変換を行うことを行うことを重視しており、reduceという関数が、列挙可能な値を全て確認した上でデータ変換を行うという性質であると考えれば、reduce関数の内部でbreakをするというのはイケてないことをしようとしているのではないかと考えることが出来る。
合わせてEnumは列挙可能なデータ構造(enumerables)に対して、処理を適応させるような関数をまとめたモジュールなため、途中で処理が停止して、残りの要素には何もしないという実行方法はミスマッチなんだろうか。

... という仮説を元に、indexを指定して、その値を取得するEnum.atの実装を見てみた。どうやら普通に再帰関数を使って停止させているようだ。仮説は誤っていたのだろうか。

defmodule Enum do
  def at(enumerable, index, default \\ nil) when is_integer(index) do
    case slice_any(enumerable, index, 1) do
      [value] -> value
      [] -> default
    end
  end

  defp slice_any(list, start, amount) when is_list(list) do
    list |> drop_list(start) |> take_list(amount)
  end

  defp drop_list(list, 0), do: list
  defp drop_list([_ | tail], counter), do: drop_list(tail, counter - 1)
  defp drop_list([], _), do: []
end

eg: list = [1, 2, 3, 4, 5], index = 2

-> Enum.at(list, index)
  -> slice_any([1, 2, 3, 4, 5], 2, 1)
    args = [1 | 2, 3, 4, 5], 2
    -> next fn([2, 3, 4, 5], 1)

    args = [2 | 3, 4, 5], 1
    -> next fn([3, 4, 5], 0)

    return [3, 4, 5]

  -> drop_list([3, 4, 5], 1)
    args = [3 | 4, 5], 1
    return [3]

  return [3]

# 最終的なreturn
3

Elixirを使っている立場から言えることは、「頻出の処理なのでEnumに実装して頂ければ有難いのですが....」ということ。
以下に同じ処理をいくつかの記述方法で実装したサンプルを載せているが、結果的にEnum.reduce関数を使わずとも、再帰関数を記述すれば、上記の処理をbreakする形式で記述することは出来る。要は面倒か、面倒ではないかのみ。

自分は一年程前に「関数型言語って副作用ないし、かっこいいし、流行ってる...」という理由で始めた不届き者です。今回の仮説と記述を通して、今更ながら「関数型言語とはどういうものなのか？」と改めて考える機会になり、非常に勉強になった。

qiita.com

ロックの例えが分かりやすかった。ロックとは何かを定義するよりも、ロックをたくさん聞いた方が早いというのはなるほどなぁと感じた。

サンプル

mapにマイナスの値を持つkeyが1つでも存在すれば初登場のkvのセットを返すという処理を例に示す。実際にこの処理は以下の記事で過去に記述した処理を採用している。

この記事を書いた時は、再帰を使うのか...Enum.reduceを使うのか...とかなり悩んだ。

www.okb-shelf.work

本来はパフォーマンスの比較のために複数のkeyの数が異なるデータを用意するべきだが、記事が長くなりすぎてしまうため、今回は割愛。シンプルに5つのkey(A, B, C, D, E)を持つmapを用意して4種類の記述方法を試してみる。

data = %{
    "A" => 1,
    "B" => 1,
    "C" => -1,
    "D" => 1,
    "E" => -1
}

条件として、mapにマイナスの値が存在しており、確認した際は{:exist, %{"C" => -1}}のような該当したデータを返し、存在しないのであれば{:ok, %{}}を返すようにする。

Enum.reduce編

普通にreduce使って書く。

Enum.reduce(data, {:ok, %{}}, fn {k, v}, acc -> 
    {_, acc_map} = acc
    if v < 0 do
        if Enum.count(acc_map) == 0 do
            {:exist, Map.put(acc_map, k, v)}
        else
            acc
        end
    else
        acc
    end
end)
|> IO.inspect()

# {:exist, %{"C" => -1}}

ちゃんとif else endを使用して返す値を明示的に記述してあげないと、nilが返ってしまうため、思わぬ結果となってしまうので注意。個人的にはインデントとコード行数が複雑になるので、簡潔な記述とは言えないのが残念。

再帰関数編

いつも自分が採用する形式。なぜ再帰関数を使っているかというと、条件に一致した時に再帰を停止させることが出来るため。普段使いするgolangやpythonでいうところの以下の処理に該当するのでデータ数が大きくなればなるほど、Enum.reduceで記述したものとはパフォーマンスに差が現れてくるだろう。計算量自体は最悪時を考えるため、一緒になるが(O(N), N=mapのkeyの数)。

package main
import "fmt"
func main(){
    // Your code here!
    
    num := 3
    for i := 0; i< 10; i++ {
        if i == num {
            fmt.Println("hit: ", i)
            break
        }
    }
}

defmodule Sample do
    def reduce_break(map) do
        _reduce_break(Map.keys(map), map, {:ok, %{}})
    end
    defp _reduce_break([], _, acc), do: acc
    defp _reduce_break([head | tail], map, acc) do
        {_, acc_map} = acc
        if Map.get(map, head) < 0 do
            {:exist, Map.put(acc_map, head, Map.get(map, head))}
        else
            _reduce_break(tail, map, acc)
        end
    end
end

Sample.reduce_break(data)
|> IO.inspect()

# {:exist, %{"C" => -1}}

モジュール使ったので若干、コード量は増えてはいるが見通しの良さは引数パターンマッチのおかげだ。先ほども記述したように、条件に一致した際に、再帰を終了して値を返して関数の実行を終了する。

if Map.get(map, head) < 0 do
    # return value
    {:exist, Map.put(acc_map, head, Map.get(map, head))}
else
    # recursive: call own
    _reduce_break(tail, map, acc)
end

Enum.filter + Enum.reduce編

最近、意識するようになった記述方法でほぼ全ての処理をEnumとパイプラインで記述することが可能なため、「Elixirを書いてるんだ〜」という熱い思いを感じることが出来る。

filtered = Enum.filter(data, fn {k, v} -> 
    if v < 0 do
        {k, v}
    end
end)

if length(filtered) > 0 do
    Enum.at(filtered, 0)
    |> (fn {k, v} -> {:exist, Map.put(%{}, k, v)} end).()
    |> IO.inspect()
end

# {:exist, %{"C" => -1}}

書き終えてから気づいたが、reduce使っていない。あと、パイプラインで無名関数使うのはスタイルガイド的にはnot preferredなので、乱用しないこと。

無限リストと遅延評価を使った(Stream.transform)実装

今回の記事を書く前まで無限リストと遅延評価について、全く知らない状態だったが、記事をまとめる中で完全に理解して、チョットワカル状態になった。こちらの実装方法は普段、大変お世話になっているpiacereさんから教えて頂いたものだ。

再帰でbreakしなければならない状況では、Stream .transformが便利です😌 #fukuokaex

これなら、無限ループの中でのbreakも書けます😉

Stream .transformのサンプルを、以前コラム化したので、よければご参考にどぞー💁‍♂️https://t.co/Musi80HODJ
— piacere@DigiDock (love Elixir&Gravity＋仮想世界創造機構) (@piacere_ex) 2019年7月1日

執筆されている、こちらの記事も非常に分かりやすかったです。

qiita.com

Stream.transform(data, false, fn {k, v}, judge ->
  if judge do
    {:halt, judge}
  else
    if v < 0 do
        {[{:exist, Map.put(%{}, k, v)}], true}
    else
        {[], judge}
    end
  end
end)
|> Enum.to_list()
|> (fn lst -> 
        if length(lst) > 0 do
            Enum.at(lst, 0)
        else
            {:ok, %{}}
        end
    end).()
|> IO.inspect()

# {:exist, %{"C" => -1}}

注意点としては、Stream.transformは少し癖があり、条件に一致しない時は要素を2つ持つタプルを返す必要があり、第1要素にはリストを。第2要素には次の再帰で使用したアキュムレーターの値を渡す。最終的な戻り値は{:halt, _}を返す直前の条件に一致しなかった際に記述してきた{[], judge}の第1要素になる(これで少し迷った)。

無限ストリームを使用しているため、必要な要素分だけ判定されるため、再帰を用いてbreakをした時と同様のパフォーマンス(データ生成のパフォーマンスは考えない)になるのではないかと考えられる。