概要
flatten 関数の定義への気持ち悪さが何だったのか、以下にて述べました。
defmodule Ex do
def flatten([]), do: []
def flatten([h|t]), do: flatten(h) ++ flatten(t)
def flatten(x), do: [x] # 非リストの平坦化は、非リストのリスト化？！
end
そして、かなり遠回りしつつ、自力で flatten の定義を絞り出したのでした。
# Elixir の標準モジュールを使うように書き換えています。
defmodule Nested do
def flatten(list) do
_flatten(list)
|> Enum.reverse()
end
defp _flatten(list) do
List.foldl(list, [], fn x, acc ->
case is_list(x) do
true -> _flatten(x) ++ acc
false -> [x|acc] # 非リストになったら累積する
end
end)
end
end
宣言的にではなく、操作的に見ればよかったのだと〆ました。
操作的表現力を高める
以下の様なインターフェースだったら、リストしか受け取れないので、
もう少し早く理解できていたかもしれません。
defmodule Flatten do
def first(list) when is_list(list), do: _first(list)
def _first([]), do: []
def _first([h|t]), do: _first(h) ++ _first(t)
def _first(x), do: [x] # データはリストの先頭からやってくる
def last(list) when is_list(list), do: _last(list, [])
defp _last([], acc), do: acc
defp _last([h|t], acc), do: _last(h, _last(t, acc))
defp _last(x, acc), do: [x|acc] # データはリストの末尾からやってくる
end
左？右？
Flatten.first/1 の内部には右結合な ++/2 があります。
Flatten.last/1 の内部では _right(h, _right(t, acc)) となっているので、
どちらも畳み込みの観点からすると、右畳み込みで処理されています。
一次元リストの平坦化？
一次元リストの反転関数の定義はこうでした。
defmodule Linear do
def reverse([]), do: []
def reverse([h|t]), do: reverse(t) ++ [h] # 左畳み込み
end
これを踏まえると、一次元リストの平坦化の定義はこうなるでしょう。
defmodule Linear do
def flatten([]), do: []
def flatten([h|t]), do: [h|flatten(t)] # 右畳み込み
end
0..9
|> Enum.into([])
|> Linear.flatten()
|> IO.inspect() # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Linear.flatten/1 と Ex.flatten/1 を見比べると、
多次元リストに対するパターン分けが見えてきます。
この２つの flatten をモジュールとして以下にまとめました。
Flatten モジュール
defmodule Flatten do
# Linear.flatten/1 と等価
def linear([]), do: []
def linear([h|t]), do: [h|linear(t)] # 右畳み込み
# Ex.flatten/1, Flatten.first/1 と等価
def nested(list) when is_list(list), do: _nested(list)
defp _nested([]), do: []
defp _nested([h|t]), do: _nested(h) ++ _nested(t) # 右畳み込み
defp _nested(x), do: [x]
end
これを眺めていたら、
前回の Nested モジュールの foldl 無し版を定義できるようになりました。
Reverse モジュール
defmodule Reverse do
# 一次元リスト用
def linear([]), do: []
def linear([h|t]), do: linear(t) ++ [h] # 左畳み込み
# 多次元リスト用
def nested([]), do: []
def nested([h|t]), do: nested(t) ++ [nested(h)] # 左畳み込み
def nested(x), do: x
# 多次元リスト用＆平坦化
def flatten([]), do: []
def flatten([h|t]), do: flatten(t) ++ flatten(h) # 左畳み込み
def flatten(x), do: [x]
end
[1, [2, [3], 4], 5]
|> Reverse.flatten()
|> IO.inspect() # => [5, 4, 3, 2, 1]
Mapping モジュール
defmodule Mapping do
def linear([], _fun), do: []
def linear([h|t], fun), do: [fun.(h)|linear(t, fun)] # 右畳み込み
def nested([], _fun), do: []
def nested([h|t], fun), do: [nested(h, fun)|nested(t, fun)] # 右畳み込み
def nested(x, fun), do: fun.(x)
def flatten([], _fun), do: []
def flatten([h|t], fun), do: flatten(h, fun) ++ flatten(t, fun) # 右畳み込み
def flatten(x, fun), do: [fun.(x)]
end
[1, [2, [3], 4], 5]
|> Mapping.flatten(fn n -> n * 2 end)
|> IO.inspect() # => [2, 4, 6, 8, 10]
Filter モジュール
defmodule Filter do
def linear([], _pred), do: []
def linear([h|t], pred) do
case pred.(h) do # 右畳み込み
true -> [h|linear(t, pred)]
false -> linear(t, pred)
end
end
def nested([], _pred), do: []
def nested([h|t], pred) do # 右畳み込み
case x = nested(h, pred) do
nil -> nested(t, pred)
_ -> [x|nested(t, pred)]
end
end
def nested(x, pred) do
if pred.(x) do x else nil end
end
def flatten([], _pred), do: []
def flatten([h|t], pred) do
flatten(h, pred) ++ flatten(t, pred) # 右畳み込み
end
def flatten(x, pred) do
if pred.(x) do [x] else [] end
end
end
[1, [2, [3], 4], 5]
|> Filter.flatten(fn n -> rem(n, 2) == 0 end)
|> IO.inspect() # => [2, 4]
気持ち悪さには拍車がかかっていた
以下の２つの二重再帰関数を見比べてみてください。
defmodule Ex do
def fibo(0), do: 0
def fibo(1), do: 1
def fibo(n), do: fibo(n-2) + fibo(n-1)
def flatten([]), do: []
def flatten([h|t]), do: flatten(h) ++ flatten(t)
def flatten(x), do: [x]
end
Ex.fibo/1 にアキュムレータを導入すると、末尾再帰に変換できるのでした。
defmodule Acc do
def fibo(n), do: _fibo(n, {0, 1})
defp _fibo(0, {acc, _bcc}), do: acc
defp _fibo(n, {acc, bcc}), do: _fibo(n-1, {bcc, acc+bcc})
end
これなら Ex.flatten/1 も末尾再帰にできそうだと思い試行錯誤しましたが、
やはり以下のものしか思いつかず、末尾再帰になりません。
defmodule Acc do
# Flatten.last/1 と等価
def flatten(list), do: _flatten(list, [])
defp _flatten([], acc), do: acc
defp _flatten([h|t], acc), do: _flatten(h, _flatten(t, acc))
defp _flatten(x, acc), do: [x|acc]
end
何故だろうと色々考えてみたところ、
扱ってるデータ型の性質が違うということにやっと気づきました。
fibo/1 で扱ってるのは整数です。整数は内部に整数を持てません。
これは、一次元リストに対する二重再帰の処理と同じ意味だったんですね。
継続渡しスタイル（CPS）
今回は詳しく説明はしませんが、CPS なら末尾再帰にできます。
defmodule CPS do
# Flatten.first/1 の CPS 版
def flatten1(list), do: _flatten1(list, &(&1))
defp _flatten1([], cont), do: cont.([])
defp _flatten1([h|t], cont) do
_flatten1(h, fn x ->
_flatten1(t, fn y -> cont.(x ++ y) end)
end)
end
defp _flatten1(x, cont), do: cont.([x])
# Flatten.last/1 の CPS 版
def flatten2(list), do: _flatten2(list, [], &(&1))
defp _flatten2([], acc, cont), do: cont.(acc)
defp _flatten2([h|t], acc, cont) do
_flatten2(t, acc, fn x ->
_flatten2(h, x, fn y -> cont.(y) end)
end)
end
defp _flatten2(x, acc, cont), do: cont.([x|acc])
end
定義内の cont にクロージャとして継続が次々に積み上げられていきます。
継続とは「未評価なプログラム」「次に評価されるべき計算」です。
どちらの flatten でも最初に継続として恒等関数 &(&1) が渡され、
内部でプライベート関数を呼び出しています。
&(&1) は fn x -> x end と等価な無名関数です。
これは、
「平坦化の処理が済んだら、その値を単に返すという継続を実行する」
ということです。
難しいですね。継続の概念が普遍的過ぎて逆に難しいのです。
四則演算は知ってるけど、ならば「数とは？」「計算とは？」と尋ねられてるようなものです。
これで末尾再帰になったわけですが、スタックを消費しない代わりに、
クロージャによりヒープ領域を消費することになってしまいました。
とりあえず今回はこの辺にしておきましょう。
終わりに
平坦化 flatten の定義があまりにもエレガント過ぎて理解に時間がかかったわけですが、
お蔭で、一般化の重要さ、操作的観点の大切さが改めて実感できました。
にしても、疲れた。