हास्केल प्रधानमंत्री परीक्षण

Question

मैं हास्केल के लिए नया हूँ, और मैं थोड़ा कोशिश कर रहा हूँ:

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

मैं कुछ प्रश्न हैं।

1. क्यों जब मैं .hs लोड करने का प्रयास, WinHugs कहते हैं: (Floating Integer, RealFrac Integer) के उदाहरण isPrime की परिभाषा के लिए आवश्यक है?
2. दुभाषिया सही सेट में एक तत्व होता है, तो इसे तुरंत बंद हो जाता है या इसे पूरी तरह से तैयार की गणना करता है? मुझे लगता है आपको पता है कि मेरा क्या आशय है।

मेरी अंग्रेजी के बारे में खेद है।

Answer 1

1) समस्या यह है कि sqrt में (Floating a) => a -> a है, लेकिन आप एक इंटीजर को तर्क के रूप में उपयोग करने का प्रयास करते हैं। तो आपको अपने इंटीजर को फ़्लोटिंग में पहले कनवर्ट करना होगा, उदा।sqrt (fromIntegral x)

2) लिख कर मैं कोई कारण नहीं क्यों == आलसी नहीं होना चाहिए देखते हैं, लेकिन एक खाली संग्रह के लिए परीक्षण के लिए आप, null समारोह (जो निश्चित रूप से आलसी है उपयोग कर सकते हैं के रूप में यह अनंत सूची पर काम करता है):

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

लेकिन अधिक मूर्खतापूर्ण समाधान प्राप्त करने के लिए, समस्या को छोटी उप-समस्याओं में विभाजित करें। सबसे पहले, हम y * y के साथ y सभी तत्वों की सूची की जरूरत < = एक्स:

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

फिर हम उस सूची अगर जांच करने की आवश्यकता:

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

फिर हम केवल तत्वों है कि एक्स विभाजित की जरूरत है रिक्त है:

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

और अगर यह आपके लिए lispy को लग रहा है, $

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

0 के साथ कोष्ठक में से कुछ की जगह अतिरिक्त स्पष्टता के लिए

आप lambdas "आउटसोर्स" कर सकते हैं:

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 प्रकार की जरूरत है। हालांकि आपने को Integer टाइप करने के लिए घोषित किया है, जो Floating प्रकार नहीं है। इसके अलावा floor, एक RealFrac प्रकार की जरूरत है ताकि x कि होने के लिए और साथ ही जरूरत है।

   त्रुटि संदेश को ठीक है कि उस Integer एक Floating प्रकार (बनाने एक उदाहरण Floating Integer (और RealFrac के लिए एक ही) को परिभाषित करते हुए द्वारा।

   पाठ्यक्रम इसमें से

   इस मामले में सही दृष्टिकोण नहीं है पता चलता है। बल्कि आप fromIntegral का प्रयोग कर एक Real को x कन्वर्ट करने के लिए (जो Floating और RealFrac का एक उदाहरण है) और फिर sqrt है कि दे।

2. हां। जैसे ही == देखता है के रूप में सही संकार्य एक है टी से कम एक तत्व है, यह जानता है कि यह [] के बराबर नहीं है और इस प्रकार False देता है।

   कहा जा रहा है कि, null यह जांचने के लिए एक और बेवकूफ तरीका है कि कोई सूची [] == से खाली है या नहीं।

Answer 3

दूसरी बात के बारे में

, यह बंद हो जाता है, उदाहरण के लिए:

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

रिटर्न False

Answer 4

1. मैं WinHugs पूर्णांक और आदि के लिए एक मॉड्यूल आयात करने के लिए की आवश्यकता है ... इंट का प्रयास करें
2. दुभाषिया कुछ भी गणना नहीं करेगा जब तक आप कॉल नहीं करते isPrime 32 तो यह अभिव्यक्ति की आलस्य की गणना करेगा।

पीएस आपका isPime कार्यान्वयन सबसे अच्छा कार्यान्वयन नहीं है!

Answer 5

Landei के समाधान है:

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

आप इसे लगभग "मानव पठनीय" कर सकते हैं किसी भी $ नहीं के साथ अशक्त $ फिल्टर की जगह बढ़िया, हालांकि, यदि आप एक और अधिक कुशल कार्यान्वयन चाहते हैं तो हमारे पास (बीएमएफ़ के लिए धन्यवाद):

-- 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 आता है निरंतर प्राइम्स का उपयोग रोम। ,

1. हास्केल क्रम परिणाम इतने बाद आमंत्रण मूल्यांकन नहीं किया जाता
2. यह तर्क टिप्पणी से संख्या की श्रेणी समाप्त कि sieve मूल्य केवल एक पुनरावर्ती तालिका है कैश सकता है: यह दो तरह से खोज को बेहतर बनाता है जहां का प्रमुख कहता है, सूची प्रमुख है, और इसे इसमें जोड़ती है। शेष सूचियों के लिए यदि कोई नंबर पहले से सूचीबद्ध सूची में पहले से ही कोई मान नहीं है तो इसके प्राइम possible सभी संभावित प्राइम्स की सूची है, क्योंकि सभी संभावित प्राइम फॉर्म 6 * के -1 या 6 में हैं * k-1 को छोड़कर 2 और 3 यही नियम shortCircuit के लिए लागू किया जाता है बहुत जल्दी गणना
से बाहर

DF द्वारा जमानत फ़ुटनोट
¹ यह अभी भी प्राइम्स खोजने के लिए एक बहुत ही अक्षम तरीका है। ट्रायल डिवीजन का प्रयोग न करें अगर आपको कुछ हजारों से अधिक प्राइम्स की आवश्यकता है, तो इसके बजाय एक चाकू का उपयोग करें। hackage पर कई far moreefficient कार्यान्वयन हैं।