हास्केल में कुछ तत्वों पर बाइनरी खोज करना

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

data Entry = Entry (String, String)

class Lexico a where
    (!) :: a -> a -> Bool

instance Lexico Entry where
    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] 


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 ))

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

Write a Haskell programs that takes the English sentence 'english', looks up each word in the English-French dictionary using binary search, performs word-for-word substitution, assembles the French translation, and prints it out.

The function 'quicksort' rejects duplicate entries (with 'error'/abort) so that there is precisely one French definition for any English word. Test 'quicksort' with both the original 'raw_data' and after having added '("saves", "sauve")' to 'raw_data'.

Here is a von Neumann late-stopping version of binary search. Make a literal transliteration into Haskell. Immediately upon entry, the Haskell version must verify the recursive "loop invariant", terminating with 'error'/abort if it fails to hold. It also terminates in the same fashion if the English word is not found.

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

In the Haskell version

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

as the constant dictionary 'a' of type '[Entry]' is globally visible. Hint: Make your string (English word) into an 'Entry' immediately upon entering 'binsearch'.

The programming value of the high-level data type 'Entry' is that, if you can design these two functions over the integers, it is trivial to lift them to to operate over Entry's.

किसी को पता है कि मुझे अपने बाइनरी खोज समारोह के बारे में कैसे जाना है?

0

4 उत्तर

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

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

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

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

  *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>
0
जोड़ा
हाँ, टाइपो ने परेशानी का एक गुच्छा दिया, जब मुझे कोड चल रहा था तो मुझे कुछ अनंत लूप मिला।
जोड़ा लेखक Flame, स्रोत

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

0
जोड़ा

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

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

Thus, [14,7,3]!!1 ~~> 7.

0
जोड़ा

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

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
  -- 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) 

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))
0
जोड़ा
@Reza, कृपया कोड के रूप में प्रारूपित होने के लिए अपने कोड ब्लॉक को 4 रिक्त स्थान के साथ इंडेंट करें। मैंने अभी आपके लिए इस पोस्ट के साथ ऐसा किया है।
जोड़ा लेखक Tom Lokhorst, स्रोत