对Haskell中的一些元素进行二分查找

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程序,它使用英语句子"english",使用二进制搜索查找英语 - 法语词典中的每个单词,执行逐字替换,汇编法语翻译并打印出来.

函数'quicksort'拒绝重复的条目('error'/ abort),这样任何英文单词都有一个法语定义.使用原始'raw_data'和将'("save","sauve")'添加到'raw_data'之后测试'quicksort'.

这是冯·诺伊曼最后的二元搜索版本.对Haskell进行字面音译.在进入时,Haskell版本必须立即验证递归"循环不变",如果无法保持,则以'error'/ abort结束.如果找不到英文单词,它也会以相同的方式终止.

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

因为'[Entry]'类型的常量字典'a'是全局可见的.提示:输入'binsearch'后立即将您的字符串(英文单词)变成'Entry'.

高级数据类型"Entry"的编程值是,如果你可以在整数上设计这两个函数,那么将它们提升到Entry的操作是微不足道的.

有谁知道我应该怎么做我的二元搜索功能？

Answer 1

二分查找需要随机访问，这在列表上是不可能的。因此，要做的第一件事可能是将列表转换为Array(with listArray)，然后对其进行搜索。