Выполнение бинарного поиска по некоторым элементам в Haskell
Я пытаюсь выполнить последнюю часть моей домашней работы по Haskell, и я застрял, пока мой код:
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 ))
Вопрос спрашивает:
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 fiIn the Haskell version
binsearch :: String -> Integer -> Integer -> Entryas 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.
Кто-нибудь знает, как я должен заниматься своей функцией двоичного поиска?
Ответы 4
Бинарный поиск требует произвольного доступа, что невозможно для списка. Итак, первое, что нужно сделать, это преобразовать список в Array (с listArray) и выполнить поиск по нему.
Преподаватель запрашивает «буквальную транслитерацию», поэтому используйте те же имена переменных в том же порядке. Но обратите внимание на некоторые отличия:
- данная версия занимает всего 1 параметр, подпись, которую он дает требуется 3. Хммм,
- данная версия не является рекурсивной, но он запрашивает рекурсивная версия.
В другом ответе говорится о преобразовании в массив, но для такого небольшого упражнения (в конце концов, это домашнее задание) я чувствовал, что мы можем притвориться, что списки являются прямым доступом. Я просто взял вашу дикцию :: [Entry] и проиндексировал ее. Мне пришлось конвертировать между Int и Integer в нескольких местах.
Незначительная нить: у вас есть опечатка в вашем английском значении (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>
Важный оператор Prelude:
(!!) :: [a] -> Integer -> a
-- xs!!n returns the nth element of xs, starting at the left and
-- counting from 0.
Таким образом, [14,7,3]!!1 ~~> 7.
вот мой код только для английской части вопроса (я тестировал его, и он отлично работает):
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))
@Reza, сделайте отступ в кодовых блоках четырьмя пробелами, чтобы он был отформатирован как код. Я только что сделал это для вас с этим постом.
Да, эта опечатка доставила кучу проблем, у меня получился бесконечный цикл, когда я запустил код.