Help us understand the problem. What is going on with this article?

Project Eular Problem 123を解いてて思ったHaskellの難しさ

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$番目の素数までを再び計算してるから遅いのだろう。

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

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

Haskellの難しさ

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした