हास्केल

Question

में कुछ तत्वों पर एक द्विआधारी खोज करना

मैं अपने हास्केल होमवर्क के अंतिम भाग को पूरा करने की कोशिश कर रहा हूँ और मैं अटक कर रहा हूँ मेरी कोड अब तक:

data Entry = Entry (String, String) 

class Lexico a where 
    (<!), (=!), (>!) :: a -> a -> Bool 

instance Lexico Entry where 
    Entry (a,_) <! Entry (b,_) = a < b 
    Entry (a,_) =! Entry (b,_) = a == b 
    Entry (a,_) >! Entry (b,_) = a > b 

entries :: [(String, String)] 
entries = [("saves", "en vaut"), ("time", "temps"), ("in", "<`a>"), 
       ("{", "{"), ("A", "Un"), ("}", "}"), ("stitch", "point"), 
       ("nine.", "cent."), ("Zazie", "Zazie")] 

build :: (String, String) -> Entry 
build (a, b) = Entry (a, b) 

diction :: [Entry] 
diction = quiksrt (map build entries) 

size :: [a] -> Integer 
size [] = 0 
size (x:xs) = 1+ size xs 

quiksrt :: Lexico a => [a] -> [a] 
quiksrt [] = [] 
quiksrt (x:xs) 
    |(size [y|y <- xs, y =! x]) > 0 = error "Duplicates not allowed." 
    |otherwise = quiksrt [y|y <- xs, y <! x]++ [x] ++ quiksrt [y|y <- xs, y >! x] 


english :: String 
english = "A stitch in time save nine." 

show :: Entry -> String 
show (Entry (a, b)) = "(" ++ Prelude.show a ++ ", " ++ Prelude.show b ++ ")" 

showAll :: [Entry] -> String 
showAll [] = [] 
showAll (x:xs) = Main.show x ++ "\n" ++ showAll xs 

main :: IO() 
main = do putStr (showAll (diction)) 

सवाल पूछते हैं:

एक हास्केल प्रोग्राम हैं जो अंग्रेजी वाक्य 'अंग्रेजी' लेता लिखें, अप द्विआधारी खोज का उपयोग कर अंग्रेजी-फ्रेंच शब्दकोश में प्रत्येक शब्द लग रहा है, शब्द के लिए शब्द प्रतिस्थापन करता है, असेंबल फादर एनच अनुवाद, और इसे प्रिंट करता है।

समारोह 'quicksort' को खारिज कर दिया डुप्लिकेट प्रविष्टियों ('त्रुटि'/बीच में बंद करें साथ) तो ठीक है कि वहाँ किसी भी अंग्रेजी शब्द के लिए एक फ्रेंच परिभाषा। परीक्षण मूल 'raw_data' दोनों के साथ 'quicksort' और '("बचाता है", "sauve")' raw_data 'में जोड़ने के बाद।

यहां एक वॉन न्यूमैन देर से रोक रहा है बाइनरी खोज के संस्करण। हास्केल में शाब्दिक लिप्यंतरण बनाएं। प्रविष्टि के तुरंत बाद, हास्केल संस्करण को रिकर्सिव "लूप इनवेरिएंट" सत्यापित करना होगा, 'त्रुटि'/निरस्त करने के साथ समाप्त होने पर इसे रोकना विफल रहता है। यह भी उसी फैशन में समाप्त होता है यदि अंग्रेजी शब्द नहीं मिला है।

function binsearch (x : integer) : integer 
local j, k, h : integer 
j,k := 1,n 
do j+1 <> k ---> 
    h := (j+k) div 2 
    {a[j] <= x < a[k]}  // loop invariant 
    if x < a[h] ---> k := h 
    | x >= a[h] ---> j := h 
    fi 
od 
{a[j] <= x < a[j+1]}  // termination assertion 
found := x = a[j] 
if found  ---> return j 
| not found ---> return 0 
fi 

हास्केल संस्करण

binsearch :: String -> Integer -> Integer -> Entry 

निरंतर शब्दकोश 'एक' प्रकार के '[प्रवेश]' के रूप में में विश्व स्तर पर दिख रहा है। संकेत: 'binsearch' दर्ज करने पर तुरंत अपनी प्रविष्टि (अंग्रेज़ी शब्द) को में 'एंट्री' बनाएं।

उच्च स्तरीय डेटा प्रकार 'प्रवेश' की प्रोग्रामिंग मूल्य कि, आप पूर्णांकों पर इन दो कार्यों डिज़ाइन कर सकते हैं, तो यह लिफ्ट उन पर संचालित करने के लिए के लिए प्रवेश के लिए तुच्छ है।

कोई भी जानता है कि मुझे अपने बाइनरीसेर्च फ़ंक्शन के बारे में कैसे जाना है?

Answer 1

