flatten 関数が理解できなかった その２

概要

前回に引き続き flatten 関数への違和感の正体を探る旅路です。

• flatten 関数が理解できなかった その１

リスト操作関数の一般化

前回 reverse/1 map/2 filter/2 を定義して終わりました。

Elixir

defmodule Acc do
  def reverse(list), do: _reverse(list, [])
  defp _reverse([],    acc), do: acc
  defp _reverse([h|t], acc), do: _reverse(t, [h|acc])

  def map(list, fun), do: _map(list, fun, [])
  defp _map([],   _fun, acc), do: reverse(acc)
  defp _map([h|t], fun, acc), do: _map(t, fun, [fun.(h)|acc])

  def filter(list, pred), do: _filter(list, pred, [])
  defp _filter([],   _pred, acc), do: reverse(acc)
  defp _filter([h|t], pred, acc) do
    case pred.(h) do
      true  -> _filter(t, pred, [h|acc])
      false -> _filter(t, pred, acc)
    end
  end
end

リスト操作関数に共通していることは、全ての要素を１つずつ見てゆき、
何かしらの操作を施すことによって、アキュムレータへと収束させることです。
この「収束させること」を、畳み込み・重畳などど表現し、
関数型言語では fold reduce などど名付けられています。

畳み込み

ここでは fold と名付けることとし、この関数のインターフェースを考えると、
fold(list, acc, fun) という形であれば上手く定義できそうです。

Elixir

defmodule Reduce do
  def fold([],    acc, _fun), do: acc
  def fold([h|t], acc,  fun), do: fold(t, fun.(h, acc), fun)
end

なんだか天下り的な流れになってきて恐縮です。

ここで、fold/3 の引数の並びについて、
それと、fold/3 の第３引数である fun/2 の引数についても、
「どうしてその並びなんですか？」と尋ねられれば、
一般的な答えは「この言語デザインを反映しています」となるでしょうか。

Elixir では、処理対象となるデータ型を第１引数に置くという暗黙の了解があります。
Elixir にはパイプライン演算子 |> があり、
この２項演算子は、１項目の値を、２項目の関数の第１引数に渡します。
この観点から fold(list, acc, fun) に合わせて、
fold/3 の第３引数は fun.(head_of_list, acc) になるわけです。

reverse/1 map/2 filter/2 の再定義

Elixir

defmodule Reduce do
  def reverse(list) do
    fold(list, [], fn x, acc -> [x|acc] end)
  end

  def map(list, fun) do
    fold(list, [], fn x, acc -> [fun.(x)|acc] end)
    |> reverse()
  end

  def filter(list, pred) do
    fold(list, [], fn x, acc ->
      if pred.(x) do [x|acc] else acc end # case より見やすい？
    end)
    |> reverse()
  end
end

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
|> Reduce.map(fn n -> n * 100 end)
|> Reduce.filter(fn n -> rem(n, 3) == 0 end)
|> IO.inspect() # => [0, 300, 600, 900]

こうやって、自分で関数を定義してみると、
日頃お世話になっている標準モジュール関数群の表情が見えてきて面白いですね。

連結

前回 [...] ++ [...] は非効率だと述べました。
この ++/2 と等価な関数を定義してみましょう。

Elixir

defmodule Reduce do
  def concat(list1, list2) do
    reverse(list1)
    |> fold(list2, fn x, acc -> [x|acc] end)
  end
end

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

なるほど reverse/1 は大活躍ですね。
いやいや、結局は全て fold/3 でした。

reverse/1 は良しとして、
map/2 filter/2 などの定義から reverse/1 を除去できないものでしょうか。

右畳み込み

リストの先頭を左と見て、
その逆、一番右の要素から操作を適用することを考えます。

Elixir

defmodule Reduce do
  def foldr([],    acc, _fun), do: acc
  def foldr([h|t], acc,  fun), do: fun.(h, foldr(t, acc, fun)) # 非末尾再帰

  def map_r(list, fun) do
    foldr(list, [], fn x, acc -> [fun.(x)|acc] end)
  end

  def filter_r(list, pred) do
    foldr(list, [], fn x, acc ->
      if pred.(x) do [x|acc] else acc end
    end)
  end

  def concat_r(list1, list2) do
    foldr(list1, list2, fn x, acc -> [x|acc] end)
  end
end

Reduce.concat_r([0, 1, 2, 3, 4], [5, 6, 7, 8, 9])
|> Reduce.map_r(fn n -> n * 100 end)
|> Reduce.filter_r(fn n -> rem(n, 3) == 0 end)
|> IO.inspect() # => [0, 300, 600, 900]

リスト操作に関しては fold/3 よりも foldr/3 の方が相性がいいですね。
しかし foldr/3 は末尾再帰にはなっていないので最適化の恩恵は受けれません。
Elixir には List.foldl/3 List.foldr/3 が定義されています。

循環した話

末尾再帰にしたくてアキュムレータを導入。
左畳み込みでリスト操作すると反転処理が必要なので、右畳み込みを導入。
一周して非末尾再帰に戻ってきました。
しかし、一般化できたことが最大の成果です。

Elixir

defmodule Sample do
  def map([],   _fun), do: []
  def map([h|t], fun), do: [ fun.(h) | map(t, fun) ]                   # 非末尾再帰

  def map_r(list, fun), do: _map_r(list, [], fun) # 引数の並びを変え、アキュムレータを追加
  defp _map_r([],    acc, _fun), do: acc
  defp _map_r([h|t], acc,  fun), do: [ fun.(h) | _map_r(t, acc, fun) ] # 非末尾再帰

  def map_l(list, fun), do: _map_l(list, [], fun) # 引数の並びを変えています
  defp _map_l([],    acc, _fun), do: acc
  defp _map_l([h|t], acc,  fun), do: _map_l(t, acc ++ [fun.(h)], fun)  # 末尾再帰

  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))         # 非末尾再帰
end

末尾再帰にこだわるのであれば CPS（継続渡しスタイル）というものがあります。
機会があれば CPS の記事も書けたらなと思います。

次回

さて、一次元リストについては一般化できました。
次回は、多次元（入れ子）リストの操作についてやっていこうと思います。

• flatten 関数が理解できなかった その３