「コラッツの予想」をElixirで書いて無限ループさせてしまった

備忘。初歩的なミスをしたので、戒めのために記録。

Twitter上でコラッツの予想（正しくは『コラッツの問題』？）に関する話を見かけて、「この問題の式を各種言語で書いてみるか。とりあえず、最初はElixirから書いてみよう」と思ったのがきっかけ。

それで、タイトル／冒頭に書いた通りに、初歩的なミスで無限ループなコードを書いてしまった。

無限ループには直接は関係ないけど、念の為バージョンは記述しておく。

erlang: 22.0.4
elixir: 1.9.0-otp-22

コラッツの予想とは

以下、Wikipediaからの引用。
コラッツの予想（または、コラッツの問題）の概要は以下の通り。

コラッツの問題は、「任意の正の整数 n をとり、 n が偶数の場合、n を 2 で割る n が奇数の場合、n に 3 をかけて 1 を足すという操作を繰り返すと、どうなるか」というものである。「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する（そして 1→4→2→1 というループに入る）」という主張が、コラッツの予想である。

ja.wikipedia.org

たとえば、「5」を対象にしてみる。
最初の5は奇数なので「5 * 3 + 1 -> 16」となる。
次に16は偶数なので「16 / 2 -> 8」となる。
その次は「8 / 2 -> 4」、「4 / 2 -> 2」、と続く。
最後に「2 / 2 -> 1」で1となり終了である。

実装の検討

ポイントは以下の3点と認識。

1) 入力が"正の整数"であること
2) 引数nが偶数の場合、nを2で割る
3) 引数nが奇数の場合、n に 3 をかけて 1 を足す

ここで、一旦1)の「正の整数」の条件はわきに置いといて、2)と3)の実装を先にすることにした。*1

実装（無限ループ版）

で、深く考えずにパッと実装したのがこちら。
もちろん失敗版。なので、実行したら無限ループに突入。

defmodule MyMath do
  def collatz(0), do: IO.puts(0)
  def collatz(1), do: IO.puts(1)
  def collatz(n) do
    IO.puts(n)
    require Integer
    case Integer.is_odd(n) do
      true -> collatz(3 * n + 1)
      _ -> collatz( n / 2)
    end
  end
end

関数へ渡す引数がマイナス値の場合の対応は、一旦なし。
関数collatz/1では、引数に1が来れば「1」を出力して終わり。
1以外であれば、コンソールに値を出力した後で奇数か偶数で引数に渡す値を切り替えて、再帰処理とする。
なお、今回は「奇数」かどうかで判定することにした。奇数の判定には「Integer.is_odd/1」を利用した。

それと、引数が「0」時のマッチングした関数を書いているが、これは特に根拠なしで作成したもの。ある意味で直感的に「0のケースがあった方が良いかなぁ…」な感覚で程度で書いた。

それで、モジュール定義を書き終わり、MyMath.collatz(5)を実行して、無限ループに突入した。
以下、実行イメージ。

iex> MyMath.collatz(5)
5
16
8.0
4.0
2.0
1.0
0.5
0.25
0.125
〜中略〜
2.0e-323
1.0e-323
5.0e-324
0.0
0.0
0.0
〜以下、延々と0.0が続く〜

解説

では、なぜ無限ループになったかを解説。

まず、無限ループになった理由。
これは簡単で、常にcollatz(n)の部分がマッチして呼び出されてしまっていたから、です。
collatz(n)は再帰処理で書かれており、これが呼ばれている間はずっと処理を繰り返してしまいます。

では、常にcollatz(n)の部分がマッチしていたのは何故か？
これは、次の3点が関係しています。

1) n / 2 の出力結果が、整数（Integer）ではなく浮動小数点数（Float）になっていたから
2) パターンマッチで、1と1.0、0と0.0は、異なる値として認識されるから
3) Integer.is_odd/1が、引数が浮動小数点数の型だと、falseを返すから

商の求め方

「1) n / 2 の出力結果が、整数（Integer）ではなく浮動小数点数（Float）になっていたから」について。 Elixirでは、四則演算で「/」を使った除算の結果は浮動小数点数（Float）になります。
そんな初歩的なことを忘れてしまい、『nを2で割る』の式を「/」を使って記述してしまいました。

なお、対策としては、整数の商の値を算出する「div/2」を使います。

パターンマッチについて

「2) パターンマッチで、1と1.0、0と0.0は、異なる値として認識されるから」について。
型が違うので、パターンマッチではマッチしないのは当然です。
試しに、0と0.0をマッチさせようとすると、no matchが発生します。

iex> 0 = 0
0

iex> 0 = 0.0
** (MatchError) no match of right hand side value: 0.0

ここで、気をつけないといけない点が、比較演算子に置ける「同値性（==）」と「厳格な同値性（===）」の対応です。
Elixirでは、他の言語に比べて、型の違うもの同士を比較することができます。
ここで、整数と浮動小数点数も「==」と「===」で出力結果が異なります。

iex> 0 == 0.0
true

iex> 0 === 0.0
false

他の言語でイコールの比較に使われる「==」は、Elixirでは型が違っても同じ値として判定されます。
ここが、パターンマッチでも一致すると勘違いする要因になっていました。

補足: 0.0になった理由

無限ループになった際に「0.0」が延々と繰り返されていました。
これは、浮動小数点数の有効桁が関係してます。

書籍『プログラミングElixir』によると、浮動小数点数はIEEE754の倍精度だそうです。
16桁の正確さがあり、最大の指数でおよそ10の308乗まで表せるそうです。

実際の出力結果から見ると、「5.0e-324」あたりまではなんとか表現できるようですね。
これ以上小さい値を表現しようとすると、0.0となってしまうようですね。

値の奇数／偶数の判定について

『3) Integer.is_odd/1が、引数が浮動小数点数の型だと、falseを返すから』について。
奇数と偶数を判断するのにInteger.is_odd/1を利用しているが、この関数は引数に整数以外の型が来るとfalseを出力する。そのため、一度引数が浮動小数点数になると、常に偶数側の処理が行われるようになってしまう。

対策

結局のところ、引数が最初に偶数になった際に次のMyMath.collatz/1に渡される値が「浮動小数点数」になったのがきっかけでした。
そのため、MyMath.collatz/1に渡されてる引数の型が常に整数であるようにします。

具体的には、「n / 2」を「div(n, 2)」に変更します。

defmodule MyMath do
  def collatz(0), do: IO.puts(0)
  def collatz(1), do: IO.puts(1)
  def collatz(n) do
    IO.puts(n)
    require Integer
    case Integer.is_odd(n) do
      true -> collatz(3 * n + 1)
#      _ -> collatz( n / 2)
      _ -> collatz( div(n,2) )
    end
  end
end

実行結果はこうなりました。

iex> MyMath.collatz(5)
5
16
8
4
2
1
:ok

これだけで、関数に渡る引数は浮動小数点数にならないので、無限ループの発生は防げました。

ちなみに、残したままになってますが、最初の「collatz(0)」は要りません（笑

まとめ

除算方法とパターンマッチの勘違い。
この2つの初歩的なミスで、無限ループを引き起こしてしまいました。

恥ずかしい反面、もう一度基本的な部分を再確認するきっかけにもなりました。ブログを書くネタにもなったので、まぁ良しとしておきます。

*1:入力値は動作確認時に自分で調整できるため

みずりゅの自由帳

主に参加したイベントやソフトウェア技術／開発について記録しています