Выполнение бинарного поиска по некоторым элементам в 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, которые занимают английское предложение «английский», выглядит до каждого слова на английском-французском словарь с использованием бинарного поиска, выполняет дословную замену, собирает французский перевод и распечатывает.

Функция 'быстрая сортировка' отклоняет повторяющиеся записи (с 'error' / abort) так что есть точно один француз определение для любого английского слова. Тестовое задание 'Быстрая сортировка' с оригиналом 'raw_data' и после добавления '("сохраняет", "sauve")' до 'raw_data'.

Вот поздняя остановка фон Неймана версия бинарного поиска. Делать буквальная транслитерация на 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

как постоянный словарь 'a' типа «[Entry]» виден во всем мире. Подсказка: Сделайте вашу строку (английское слово) в «Вход» сразу после входа 'Binsearch'.

Значение программирования высокоуровневый тип данных «Ввод» таков, если вы можете разработать эти две функции через целые числа, это тривиально поднимите их, чтобы работать над Энтри.

Кто-нибудь знает, как мне поступить с функцией бинарного поиска?

Answer 1

Инструктор запрашивает «буквальную транслитерацию», поэтому используйте те же имена переменных в том же порядке. Но обратите внимание на некоторые различия:

• данная версия занимает всего 1 параметр, подпись он дает требуется 3. Хммм
• данная версия не является рекурсивной, но он запрашивает рекурсивная версия.

В другом ответе говорится, что нужно преобразовать в массив, но для такого небольшого упражнения (в конце концов, это домашняя работа) я чувствовал, что мы можем притвориться, что списки имеют прямой доступ. Я просто взял вашу дикцию :: [Entry] и внес в нее индекс. Мне пришлось конвертировать между Int и Integer в нескольких местах.

Minor nit: у вас есть опечатка в вашем английском значении (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 2

Бинарный поиск требует произвольного доступа, что невозможно в списке. Итак, первое, что нужно сделать, это, вероятно, преобразовать список в Array (с listArray) и выполнить поиск по нему.

Answer 3

вот мой код только для английской части вопроса (я проверил, и она отлично работает):

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

Answer 4

Важным оператором прелюдии является:

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

Таким образом, [14,7,3]!!1 ~~> 7.