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

# 概要

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

- [flatten 関数が理解できなかった その１](https://qiita.com/feelinguy/items/43bfeebec63b63a51847)

# リスト操作関数の一般化

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

```elixir: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: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: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: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: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: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 関数が理解できなかった その３](https://qiita.com/feelinguy/items/cc3943684ba8ced15b49)