概要
flatten 関数への旅路。やっと多次元リストについてです。
前回までの成果を Linear モジュールとして再掲しておきます。
defmodule Linear do
def list?([]), do: true
def list?([_|t]), do: list?(t)
def list?(_), do: false
def foldl([], acc, _fun), do: acc
def foldl([h|t], acc, fun), do: foldl(t, fun.(h, acc), fun)
def foldr([], acc, _fun), do: acc
def foldr([h|t], acc, fun), do: fun.(h, foldr(t, acc, fun))
# 一般的な言語では、
# 以下に示す関数群は左畳み込みで実装されていると思います。
def reverse(list) when is_list(list) do
foldl(list, [], fn x, acc -> [x|acc] end)
end
def map(list, fun)
when is_list(list) and is_function(fun, 1) do
foldl(list, [], fn x, acc -> [fun.(x)|acc] end)
|> reverse()
end
def filter(list, pred)
when is_list(list) and is_function(pred, 1) do
foldl(list, [], fn x, acc ->
if pred.(x) do [x|acc] else acc end
end)
|> reverse()
end
def concat(list1, list2)
when is_list(list1) and is_list(list2) do
reverse(list1)
|> foldl(list2, fn x, acc -> [x|acc] end)
end
end
ちなみに、Elixir のガード節（when）に置ける式は制限されています。
ガード節に置ける述語は is_ が前置されているものです。
したがって、自前で定義した Linear.list?/1 はガード節には置けません。
ガード節に置ける式のリストは以下で確認できます。
Kernel -> Guards
多次元（入れ子）リスト
何かについて考察したいときは、まず述語を作ることにしています。
多次元リストであるということは「リストの要素の何れかがリスト」であるものですね。
とすると、こんな述語があると便利だなと思いつきます。
- リストの全ての要素は○○か？
- リストの何れかの要素は○○か？
述語の追加
「全てが○○」＝「１つでも非○○があればダメ」
「何れかが○○」＝「１つでも○○があれば良し」
ということは foldl/3 foldr/3 の様に、全要素を探索する必要はないということですね。
defmodule Linear do
def all?([], _pred), do: true
def all?([h|t], pred) do
case pred.(h) do
true -> all?(t, pred)
false -> false # break!
end
end
def any?([], _pred), do: false
def any?([h|t], pred) do
case pred.(h) do
true -> true # break!
false -> any?(t, pred)
end
end
end
IO.inspect Linear.all?([], &is_integer/1) # => true
IO.inspect Linear.any?([], &is_integer/1) # => false
IO.inspect Linear.all?([1, 2, 3], &is_integer/1) # => true
IO.inspect Linear.any?([1, 2, 3], &is_integer/1) # => true
IO.inspect Linear.all?([1, :b, 3], &is_integer/1) # => false
IO.inspect Linear.any?([1, :b, 3], &is_integer/1) # => true
空リストに対する all?/2 に違和感を憶えますが Enum.all?/2 もこれと等価になってます。
多次元リストの仕様
defmodule Nested do
def list?(list) do
list
|> Linear.any?(&Linear.list?/1)
end
end
IO.inspect Nested.list? [] # => false
IO.inspect Nested.list? [1, 2, 3] # => false
IO.inspect Nested.list? [1, [2], 3] # => true
IO.inspect Nested.list? [[]] # => true
述語があると、仕様がハッキリしますね。
リバース
一次元リストのときに reverse/1 が大活躍したので、
多次元リストの場合も反転させることからやってみましょう。
例えば、[1, [2, [3], 4], 5] -> [5, [4, [3], 2], 1] になるように。
defmodule Nested do
def reverse(list) do
Linear.foldl(list, [], fn x, acc ->
case Linear.list?(x) do
true -> [reverse(x)|acc]
false -> [x|acc]
end
end)
end
end
IO.inspect Nested.reverse [] # => []
IO.inspect Nested.reverse [1, 2, 3] # => [3, 2, 1]
IO.inspect Nested.reverse [1, [2, [3], 4], 5] # => [5, [4, [3], 2], 1]
これぞ一般化の為せる技ですね。
fold 関数が無かったら、どう定義したものかと途方に暮れます。
これならマップ＆フィルターもいけそうです。
マップ＆フィルター
defmodule Nested do
def map(list, fun) do
_map(list, fun)
|> reverse()
end
defp _map(list, fun) do
Linear.foldl(list, [], fn x, acc ->
case Linear.list?(x) do
true -> [_map(x, fun)|acc]
false -> [fun.(x)|acc]
end
end)
end
def filter(list, pred) do
_filter(list, pred)
|> reverse()
end
defp _filter(list, pred) do
Linear.foldl(list, [], fn x, acc ->
case Linear.list?(x) do
true -> [_filter(x, pred)|acc]
false -> if pred.(x) do [x|acc] else acc end
end
end)
end
end
[0, [1, [2], 3], 4, 5, [6, [7], 8], 9]
|> Nested.map(fn n -> n * 100 end)
|> IO.inspect() # => [0, [100, [200], 300], 400, 500, [600, [700], 800], 900]
[0, [1, [2], 3], 4, 5, [6, [7], 8], 9]
|> Nested.filter(fn n -> rem(n, 2) == 0 end)
|> IO.inspect() # => [0, [[2]], 4, [6, [], 8]]
おお、できましたね。このフィルターに需要があるか疑問ですが。
一次元リストのときはこの後 concat/2 を定義したわけですが、
多次元リスト同士の連結って何だ？と考えてみると、
concat([1, [2], 3], [4, [5], 6]) -> [1, 2, 3, 4, 5, 6] ですねよ、きっと。
え？ [1, [2], 3, 4, [5], 6] じゃないかって？（無視
やっときましたね。
今ここに flatten/1 を欲するときが。
平坦化
defmodule Nested do
def flatten(list) do
_flatten(list)
|> reverse() # すでに平坦化済みなので Linear.reverse/1 でも可
end
defp _flatten(list) do
Linear.foldl(list, [], fn x, acc ->
case Linear.list?(x) do
true -> _flatten(x) ++ acc # Linear.concat/2
false -> [x|acc]
end
end)
end
end
[0, [1, [2], 3], 4, 5, [6, [7], 8], 9]
|> Nested.flatten()
|> IO.inspect() # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
なるほど、そういうことですよね。
でもね、
defmodule Ex do
def flatten([]), do: []
def flatten([h|t]), do: flatten(h) ++ flatten(t)
def flatten(x), do: [x]
end
エレガント過ぎでしょー。
初っぱなでこれ見せられてもわかりませんて。
何が気持ち悪かったのか？
関数型言語を学ぶとき、前回までの流れの内に flatten がやってくることが多いと思います。
すると、私の場合ですが def flatten(x), do: [x] を見てこう読んでしまうのです。
「リスト以外のものの平坦化とは、それをリスト化したものである」
はあ？ってなってしまうのです。
実際はこう読めばよかったのです。
「リスト以外のものを受け取ったら、リスト化してもよい」
宣言的ではなく、操作的に読めばよかったのです。
Ex.flatten/1 にアキュムレータを導入すると操作的表現力が増します。
defmodule Flatten do
# Ex.flatten/1 と等価
def first([]), do: []
def first([h|t]), do: first(h) ++ first(t)
def first(x), do: ( IO.inspect(x); [x] )
# アキュムレータ版
def last(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: ( IO.inspect(x); [x|acc] ) # 非リストになったら累積する
end
nested = [1, [2, [3], 4], 5]
IO.puts "--- Flatten.first/1 ---"
nested
|> Flatten.first()
|> IO.inspect()
IO.puts ""
IO.puts "--- Flatten.last/1 --- "
nested
|> Flatten.last()
|> IO.inspect()
> elixir flatten.exs
--- Flatten.first/1 ---
1
2
3
4
5
[1, 2, 3, 4, 5]
--- Flatten.last/1 ---
5
4
3
2
1
[1, 2, 3, 4, 5]
終わりに
どんなに宣言的に考えようとも、
実際に地べたはコンピュータという操作的なものだったと思い知るときがきます。
Prolog を書いているときに陥る状況になっていたんですね。
Elixir を書く人で Prolog 未経験の人は是非どうぞ。きっと楽しいですよ。
Ruby じゃないです、Prolog です。
次回
終わりませんでした。