220 Heighway Dragon

Problem 220 – Project Euler

ドラゴン曲線といえば，有名なフラクタル．

フラクタルの自己相似性をうまく利用． 

dragon :: Integer -> (Integer, Integer)
dragon  = (, )
dragon n = let (s, (x, y)) = until ((>= n).fst) step $ (1, (, 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