tkykmw code

学びたいことを学ぶ

アンダースタンディング コンピュテーション 6.1.11.2 再帰なしRANGEの弱点

本文には書いていない点。

再帰なしのMODが0除算に対して異なる結果を返すのと同じように、再帰なしのRANGEも元と異なる結果を返す場合がある。

値の範囲の大小を入れ替えた場合、再帰版は空のリストを返すのに対し、再帰なし版は終端の値を含む要素1のリストを返す。

expect(to_integer_array(RANGE_WITH_RECURSION[ONE][ZERO])).to eq([])
expect(to_integer_array(RANGE_WITHOUT_RECURSION[THREE][ONE])).to eq([1])

m > n のとき SUBTRACT[n][m] が0になり、それをINCREMENTして実行するので、最低でも1回は呼び出されてしまうため。

回避したかったら、最初に大小チェックするのが一番簡単なのかな?

NOT = -> b { IF[b][FALSE][TRUE] }
IS_GREATER_THAN = -> m { -> n { NOT[IS_LESS_THAN_OR_EQUAL[m][n]] } }

RANGE_WITHOUT_RECURSION = -> m { -> n {
  IF[IS_GREATER_THAN[m][n]][
    EMPTY
  ][
    LEFT[
      INCREMENT[SUBTRACT[n][m]][COUNTDOWN][PAIR[EMPTY][n]]
    ]
  ]
}}