Elixirでの累積リスト1作成
本記事では累積リストとは、[1,2,3] -> [[1],[1,2],[1,2,3]] のように1次元のリストがあったとき、n番目までの要素のリスト、を要素とするリストのこと。リストのリストとなる。「ジャグ配列」だと階段状であることが表現できないので、ここでは累積リストと呼ぶことにする。
用途としては、nの階乗を順に並べたリスト[1,2,6,24,120]を作ったり、Windowsのフォルダを並べたリスト["c:", "Users", "Doe", "Documents"]から、親フォルダの絶対パスを階層の順["c:", "c:/Users", "c:/Users/Doe", "c:/Users/Doe/Documents"]に得たりする。
ElixirでEnum.reverse/1を活用して実装した。build_cumulative/1では、Enum.reverse/1を使ってリストの順を逆順にする。また、結果をとるアキュムレーターの初期値[]を第2引数にして、build_cumulative/2を呼び出す。
def build_cumulative(enum) do: build_cumulative(Enum.reverse(enum), [])
# [1,2,3] -> build_cumulative([3,2,1])
build_cumulative/2では、第1引数（元のリスト全体）を再度逆順にすることによって元に戻したリストをアキュムレーターに渡す。逆順リストからヘッダ（＝末尾項目）を除く。のぞいた結果を第1引数に与えて再帰的に自分自身を呼び出す。
def build_cumulative([head | tail], acc) do
build_cumulative(tail, [Enum.reverse([head | tail])|acc])
end
# [3 | [2,1]], [] -> build_cumulative( [2,1], [[1,2,3] | []])
すべての項目が除かれたら、アキュムレーターには完成した累積リストが入っているので、それを終了条件としてアキュムレーターを返す。
def build_cumulative([], acc), do: acc
累積リストのコード全体
def build_cumulative(enum) do: build_cumulative(Enum.reverse(enum), [])
def build_cumulative([], acc), do: acc
def build_cumulative([head | tail], acc) do
build_cumulative(tail, [Enum.reverse([head | tail])|acc])
end
応用
累積リストの応用例である累積和や階乗リスト、フォルダ階層はEnum.scan/2でも実現でき、最適化もされているので累積リストをあえて使うことはないかもしれない2。累積リストは基礎的な興味を満たすのと、後続の処理で関数の引数が要素ではなくリストを使えるところが違い。
累積和
累積リストができると、Enum.mapの第2引数に与える関数をリストに対する関数を与えることができ、1, 1+2, 1+2+3, ... のような項目数が一つずつ増えた数列の和を返すことができる。
1..10
|> build_cumulative()
|> Enum.map( fn list -> Enum.reduce(list, fn x, acc -> acc + x end) end)
#[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
[別解]
1..10 |> Enum.scan(fn x, acc -> acc + x end)
階乗
階乗も項目数を1つずつ増やした数列の積のリストとして得ることができる。
1..10
|> build_cumulative()
|> Enum.map( fn list -> Enum.reduce(list, fn x, acc -> acc * x end) end)
#[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
[別解]
1..10 |> Enum.scan(fn x, acc -> acc * x end)
フォルダ階層
フォルダ階層も、親の階層から順に子、孫、ひ孫の階層のフォルダの絶対パスにすることができる3。
["c:","User","Doe","Documents"]
|> build_cumulative()
|> Enum.map( fn list -> Enum.join(list,"/") end)
#["c:", "c:/User", "c:/User/Doe", "c:/User/Doe/Documents"]
[別解]
["c:","User","Doe","Documents"] |> Enum.scan(fn x, acc -> acc <> "/" <> x end)
複数階層からの絞り込み
組織階層の途中のノードで絞り込みを行う。
[
["ABC株式会社", "D事業部", "E部", "F室"],
["ABC株式会社", "D事業部", "E部", "G室"],
["ABC株式会社", "H事業部", "J部", "K室"],
["ABC株式会社", "I事業部", "L部", "M室"]
]
|> Enum.map(fn hierarchy -> build_cumulative(hierarchy) end)
|> Enum.map(fn hierarchy_list -> Enum.filter(hierarchy_list, fn list -> Enum.any?(list, fn x -> x == "E部" end) end) end)
|> Enum.filter(fn hierarchy_list -> hierarchy_list != [] end)
#[
# [
# ["ABC株式会社", "D事業部", "E部"],
# ["ABC株式会社", "D事業部", "E部", "F室"]
# ],
# [
# ["ABC株式会社", "D事業部", "E部"],
# ["ABC株式会社", "D事業部", "E部", "G室"]
# ]
#]