haskell-jp / questions #104 at 2023-10-05 16:57:13 +0900

Haskellの勉強がてら　コラッツ予想に取り組んでいます。
ご存知の方も多いと思いますが　自然数において
奇数の場合は　3倍して　1を足す
偶数の場合は　2で割る　を繰り返すと
1に収束するという予想です。

上記の条件を　奇数の場合に　3倍して　1を引く　とした場合には
1に収束しなくなり　下記のプログラムでは　止まらなくなります。
発散する場合は仕方ありませんが　1以外で収束する場合に　止まるようにしたいと考えています。

数列が　例えば　[2, 3, 4, 5]　まで形成され　次の数字が　今までに出現した数字の場合
（左記の場合は　2　3　4　5　のいずれか）になった場合に停止するように　プログラムしたいのですが
どうにもうまくいきません。

御指導いただければ助かります。
よろしくお願いします。


import Data.Char
import Data.List

type Nat = Integer

collatz :: Nat -> Nat
collatz n
| odd n = 3 * n + 1
| even n = div n 2

sequence :: Nat -> [Nat]
sequence n
| n == 1 = 1 : []
| otherwise = n : sequence (collatz n)

こういう時は再帰を行う関数に追加の引数を持たせると書きやすいことがよくあります。つまり、`sequence` 関数とは別に sequence' 関数を用意して、それに「これまでに出現した数のリスト」を追加の引数で渡すのです。イメージとしては

sequence' :: [Nat] -> Nat -> [Nat]
sequence' seen n  -- seenはこれまでに出現した数のリスト
  | 〈nがseenに含まれる場合〉 = []
  | otherwise = n : sequence' ({- 「すでに出現した数のリスト」に n を加える -} n : seen) (collatz n)

という感じで、追加の引数に初期値を与えて呼び出す関数を作ればそれが所望のものになります：

sequence :: Nat -> [Nat]
sequence = sequence' []

mod_poppoさん　ありがとうございます。早速試してみたいと思います。