Problem 123
日本語訳

注意

この記事はProblem 123の解答を含みます。

最初に書いた解答

import Data.Numbers.Primes  

r n = mod (2 * p * n) (p * p)                                                           
  where                                                                      
    p = primes !! n                                                          

head $ filter (\n -> (r n > 10 ^ 10) && 1 == mod n 2) [1..]

これで解けるはずだが終わらない。
primes !! nを用いて素数を取り出している。

次に書いた解答

import Data.Numbers.Primes

r p n = mod (2 * p * n) (p * p)

snd $ head $ filter (\(p, n) -> (r p n > 10 ^ 10) && 1 == mod n 2) $ zip primes [1..]

これは間に合う。
primesを最初から一つずつ取り出している。

何が言いたいのか

Data.Numbers.Primesでどのような実装でprimesを作っているのかは知らないが、少なくとも$n$番目の素数を求めておけば、$n+1$番目の素数を求める計算量は少なくなるはずである。
ただ、はじめに書いたコードでは、$n+1$番目の素数を求める際に、すでに計算したはずの$n$番目の素数までを再び計算してるから遅いのだろう。

では、２つ目の解答の場合はどうなのかというと、これはzipを用いてprimesから一つずつ素数を取り出している。
このときは、$n+1$番目の素数を取り出す際に、$n$番目の素数までの計算を再び行うという無駄なことはせずに、計算出来ているんだと思う。

この違いはどこにあるんだろうか？
また、このような違いをHaskellを書いてる人が意識する必要があるのだろうか？？

Haskellの難しさ

「Haskell メモ化」で調べるとフィボナッチ数列を例として、コンパイラがどのような条件でメモ化をしているのかを解説する記事や具体的なメモ化の方法が出てくる。(参考)
また、他にも並列化の時などはHaskellの遅延評価がどのようなときにどの式の計算を行うのかをきちんと理解しないといけない。(参考, 参考)
Haskellは純粋関数型言語だから関数の定義を書いてるだけで計算が出来る。
ただ、このようにメモ化や計算の順番については、定義を書いてるだけなゆえに意識するのが難しくなっていると思う。
こんなこともわからないお前がザコなんだと言われれば謝るしかないが、難しいことを意識せずに楽しくプログラミング出来ないのかな。