グッドスタイン数列
最近、計算可能性とか不完全性定理とかについて勉強しています。その中でグッドスタイン数列というのが出てきて、これを Haskell で書いてみようと思いました。
遺伝的記述をリストで表現しようとしていて、値と遺伝的記述を変換する関数を書きたいのですが、どのように型 Gen を定義すればエラーにならないのかが分かりません。
→とか何とかやっていたら、動くようになったみたいです。
data Gen = G [Gen] instance Show Gen where show (G x) = show x main = do print $ goodstein 3 print $ take 10 $ goodstein 4 goodstein :: Integer -> [Integer] goodstein = takeWhile (> 0) . map snd . iterate next . (,) 2 next :: (Integer, Integer) -> (Integer, Integer) next (e, n) = (e + 1, num (e + 1) (gen e n) - 1) gen :: Integer -> Integer -> Gen gen e 0 = G [] gen e n = G (x : xs) where i = floor $ (log $ fromIntegral n) / (log $ fromIntegral e) x = gen e i G xs = gen e (n - e ^ i) num :: Integer -> Gen -> Integer num e (G []) = 0 num e (G (x:xs)) = (e ^ num e x) + num e (G xs)
ちなみに Common Lisp で書くとこんな感じです。iterate とか unfoldr があれば、このまま Lisp で書くのが早そうなんですが。
(defun gen (e n) (if (/= n 0) (let ((i (truncate (log n e)))) (cons (gen e i) (gen e (- n (expt e i))))))) (defun num (e lst) (if lst (+ (expt e (num e (car lst))) (num e (cdr lst))) 0)) ; 5 = 2^(2^(2^0)) + 2^0 -> (((0)) 0) (gen 2 5) (((nil)) nil) ; 16 = 3^(3^0 + 3^0) + 3^(3^0) + 3^(3^0) + 3^0 -> ((0 0) (0) (0) 0) (gen 3 16) ((nil nil) (nil) (nil) nil) (num 2 '(((())) ())) 5