flatten 関数が理解できなかった 追試

# 概要

`flatten` 関数の定義への気持ち悪さが何だったのか、以下にて述べました。

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

```elixir:Elixir
defmodule Ex do
  def flatten([]),    do: []
  def flatten([h|t]), do: flatten(h) ++ flatten(t)
  def flatten(x),     do: [x] # 非リストの平坦化は、非リストのリスト化？！
end
```

そして、かなり遠回りしつつ、自力で `flatten` の定義を絞り出したのでした。

```elixir:Elixir
# 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
```

宣言的にではなく、操作的に見ればよかったのだと〆ました。

# 操作的表現力を高める

以下の様なインターフェースだったら、リストしか受け取れないので、
もう少し早く理解できていたかもしれません。

```elixir:Elixir
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))` となっているので、
どちらも畳み込みの観点からすると、右畳み込みで処理されています。

# 一次元リストの平坦化？

一次元リストの反転関数の定義はこうでした。

```elixir:Elixr
defmodule Linear do
  def reverse([]),    do: []
  def reverse([h|t]), do: reverse(t) ++ [h] # 左畳み込み
end
```

これを踏まえると、一次元リストの平坦化の定義はこうなるでしょう。

```elixir:Elixir
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 モジュール

```elixir:Elixir
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 モジュール

```elixir:Elixir
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 モジュール

```elixir:Elixir
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 モジュール

```elixir:Elixir
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]
```

# 気持ち悪さには拍車がかかっていた

以下の２つの二重再帰関数を見比べてみてください。

```elixir:Elixir
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` にアキュムレータを導入すると、末尾再帰に変換できるのでした。

```elixir:Elixir
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` も末尾再帰にできそうだと思い試行錯誤しましたが、
やはり以下のものしか思いつかず、末尾再帰になりません。

```elixir:Elixir
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 なら末尾再帰にできます。

```elixir:Elixir
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` の定義があまりにもエレガント過ぎて理解に時間がかかったわけですが、
お蔭で、一般化の重要さ、操作的観点の大切さが改めて実感できました。
にしても、疲れた。