एक बाइनरी खोज को यादृच्छिक पहुंच की आवश्यकता होती है, जो किसी सूची में संभव नहीं है। तो, ऐसा करने वाली पहली बात शायद सूची को Array (listArray के साथ) में परिवर्तित करना होगा, और उस पर खोज करें।

Answer 2

प्रशिक्षक एक "शाब्दिक लिप्यंतरण" मांगता है, इसलिए उसी क्रम में समान वैरिएबल नामों का उपयोग करें। लेकिन कुछ मतभेद पर ध्यान दें:, हस्ताक्षर वह देता

• दिया संस्करण केवल 1 पैरामीटर लेता है 3. हममम की आवश्यकता है,
• दिया संस्करण पुनरावर्ती नहीं है, लेकिन वह एक पुनरावर्ती संस्करण के लिए पूछता है।

एक और जवाब एक ऐरे में परिवर्तित करने के लिए कहता है, लेकिन इस तरह के एक छोटे से अभ्यास (यह सब के बाद होमवर्क है) के लिए, मुझे लगा कि हम दिखा सकते हैं कि सूचियां सीधे पहुंच हैं। मैंने अभी आपकी डिक्शनरी :: [एंट्री] ली और उसमें अनुक्रमित किया। मुझे कुछ स्थानों में इंट और इंटीजर के बीच कनवर्ट करना पड़ा।

माइनर निट: आप अपने अंग्रेज़ी मूल्य में कोई गलती मिल गया है (bs मैंने बनाया binSearch के लिए एक शॉर्टकट है):

*Main> map bs (words english) 
[Entry ("A","Un"),Entry ("stitch","point"),Entry ("in","<`a>"),Entry ("time","te 
mps"),*** Exception: Not found 
*Main> map bs (words englishFixed) 
[Entry ("A","Un"),Entry ("stitch","point"),Entry ("in","<`a>"),Entry ("time","te 
mps"),Entry ("saves","en vaut"),Entry ("nine.","cent.")] 
*Main> 

Answer 3

एक महत्वपूर्ण प्रस्तावना ऑपरेटर है:

(!!) :: [a] -> Integer -> a 
-- xs!!n returns the nth element of xs, starting at the left and 
-- counting from 0. 

इस प्रकार, [14,7,3]!!1 ~~> 7.

Answer 4

यहाँ सवाल का सिर्फ अंग्रेजी हिस्सा (मैं इसे परीक्षण किया है और यह पूरी तरह काम करता है) के लिए मेरे कोड है:

+०१२३५१६४१०६१

module Main where 

class Lex a where 
    (<!), (=!), (>!) :: a -> a -> Bool 

data Entry = Entry String String 

instance Lex Entry where 
    (Entry a _) <! (Entry b _) = a < b 
    (Entry a _) =! (Entry b _) = a == b 
    (Entry a _) >! (Entry b _) = a > b 
    -- at this point, three binary (infix) operators on values of type 'Entry' 
    -- have been defined 

type Raw = (String, String) 

raw_data :: [Raw] 
raw_data = [("than a", "qu'un"), ("saves", "en vaut"), ("time", "temps"), 
       ("in", "<`a>"), ("worse", "pire"), ("{", "{"), ("A", "Un"), 
       ("}", "}"), ("stitch", "point"), ("crime;", "crime,"), 
       ("a", "une"), ("nine.", "cent."), ("It's", "C'est"), 
       ("Zazie", "Zazie"), ("cat", "chat"), ("it's", "c'est"), 
       ("raisin", "raisin sec"), ("mistake.", "faute."), 
       ("blueberry", "myrtille"), ("luck", "chance"), 
       ("bad", "mauvais")] 

cook :: Raw -> Entry 
cook (x, y) = Entry x y 

a :: [Entry] 
a = map cook raw_data 

quicksort :: Lex a => [a] -> [a] 
quicksort []  = [] 
quicksort (x:xs) = quicksort (filter (<! x) xs) ++ [x] ++ quicksort (filter (=! x) xs) ++ quicksort (filter (>! x) xs) 

getfirst :: Entry -> String 
getfirst (Entry x y) = x 

getsecond :: Entry -> String 
getsecond (Entry x y) = y 

binarysearch :: String -> [Entry] -> Int -> Int -> String 
binarysearch s e low high 
    | low > high = " NOT fOUND " 
    | getfirst ((e)!!(mid)) > s = binarysearch s (e) low (mid-1) 
    | getfirst ((e)!!(mid)) < s = binarysearch s (e) (mid+1) high 
    | otherwise = getsecond ((e)!!(mid)) 
     where mid = (div (low+high) 2) 

translator :: [String] -> [Entry] -> [String] 
translator [] y = [] 
translator (x:xs) y = (binarysearch x y 0 ((length y)-1):translator xs y) 

english :: String 
english = "A stitch in time saves nine." 

compute :: String -> [Entry] -> String 
compute x y = unwords(translator (words (x)) y) 

main = do 
    putStr (compute english (quicksort a))