하스켈 주요 테스트

Question

내가 하스켈에 새로 온 사람, 나는 조금을 시도하고있다 :

isPrime :: Integer->Bool 
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0]) 

나는 몇 가지 질문이 있습니다. 나는 .hs를로드 할 때

1. 왜, WinHugs 말 : (Floating Integer, RealFrac Integer)의 인스턴스가 isPrime의 정의에 필요한?
2. 해석기가 오른쪽 집합에서 하나의 요소를 찾으면 즉시 중단하거나 모든 집합을 계산합니까? 내 말이 무슨 뜻인지 알 것 같아.

영어로 죄송합니다.

Answer 1

1) 문제는 sqrt이 (Floating a) => a -> a 유형이지만 정수를 인수로 사용하려고합니다. 따라서 Integer를 먼저 Floating으로 변환해야합니다.

2 sqrt (fromIntegral x))를 작성하여 나는 == 게으른하지 않아야 할 이유를 볼하지만) 무한리스트에 작품으로 빈 콜렉션에 대한 테스트를 위해 당신은 확실히 게으른입니다 null 기능을 (사용할 수 있습니다

isPrime :: Integer->Bool 
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0] 

그러나 더 관용적 인 해결책을 얻으려면 문제를 더 작은 하위 문제로 나눕니다. 우선, Y의 *의 Y와 Y의 모든 요소의리스트를 필요 < = X :

filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..]) 

그렇다면 우리는 그리스트 있는지 확인해야

takeWhile (\y -> y*y <= x) [2..] 

그렇다면 우리는 X 분할 요소만을 필요

isPrime x = null (filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..])) 

그리고 이것은 당신에게 Lisp 다운을 보이는 경우, $

isPrime x = null $ filter (\y -> x `mod` y == 0) $ takeWhile (\y -> y*y <= x) [2..] 

0 괄호의 일부를 대체 : 비어 추가 설명을 위해

당신은 람다 "아웃소싱"할 수

이

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where 
    divisible y = x `mod`y == 0 
    notTooBig y = y*y <= x 

Answer 2

1. 는 sqrt 때문에 유형 Floating a => a -> a 있습니다. 즉, 입력은 Floating 유형이어야하며 출력은 동일한 유형이어야합니다. 즉, x은 Floating 유형이어야합니다. 그러나 x이 Integer 유형이고 Floating 유형이 아닌 것으로 선언했습니다. 또한 floor에는 RealFrac 유형이 필요하므로 x도 입력해야합니다.

   오류 메시지는 물론이의 인스턴스 Floating Integer (및 RealFrac에 대해 동일)를 정의하여 IntegerFloating 유형 (함으로써.

   이 경우에 올바른 방법이 아니라고 수정 제안합니다. 오히려 당신은 (Floating 및 RealFrac의 인스턴스 인)을 Real에 x 변환 fromIntegral를 사용하고 sqrt에 그를 제공해야합니다.

   는

2. 예. 즉시 ==가 보는대로 오른쪽 피연산자는을 가지고 적어도 하나의 요소는 []과 같지 않으므로 False을 반환합니다.

   즉, null은 목록이 [] ==보다 비어 있는지 확인하는 관용적 인 방법입니다. 두 번째 점에 대해서는

Answer 3

, 예를 들어, 중지 :

[] == [x | x <- [1..]] 

반환 False

Answer 4

1. 내가 WinHugs는 정수 등의 모듈을 가져올 필요하다고 생각 ... 지능 시도
2. 예를 들어 전화 할 때까지 통역사가 아무 것도 계산하지 않습니다. isPrime 32 그러면 표현식이 느리게 계산됩니다.

PS 귀하의 isPrime 구현은 최상의 구현이 아닙니다!

Answer 5

Landei의 솔루션입니다 : 어떤 $하지 null와 $ 필터를 교체하여

이

isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where 
    divisible y = x `mod`y == 0 
    notTooBig y = y*y <= x 

당신은 거의 "사람이 읽을 수있는"수를 그러나 더 효율적인 ¹ 구현을 원한다면 (BMeph에게 감사드립니다) :

-- list of all primes 
primes :: [Integer] 
primes = sieve (2 : 3 : possible [1..]) where 
    sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0] 
    possible (x:xs) = 6*x-1 : 6*x+1 : possible xs 

isPrime :: Integer -> Bool 
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where 
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0)) 
    divisible y = n `mod` y == 0 
    inRangeOf y = y * y <= n 

'효율성'은 다음과 같습니다. f rom 상수 소수의 사용. , 하스켈 런타임이 때문에 이후의 호출은 그것은 sieve 값이 단순히 재귀 테이블입니다 논리 참고로 숫자의 범위를 제거

을 평가하지 않는 결과를 캐시 할 수

1. : 그것은 두 가지 방법으로 검색을 향상 여기서 의 머리를 말하고 목록은 소수이며 그것을 추가합니다. 리스트의 나머지 부분에 대해 숫자를 구성하는리스트에 다른 값이 이미 존재하지 않으면 possible은 모든 가능한 소수가 형태 6 * k-1 또는 6에 있으므로 가능한 모든 소수의 목록입니다 * K-1 (2, 3) 것을 제외하고는 동일한 규칙이 적용된다 shortCircuit 너무 빨리 DF로

계산

에서 각주 구제
¹ 여전히 소수를 찾는 것은 대단히 비효율적 인 방법입니다. 수천을 넘는 소수가 필요하다면 시브 분열을 사용하지 말고 체를 대신 사용하십시오. far more efficient 개의 구현이 hackage에 있습니다.