Project Euler 80

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


昔習った平方根を1桁ずつ求める計算法をシミュレートする。
square_rootは平方根の精度が1桁ずつよくなるリスト。例えば、

square_root = [1, 14, 141, 1414, 14142, …]

その中のaは、余りと答えのタプルのリスト。

digits 0 = []
digits n = (digits (div n 10)) ++ [mod n 10]

square_root n = map snd (tail a) where
	a = (n, 0):[ next e | e <- a ]
	next (n,m) = last (takeWhile (\(n,_) -> n >= 0)
		[ ((n - d * (d + 20 * m)) * 100, m * 10 + d) | d <- [0..] ])

n = 100
m = 100
main = print (sum [ d | k <- [1..n], a <- [(square_root k)],
					d <- digits (a!!(m-1)), (head a)^2 /= k ])