하스켈은 어떤 종류의 최적화를 수행합니까?

Question

저는 하스켈 초보자입니다.하지만 요즘에는 소수의 과장이 많아서 많이 좋아합니다. (어느 쪽이 나를 바꿔 놓았 을까)

나는이 비교적 기본적인 스크립트를 가지고있다. 가능한 한 효율적이지 않더라도 정확하게 작동합니다. 그건 내 질문이 아니야. 여기 내 스크립트는 다음과 같습니다.

import System.Environment 


oddFactors p = [x | x<- [3,5..floor (sqrt (fromIntegral p))], p `mod` x == 0] 
prime x = oddFactors (2^x -1) == [] 

main = do 
    args <- getArgs 
    print (prime (read (head args) :: Int)) 

간단하게 말했습니다. oddFactors은 3에서 sqrt(p)까지의 홀수를 거쳐서 p의 요소이면 목록에 추가합니다.

primes2^x -1에 oddFactor을 호출하고 결과 목록이 빈 목록과 같은지 확인합니다.

이상한 점은 이미 최적화 된 것으로 보입니다. primes의 경우, 예를 들어, 61 일 경우, 프로그램 실행에 49 초가 걸리고 참을 리턴합니다. 내가 60이나 62를하면, 실행하는 데 .005 초가 걸리고 False를 반환합니다. 이것들은 올바른 반환 값입니다. 그러나리스트가 []가 될 수 없으므로 []과 일치하는리스트만을 찾고 나서 찾을 수 없다는 것을 알기 때문에 어떻게 든 최적화되면 궁금합니다.

Long 질문을 던졌지 만 지금까지는 내 코드에 대한 제안을 기꺼이 받아들이 려합니다. ;)

물론 나는 그런 밀러 - 라빈 같은 소수성 테스트로 더 나은 뭔가를 사용할 수 있습니다 알고 있지만 그 시점이 아니다 : 나는, 너무 좋은 :)

편집 일까지 약 2 시간 전 하스켈을 포착

Answer 1

테스트 list == []은 list의 빈 상태를 확인하는 데 필요한만큼만 list을 평가합니다. 기술적으로, list (: 또는 [] 일 수 있음)의 가장 바깥 쪽 생성자를 발견하는 데 필요한만큼, list을 약한 머리 정상형 (WHNF)으로 만드는 데 필요한만큼.

예를 들어, (error "hello" : error "world") == []은 error 표현을 평가하지 않고 False을 반환합니다.

이되는 표현의 결과 게으르게 평가하고 자연적인 방법으로 패턴 매칭을 사용하여 (==)의 정의 :

비교하여

[]  == []  = True 
[]  == _  = False 
_  == []  = False 
(x:xs) == (y:ys) = x==y && xs==ys 

, 정의는 다음

[]  == []  = True 
[]  == (y:ys) = []==ys && False 
(x:xs) == []  = xs==[] && False 
(x:xs) == (y:ys) = x==y && xs==ys 

를 있었다면하는 list == []있을 것입니다 False (또는보다 정확하게는 list spine)을 반환하기 전에 전체 목록의 계산을 강제했습니다.

Answer 2

하스켈은 느리게 함수 호출을 평가합니다. 즉, prime 60이라고 말하면 1152921504606846975의 홀수 요소를 찾으려고 시도 할 때 처음으로 == "전화"를 파악하려고합니다. 이것을 평가할 때는 == 정의로 내려갑니다. 빈 목록의 경우 하나 이상의 요소가 있는지를 파악하려고 시도합니다.이것이 사실이기 때문에

1152921504606846975 `mod` 3 == 0 

, 그것은 심지어는 목록의 나머지 부분을 평가하지 않는 경우에 따라서 효율적으로 만 평가 : 이미 False을 할 3:(stuff) == []을 알고 관계없이 (stuff)가 평가 수 무슨.

61을 전달하면 2305843009213693951이라는 홀수 인 수를 찾으려고 시도하는데, 이는 홀 목록 이해력을 확장해야 비어 있음을 알 수 있습니다. 그래서 오래 걸립니다.