http://projecteuler.net/index.php?section=problems&id=175

前に似たような問題があった。

結論からいうとユークリッドの互除法のようなもの

import Data.List
step :: Integral a => (a,a) -> Maybe (a,(a,a))
step (p,q) | q ==  = Nothing
| p <= q = let (n,q') = divMod q p in Just (n,(p,q'))
| otherwise = let (n,p') = divMod p q
in if p' ==  then Just (n-1,(q,q)) else Just (n,(p',q))
main = putStrLn.init.tail.show.reverse.unfoldr step $ (123456789,987654321)