上做哈斯克爾

Question

一些元素二進制搜索

我想完成我的家庭作業的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)) 

問題問：

寫Haskell程序是需要 英文句子「英語」，採用二進制搜索查找 了每個單詞在英語 - 法語字典 ， 執行字對字的替換， 組裝神父ench翻譯和 將其打印出來。

功能「快速排序」拒絕 重複的條目（以「錯誤」 /中止） ，以便有一個精確法國 定義爲任何英文單詞。測試 'quicksort'與原始 'raw_data'以及在將 '（「保存」，「sauve」）'添加到'raw_data'之後。

這裏是一個馮諾依曼遲到 版本的二進制搜索。將 直接轉換成Haskell。 立即進入後，Haskell 版本必須驗證遞歸 「循環不變」，如果無法保持，則以 '錯誤'/終止爲終止。如果 英文單詞未找到，它也會以相同的方式終止。

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 

在Haskell的版本

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

作爲恆定字典 'A' 型的 '[輸入]' 是全局可見的。提示： 在輸入 'binsearch'後立即將您的字符串（英文單詞）變成 'Entry'。

的 高級數據類型「進入」的節目價值在於， 如果你能在整數設計這兩個函數 ，這是微不足道的 提升他們對工作在入學的。

有人知道我應該如何去關於我的二進制搜索功能？

Answer 1

二分查找需要隨機訪問，這在列表中是不可能的。因此，首先要做的事情可能是將列表轉換爲Array（與listArray），並對其進行搜索。

Answer 2

指導員要求提供「字面音譯」，因此請使用相同的變量名稱，順序相同。但需要注意的一些差異：

• 給定的版本只需要1 參數，他給 簽名要求3嗯，
• 給定的版本是不是遞歸，但他問了 遞歸版本。

另一個答案說轉換爲數組，但是對於這樣一個小練習（畢竟這是作業），我覺得我們可以假裝列表是直接訪問。我只是把你的diction :: [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> 

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

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