Haciendo una búsqueda binaria sobre algunos elementos en Haskell

Question

Estoy tratando de completar la última parte de mi tarea Haskell y estoy atascado, mi código hasta ahora:

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

La pregunta es:

se pueden escribir programas Haskell que se lleva a la sentencia Inglés 'Inglés', se ve a cada palabra en el diccionario Inglés-francés mediante la búsqueda binaria, realiza palabra por palabra sustitución, monta el P. ench traducción, y lo imprime.

La función de 'clasificación rápida' rechaza entradas duplicadas (con 'error'/abortar) de modo que no es precisamente una definición de cualquier palabra francesa Inglés. Pruebe 'quicksort' con el 'raw_data' original y después de haber agregado '("guardar", "sauve")' a 'raw_data'.

Aquí hay una versión de búsqueda binaria de von Neumann que se detiene tarde . Realice una transcripción literal en Haskell. Inmediatamente después de la entrada, la versión de Haskell debe verificar el recursivo "loop invariant", que termina con 'error'/abort si no se puede mantener. Es también termina de la misma manera si no se encuentra la palabra en inglés.

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 

En la versión Haskell

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

como el diccionario constante 'a' de tipo '[Entrada]' es globalmente visible. Sugerencia: Haga su cadena (palabra inglesa) en una 'Entrada' inmediatamente después de ingresar 'binsearch'.

El valor de programación del tipo de datos alto nivel 'Entrada' es que, si se puede diseñar estas dos funciones sobre los números enteros, es trivial para ascensor que operan a lo largo de la entrada.

¿Alguien sabe cómo debo hacer con mi función binarysearch?

Answer 1

Una búsqueda binaria necesita acceso aleatorio, lo que no es posible en una lista. Entonces, lo primero que debe hacer es convertir la lista a Array (con listArray) y hacer la búsqueda en ella.

Answer 2

El instructor solicita una "transliteración literal", por lo tanto, utilice los mismos nombres de variable, en el mismo orden. Pero tenga en cuenta algunas diferencias:

• la versión dada tarda sólo 1 parámetro, la firma da requiere 3. Hmmm,
• la versión dada no es recursivo, pero le pide un versión recursiva.

Otra respuesta dice que se convierta en una matriz, pero para un ejercicio tan pequeño (después de todo esto es tarea), sentí que podíamos fingir que las listas son de acceso directo. Acabo de tomar su dicción :: [Ingreso] e indexado en eso. Tuve que convertir entre Int y Entero en algunos lugares.

nit Menor: Usted tiene un error en el valor de Inglés (BS es un acceso directo a binsearch hice):

*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

Un operador preludio importante es:

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

Por lo tanto, [14,7,3]!!1 ~~> 7.

Answer 4

aquí está mi código para sólo la parte de Inglés de la cuestión (lo probé y funciona perfectamente):

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