Happy number
Happy numbers - Rosetta Code から
Happy number とは次のようなものらしい。
- その数の各桁の平方和が 1 になれば Happy
- ならない場合は再帰して調べる
- 各桁の平方和が 4 になると循環するので Happy ではない
例) 79 は 49+81=130 -> 1+9+0=10 -> 1 なので Happy
Groovy のコードはなかったので Haskell だけ引用
Haskell
import Data.Char (digitToInt) import Data.Set (member, insert, empty) isHappy :: Integer -> Bool isHappy = p empty where p _ 1 = True p s n | n `member` s = False | otherwise = p (insert n s) (f n) f = sum . map ((^2) . toInteger . digitToInt) . show main = mapM_ print $ take 8 $ filter isHappy [1..]
これを Groovy に書き換える。
Happy でない場合はサイクルするかどうかで判定するのだが、その場合は 4 になるらしい*1ので実装上簡単な 4 で判定する。
まずは判定部分
// n が Happy number か判定する isHappy = { n -> n == 1 ? true : n == 4 ? false : call(sumsq(n)) } // n の各桁の平方和を求める sumsq = { n, sum = 0 -> n ? call(n.intdiv(10), sum+((n%10)**2)) : sum }
今回は Haskell 同様、無限リストを使って実装してみる。
from = { i -> [next: { i++ }] as Iterator }
filter = { f -> { xs -> [next: { [xs.next()].find(f) ?: call() }] as Iterator } }
take = { n -> { xs -> n ? [xs.next(), *take(n-1)(xs)] : [] } }
assert [1, 7, 10, 13, 19, 23, 28, 31] == take (8) (filter (isHappy) (from(1)))
イテレータは無限ループなので hasNext は true しか返さないし、remove は使わないので実装しなかった。
参考：Groovyならインタフェースはクロージャとマップで実装できる - No Programming, No Life
複数のメソッドを持つ場合は Map を使えばいいみたいだ。asType の実装を見てみたらインターフェイスにキャストする場合の親クラスである ConversionHandler は JParsec の作者の Ben Yu 氏が author だったので驚いた。*2
遅延評価とコールバック
『プログラミング Haskell』を読み終わったので考えたことをまとめておくと遅延評価のメリットの1つは自動的にコールバックになることだと思う。
10章までは問題なかったが 11章の切符番号遊びを Haskell から Groovy に直訳すると結果が返ってこない。これは組合せの爆発によって膨大な要素を持つリストを生成してしまうためだ。すべて生成してから処理ではなく各要素毎に処理すれば結果は返ってくる。Haskell のコードを見ると内部イテレータのように見えるが遅延評価を行わない Groovy では実は for に相当する処理だった。コールバック方式で書いてみる。
def count = 0 def callback = { n -> println n ++count < 8 } for (n = 1; ; n++) if (isHappy(n)) if (!callback(n)) break
Haskell と比べると count などの問題の本質ではない変数が必要になるというだけだった。
では簡潔に書けるなら遅延評価でいいんじゃないのという話になるが、それはそれで最後まで評価されないので展開されたままメモリに存在することが問題になることがある。どちらも使う側が理解していなければならないことに変わりはないみたいだ。
for はリスト内包表記で書けるので Haskell に書き直してみる。
happy_numbers = [n | n <- [1..], isHappy n] where sumsq n sum = case n `divMod` 10 of (0, r) -> sum + r^2 (q, r) -> (sumsq q sum) + r^2 isHappy 1 = True isHappy 4 = False isHappy n = isHappy $ sumsq n 0 main = mapM_ print $ take 8 $ happy_numbers
2011-04-21 追記
出力を同じ形式にすると次のように書ける。
happy = { callback ->
for (n = 1; ; n++)
if (isHappy(n))
if (!callback(n)) break
}
list = []
happy { list << n; list.size() < 8 }
assert [1, 7, 10, 13, 19, 23, 28, 31] == list
でも関数を書く際は通常コールバックを書かないので、1行目と2行目を展開して記述する。
happy = { N ->
def list = []
def n = 1
while (list.size() < N) {
if (isHappy(n)) list << n // take
n++
}
list
}
assert [1, 7, 10, 13, 19, 23, 28, 31] == happy(8)
このあたりで遅延評価で記述するのに比べて柔軟性が失われてしまうのかな?
