Performing a binary search on some elements in Haskell

Question

I am trying to complete the last part of my Haskell homework, and I am stuck, my code so far:

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

The question asks:

Write a Haskell program that has an English sentence "English", looks for every word in the English-French dictionary using binary search, performs a phrase, collects a French translation and prints it.

The quicksort function rejects duplicate entries (with error / interruption) so there is exactly one French definition for any English word. Verification work of "quicksort" with the original 'raw_data' and after adding '("saves", "sauve")' to 'raw_data'.

Here is von Neumann, a late-stop version of the binary search. Do literal transliteration in Haskell. Immediately after entering Haskell, the version should check for a recursive "loop invariant" that ends with 'error' / abort if it is not held. It also stops in the same way 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 

how the constant dictionary 'a' of type "[Entry]" is displayed worldwide. Hint: Make your line (English word) in the "Login" immediately after entering 'Binsearch'.

The value of programming the high-level Entry data type is if you can design these two functions on integers trivially lift them to work on the record.

Does anyone know how I should go about my binarysearch function?

Answer 1

The instructor requests a "literal transliteration", so use the same variable names in the same order. But pay attention to some differences:

• this version accepts only 1 parameter, the signature it gives requires 3. Hmmm,
• This version is not recursive, but it asks for a recursive version.

Another answer says to convert to an array, but for such a small exercise (this is still homework), I felt that we could pretend that the lists had direct access. I just took your diction :: [Entry] and indexed it. I needed to convert between Int and Integer in several places.

Minor thread: you have a typo in your English value (bs is the shortcut for binSearch that I did):

  *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 2

Binary search requires random access, which is not possible in the list. So, the first thing to do is convert the list to Array (with listArray ) and do a search on it.

Answer 3

here is my code only for the english part of the question (I tested it and it works fine):

 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 xy 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 xy) = x getsecond :: Entry -> String getsecond (Entry xy) = y binarysearch :: String -> [Entry] -> Int -> Int -> String binarysearch se 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 xy 0 ((length y)-1):translator xs y) english :: String english = "A stitch in time saves nine." compute :: String -> [Entry] -> String compute xy = unwords(translator (words (x)) y) main = do putStr (compute english (quicksort a)) 

Answer 4

An important Prelude statement is:

 (!!) :: [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.