top page > computer > haskell > web_lecture > for_programmer > collatz.html
更新日:
文責: 重城良国

コラッツ数列

collatz.hs

コラッツの予想

コラッツの問題という未解決問題がある。「偶数のときは2で割り奇数のときは3倍して1を足す。これをくりかえすと必ず1になる。」これがコラッツの予想だ。証明も反証もされていない。現在のところ5 * 2 ^ 60(5,764,607,523,034,234,880)までの初期値で成り立つことが確認されている。

メモ: 五百七十六京四千六百七兆五千二百三十億三千四百二十三万四千八百八十

24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...

コラッツ数列

初期値からうえのルールで1になるまでの値の列をコラッツ数列と呼ぶ。

コラット数列の生成

  1. 初期値から上記のルールで無限数列を生成する
  2. 最初の1までをとりだす

最初の1までをとりだす

最初の1までをとりだすのに関数takeToを作成する。関数takeToは条件を表す関数とリストをとり条件を満たす値までをとりだす。

takeTo :: (a -> Bool) -> [a] -> [a]

第1引数は「条件」なのでa型の値をとりBool値を返す関数だ。第2引数はとりだし前のリストなので[a]だ。返り値はとりだされた値から成るリストなのでやはり[a]だ。

基底部

基底となるのは

のどちらかだ。空リストのときは結果も空リストとする。

takeTo _ [] = []

これは「もし条件を満たすものがなかったらリストの全体を返す」ということだ。「条件を満たすものがなかったらエラー」としたければここでエラー値を返すことになる。

リストの先頭の要素が条件を満たすときはそれ以降の要素は不要なので先頭要素ひとつから成るリストを返す。

takeTo p (x : xs)
| p x = [x]

再帰部

リストの先頭要素が条件を満たさないときは残りのリストから条件を満たすまでをとりだしてそれに先頭の要素を追加する。

| otherwise = x : takeTo p xs

出来上がり

takeTo _ [] = []
takeTo p (x : xs)
| p x = [x]
| otherwise = x : takeTo p xs

% ghci collatz.hs
*Main> takeTo even [3, 7, 9, 8, 5, 4, 2]
[3,7,9,8]

関数foldrを使う

次のような関数を考えてみよう。

fun x lst = if p x then [x] else x : lst

これを使って次のように書き換えられる。

takeTo p (x : xs) = fun x (takeTo p xs)
where
fun x lst = if p x then [x] else x : lst

わかるだろうか。わかりにくければ一度展開してみると良い。関数funを演算子とすると

takeTo p (x : xs) = x `fun` takeTo p xs

となる。すると関数takeToは以下のように書ける。関数の枠組みがわかりやすいようにあえて丸括弧を明示してある。

(takeTo p) [] = []
(takeTo p) (x : xs) = x `fun` (takeTo p) xs

takeTo pは[]を[]に置き換え、(:)をfunに置き換えている。

1 : 2 : 3 : 4 : []
-> 1 `fun` 2 `fun` 3 `fun` 4 `fun` []

これはfoldrの枠組みだ。関数funを展開してfoldrに与える。

takeTo p = foldr (\x lst -> if p x then [x] else x : lst) []

ポイントフリースタイル

\x lst -> if p x then [x] else x : lstは\x -> (\lst -> if p x then [x] else x : lst)だ。(\lst -> ...)の部分はもしxがpを満たせばlstの値を問わず[x]を返し、そうでないならlstの先頭にxを追加した値を返す。よって以下のようにできる。

\x -> if p x then const [x] else (x :)

[x]はx : []ということだ。(x :)の部分が重複している。ひとつにまとめよう。

\x -> (x :) . if p x then const [] else id

これを使ってtakeToを書くと以下のようになる。

takeTo p = foldr (\x -> (x :) . if p x then const [] else id) []

無駄な仮引数や重複がなくなった。

ポイントフリー狂

ここから先は禁断の地だ。ポイントフリーにこだわると以下のようになる。Control.Applicativeモジュールを使う。

takeTo = (`foldr` []) . ((.) <$> (:) <*>) . ((([id, const []] !!) . fromEnum) .)

うわぁぁぁぁぁ、Haskell恐い。ポイントフリーはほどほどにしないと嫌われてしまう。

無限数列を作る

仕様

与えられた自然数から始まりコラッツ数列のルールにしたがって次の数を生成することで無限数列を作成する。

整数をとって整数のリストを返す。

collatzInf :: Integer -> [Integer]

次を求める

関数collatzNextは与えられた値から次の値を求める。

collatzNext :: Integer -> Integer
collatzNext n
| even n = n `div` 2
| otherwise = n * 3 + 1

基底部

無限数列に基底部は存在しない。基底部は終了条件だ。終了条件が分離できるということだ。

再帰部

collatzInf n = n : collatzInf (collatzNext n)

nから始まるコラッツ数列はnの次の値から始まるコラッツ数列の先頭にnを追加したものだ。

出来上がり

collatzNext :: Integer -> Integer
collatzNext n
| even n = n `div` 2
| otherwise = n * 3 + 1

collatzInf :: Integer -> [Integer]
collatzInf n = n : collatzInf (collatzNext n)

関数iterate

collatzInf nによって作られるリストは以下のようになる。

[n, collatzNext n, collatzNext (collatzNext n), ...]

関数iterateはこのような形のリストを作成する関数だ。iterate f nは以下のようなリストを作成する。

[n, f n, f (f n), f (f (f n)), f (f (f (f n))), ...]

関数collatzInfは次のように書ける。

collatzInf = iterate collatzNext

展開する

collatzNextを展開しておく。

collatzInf = iterate $ \n -> if even n then n `div` 2 else n * 3 + 1

無限数列からコラッツ数列をとりだす

collatz :: Integer -> [Integer]
collatz = takeTo (== 1) . collatzInf

関数collatzInfで作成した無限数列から値1までをとりだしてた。

出来上がり

takeTo :: (a -> Bool) -> [a] -> [a]
takeTo p = foldr (\x -> (x :) . if p x then const [] else id) []

collatzInf :: Integer -> [Integer]
collatzInf = iterate $ \n -> if even n then n `div` 2 else n * 3 + 1

collatz :: Integer -> [Integer]
collatz = takeTo (== 1) . collatzInf

*Main> :reload
*Main> collatz 11
[11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

まとめ

無限リストを利用して値の生成と終了条件とを分離した。関数foldrや関数iterateを使えば直接的な再帰を使わずにすむ。

「整数の列挙」へもどる 「関数iterateの定義」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics