100万までの数の中で、最も長いコラッツ列を生成する数を求める
コラッツ列： cn が偶数なら cn+1 = cn/2, 奇数ならcn+1 = 3*cn+1 ... と続く数列
まずは素直に書いてみる。
これで答えは出る。ただし時間が掛かる。私のデスクトップで、答えが出るまで3分ちょっと待つことになった。もう少し効率化したい。
方向性が悩ましいが、一つ明らかに無駄な計算をしているのは、途中から同じ数列を辿るケースだ。例えば、13から始まるコラッツ列は
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
で長さ10を求めるために9ステップの計算が必要となる。同様に52から始まるコラッツ列の長さを求めるためには
52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
と11ステップの計算をしているが、13以降は同じステップを繰り返しているだけなので、もし13に辿り着いた時点で"この先の長さは9"という情報を返すことができれば、都合3ステップ（9を返す操作も1ステップと数えて）で事足りる。
さあ、そういう風に実装できるだろうか？
ここからはそれなりの勉強が必要だった。結果辿り着いた答えがベストなのかもよく分からない。苦労した割には、計算速度は5倍程度早くなるにとどまった。それでも一応早くはなったのと、Data.Mapの使い方に触れることができたのが収穫か。
関数のネーミングセンスには、今回も目をつむって欲しいところだが、collatz とcolseq という2つの関数を準備した。Map.Dataに格納する際、コラッツ列の起点となる数字をKey，コラッツ列の長さをValueとして、Table（型はMap.Map Key Value） にKey → Valueの対応を記憶して行く。
collatzの型は collatz :: Key -> Value -> Table -> (Value, Table) とややこしいが、Keyに対してValueを求める際に、計算の途中で出てきた他の数とコラッツ列の長さの対応を覚えて置くために、その記憶Tableを一緒に返してあげている。この辺はHaskellっぽさが出る。IOを使ってTableを外の世界に置いてやることも可能だが、純粋関数型の矜持に反する気がして気が進まない。collatzの実行例はこちら。
(10,fromList [(2,2),(4,3),(5,6),(8,4),(10,7),(13,10),(16,5),(20,8),(40,9)])
13から始まるコラッツ列の長さを計算したら、途中に出てきた数字にもコラッツ列の長さを紐付けてあげる。一見余計な仕事をして計算負荷を上げているように見えるが、関数colSeqでは、このfromListを引き継ぎながら1,2,3...と順番にコラッツ列の長さを計算することで、前に一度出てきた数に対する処理を省略することができるので、あとへ行くほど計算負荷が低くなる。若い時に苦労して経験を積むことで、歳を取ったら悩まずに仕事ができる…というのに似ている（そうか？）。
休日丸々潰してしまったが、もっと効率化できる気がする★
