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

# 概要

`flatten` 関数への旅路。やっと多次元リストについてです。

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

前回までの成果を `Linear` モジュールとして再掲しておきます。

```elixir:Elixir
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](https://hexdocs.pm/elixir/master/Kernel.html#guards)

# 多次元（入れ子）リスト

何かについて考察したいときは、まず述語を作ることにしています。
多次元リストであるということは「リストの要素の何れかがリスト」であるものですね。
とすると、こんな述語があると便利だなと思いつきます。

- リストの全ての要素は○○か？
- リストの何れかの要素は○○か？

## 述語の追加

「全てが○○」＝「１つでも非○○があればダメ」
「何れかが○○」＝「１つでも○○があれば良し」

ということは `foldl/3` `foldr/3` の様に、全要素を探索する必要はないということですね。

```elixir:Elixir
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` もこれと等価になってます。

## 多次元リストの仕様

```elixir:Elixir
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]` になるように。

```elixir:Elixir
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` 関数が無かったら、どう定義したものかと途方に暮れます。
これならマップ＆フィルターもいけそうです。

## マップ＆フィルター

```elixir:Elixir
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` を欲するときが。

## 平坦化

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

なるほど、そういうことですよね。
でもね、

```elixir:Elixir
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` にアキュムレータを導入すると操作的表現力が増します。

```elixir:flatten.exs
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()
```

```:Shell
> 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 です。

# 次回

終わりませんでした。

- [flatten 関数が理解できなかった 追試](https://qiita.com/feelinguy/items/49b6ea264b5b6952a737)