Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@feelinguy

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

More than 1 year has passed since last update.

概要

前回に引き続き 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

リスト操作関数に共通していることは、全ての要素を1つずつ見てゆき、
何かしらの操作を施すことによって、アキュムレータへと収束させることです。
この「収束させること」を、畳み込み・重畳などど表現し、
関数型言語では 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 の第3引数である fun/2 の引数についても、
「どうしてその並びなんですか?」と尋ねられれば、
一般的な答えは「この言語デザインを反映しています」となるでしょうか。

Elixir では、処理対象となるデータ型を第1引数に置くという暗黙の了解があります。
Elixir にはパイプライン演算子 |> があり、
この2項演算子は、1項目の値を、2項目の関数の第1引数に渡します。
この観点から fold(list, acc, fun) に合わせて、
fold/3 の第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 の記事も書けたらなと思います。

次回

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

1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?