Life Goes On

まあまあだけど楽しんでる方です

グッドスタイン数列

最近、計算可能性とか不完全性定理とかについて勉強しています。その中でグッドスタイン数列というのが出てきて、これを 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