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

はじめに

Lisp、Prolog に魅せられ、小さな関数を写経し生きてきましたが、
なんだか理解しがたいものにリストの平坦化がありました。

Elixir

defmodule Ex do
  def flatten([]),    do: []
  def flatten([h|t]), do: flatten(h) ++ flatten(t)
  def flatten(x),     do: [x]
end

IO.inspect Ex.flatten []                  # => []
IO.inspect Ex.flatten [1, 2, 3]           # => [1, 2, 3]
IO.inspect Ex.flatten [1, [2, [3], 4], 5] # => [1, 2, 3, 4, 5]

恥ずかしながら、なぜこの定義で良いのかずっと理解できなかったのです。
理解できないよりも先行して、なんか気持ち悪いのです。
この気持ち悪さを解消するため、
少し遠回りしながら初心に返り、flatten に歩み寄っていこうと思います。

再帰的に考える

関数型言語には普通、再代入可能な変数が無く、
それゆえループ構文が無かったりします。
ですので、数学の教科書に出てくる諸々の定義と同じく、
再帰的に関数を定義すればループ構文いらないんですと言われます。（誰に？

階乗

そして必ずといっていいほど階乗関数が出てきます。

Elixir

defmodule Ex do
  def fact(0), do: 1
  def fact(n), do: n * fact(n-1)
end

for n <- 0..9 do # 内包表記で [0,1,2,3,4,5,6,7,8,9] を生成
 Ex.fact(n)
end
|> IO.inspect() # => [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

フィボナッチ数

次に多重再帰の例としてフィボナッチ数がやってきます。

Elixir

defmodule Ex do
  def fibo(0), do: 0
  def fibo(1), do: 1
  def fibo(n), do: fibo(n-2) + fibo(n-1)
end

for n <- 0..9, do: Ex.fibo(n)
|> IO.inspect() # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

連結リスト

なぜ関数型言語といえば、基本データ構造に必ず連結リストが用意されているのでしょうか。
それはこのデータ構造が再帰的に構築されているからです。

Elixir

defmodule Ex do
  def list?([]),    do: true
  def list?([_|t]), do: list?(t)
  def list?(_),     do: false
end

IO.inspect Ex.list? []        # => true
IO.inspect Ex.list? [1, 2, 3] # => true
IO.inspect Ex.list? 123       # => false

マッピング

再帰的に考えることに慣れてきたところで、
リスト内のデータを一括変換し、そのリストを返す関数を書きましょう。
すでに使った内包表記の関数版を作るということです。

Elixir

defmodule Ex do
  def map([],   _fun), do: []
  def map([h|t], fun), do: [ fun.(h) | map(t, fun) ]

  # 内包表記利用版
  def map_(list, fun) do
    for n <- list, do: fun.(n)
  end
end

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
|> Ex.map(fn n -> n * 2 end)
|> IO.inspect() # => [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

フィルター

お約束の順番です。
リストから所望のデータだけを集めたリストを返してもらうというやつです。

Elixir

defmodule Ex do
  def filter([],   _pred), do: []
  def filter([h|t], pred) do
    case pred.(h) do
      true  -> [ h | filter(t, pred) ]
      false -> filter(t, pred)
    end
  end
end

odd? = fn n -> rem(n, 2) == 1 end

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
|> Ex.filter(odd?)
|> IO.inspect() # => [1, 3, 5, 7, 9]

末尾呼出最適化

ここまで書いてきた再帰的関数の中で list?/1 だけが、
末尾呼出最適化の恩恵を受けます。

関数定義の中で、自身の再帰呼び出しが最終ステップにくるものを末尾再帰と呼びます。
関数が末尾再帰になっているということは、
自身の呼出以外に処理することは残っていないということなので、
手続き型言語のループや goto に書き換えることができます。
この書き換えを末尾呼出最適化といいます。

言語の処理系がこの最適化をしてくれるならば、
末尾再帰で定義された関数はスタックオーバーフローを起こしません。

アキュムレータ

末尾再帰でないものを末尾再帰に書き換えるにはどうすればよいのでしょうか。
まずは先の fact/1 を手続き型言語で定義してみましょう。

Python3

def fact(n):
  sum = 1
  for i in range(n, 1, -1):
    sum *= i
  return sum

この定義内の sum の様に、
演算結果を累積するものをアキュムレータと呼びます。
fact/1 においてはアキュムレータが１つあるとループで書けるようなので、
この観点を再帰関数に取り入れます。

Elixir

defmodule ExAcc do
  def fact(n), do: _fact(n, 1)
  defp _fact(0, acc), do: acc
  defp _fact(n, acc), do: _fact(n-1, acc*n)
end

プライベート関数 _fact/2 の第２引数をアキュムレータとし持ち回します。
再帰呼び出しが起こる度に第１引数はゼロに向かっていき、
晴れてゼロを迎えた折には、累積結果のアキュムレータが返されます。

フィボナッチもやってみましょう。

Python3

def fibo(n):
  a, b = 0, 1
  for _ in range(n):
    a = b
    b = a + b
  return a

二重再帰で定義したものは、アキュムレータも２つ使えばいいんですね。

Elixir

defmodule ExAcc 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

あと、マップ＆フィルターもやっておきましょう。

Elixir

defmodule ExAcc do
  def map(list, fun), do: _map(list, fun, [])
  defp _map([],   _fun, acc), do: acc
  defp _map([h|t], fun, acc), do: _map(t, fun, acc ++ [fun.(h)]) # 非効率

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

上記の acc ++ [...] は効率が悪いですね。
連結リストは先頭からしかデータを探索できないので、
再帰の度にこの連結処理をされるのはよろしくないです。

そこで、アキュムレータの先頭からデータを追加してゆき、
最終段階でひっくり返した方が早いなと考えるわけです。

そんなわけでリスト反転関数を自前で作ってみましょうか。

リバース

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

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
|> Acc.map(fn n -> n * 2 end)
|> Acc.filter(fn n -> n >= 10 end)
|> IO.inspect() # => [10, 12, 14, 16, 18]

なにやらリスト操作関数には一定のパターンがありますね。

次回

そういうわけで、次回はリスト操作関数の一般化をしてみます。

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