Problem 220

220 Heighway Dragon
Problem 220 - Project Euler
ドラゴン曲線といえば，有名なフラクタル．
フラクタルの自己相似性をうまく利用．

dragon :: Integer -> (Integer, Integer)
dragon 0 = (0, 0)
dragon n = let (s, (x, y)) = until ((>= n).fst) step $ (1, (0, 1))
               (x', y') = dragon (s - n)
           in (x - y', y + x')
    where step (s, (x, y)) = (2 * s, (x + y, -x + y))

main :: IO ()
main = print.dragon $ 10^12