Linguas de programación
Fernando López Ostenero e Ana García Serrano
O concurso coñecido “Figuras e letras” propoñen dous tipos de probas aos seus participantes: unha das cifras nas que se deben achegar tanto como sexa posible a un número de destino composicións básicas sobre varios números e unha proba de letras, onde deben atopar Lapalabra ( Válido) máis tempo que é posible escribir cunha serie de letras.
Nesta práctica crearemos un programa que resolverá a segunda desas probas. O programa recibirá unha serie de letras e volverá Todas as palabras válidas construír con eles. Para comprobar se unha palabra é válida ou non, é imprescindible usar un dicionario.
Para facelo, proporcionarase un ficheiro co dicionario de Wordspene 79517 ao dicionario dos rae para que os estudantes poidan Proba o teu programa. Problemas de saída debido á codificación de caracteres, elimináronse todas as palabras e elimináronse os acentos gráficos.
Así, a práctica dividirase en dúas fases diferentes:
- Creación do dicionario: un ficheiro de texto que contén as palabras que imos considerar válido (unha palabra por liña) será inserida e cada un deles será inserido nunha estrutura de dicionario sobre a que se consultarán as palabras posibles.
- Buscar palabras: Unha vez que o dicionario está dispoñible, o programa pedirá ao usuario a secuencia de letras para analizar e devolver todas as palabras válidas posibles que poden ser construídas a partir destas letras, ordenadas alfabeticamente e agrupadas por tamaño máis alto a menor.
Asuntos que a entrada / saída no paradigma funcional non forma parte da axenda que se estuda a materia, todas as funcións responsables da lectura do dicionario dun ficheiro ou l Os asuntos co usuario estarán programados para estudantes. Nesta afirmación haberá explicación do funcionamento das devanditas funcións.
Declaración de prácticas
A práctica é elaborar un programa en Haskell que cargue un ficheiro de texto de conspalabra válido e cre que un dicionario .. Unha vez feito isto, o programa pedirá ao usuario a diferentes secuencias de letras e devolverá as palabras válidas (aqueles presentes en Eldictionary) que se poden construír en función das letras dispoñibles.
Exemplo 1: O programa busca o programa Dicionario ficha por palabras (Dictionary.Txt), constrúe o dicionario e espera que o usuario introduza unha secuencia de letras:
* principal > Lista de palabras maincargo do Dictionary File.txT79517 Ler palabras
Introduza secuencia de letras:
Exemplo 2: co dicionario xa cargado xa cargado, o usuario entra na secuencia de letras “AOSC” eo programa devolve todo o palabras do dicionario que se poden construír mediante letras:
Aquí podemos ver o dicionario resultante representado gráficamente nunha forma de árbore. Como anteriormente Seindicado, os nodos intermedios (excepto a raíz, representada como RN) son os Único que coñece personaxes. E a concatenación dos personaxes que forman o camiño da raíz accesible dos nodos de follas (representados como WN) indican as palabras presentes en Eldictionary.
Para obter unha mellor comprensión da estrutura de datos que se usan, nós Suxerir aos alumnos que están a executar un tempo de visualización do dicionario mostrado na Figura 1 para comprobar exactamente as once palabras indicadas na lista que se usou para creala.
2.2 Estrutura dos módulos de práctica
A práctica está dividida en dous módulos, cada un nun ficheiro independente cuxo nome (incluíndo maiúsculas e minúsculas) co nome do módulo e cuxa extensión é .hs:
- Dicionario módulo: Dentro diso Módulo, as funcións de construción e acceso ao dicionario será programada. Tamén inclúe a definición do tipo de datos do dicionario.
- Módulo principal: Este módulo contén o programa principal e todas as funcións responsables de cargar a lista de palabras e interactuar co usuario.
Dado que un estudo máis profundo dos módulos en Haskell está fóra do ámbito da LaSsignature, só indicaremos que cada módulo importa unha serie de módulos que son necesarios para o seu funcionamento. Na nosa práctica, a principal importación de módulos (ademais do módulo de módulo) módulos adicionais para poder traballar coa saída, ficheiros e converter todas as letras. Ademais, a lista de identificadores entre parénteses que acompaña o ano do módulo de dicionario representa as definicións de tipos e funcións que a moduleexport.Calquera outra definición considerarase privado, sendo accesible só polo módulo
Figura 1 :. Dicionario representada na árbore en forma
2.3 Tipo de datos de dicionario (módulo dicionario)
Nesta sección imos introducir o tipo de datos que imos usar para almacenalo na práctica. Está definido na parte do módulo de dicionario que proporciona a ensinar a eleger. Como vimos na sección anterior, un dicionario será unha árbore na que os nodos intermedios conterán un personaxe, mentres que os nodos de follas daranos a formación de que palabras pertencen ao dicionario. Así, a definición do tipo de dicionario:
dicionario de datos = rootnode | LetternODe carácter | Wordnode
é dicir, un dicionario ou é un rootnode (nodo raíz) que contén unha lista de dicionarios , unletternode (letra no) que contén un char e unha lista de dicionarios, ou un wordnode (nó palabra) que será un nó folla que marcar-nos que a concatenación de todos lettersContenses nos ganglios da raíz (que non fai conter ningún) ata o pai da forma no folla unha palabra válida do dicionario.
Este tipo de datos se engade como instancia da clase concerto, para poder ver o contido de un tipo de dicionario elemento e así facilitar a tarefa de programación as funcións decreies dicionario
a representación interna do dicionario da Figura 1 sería a seguinte :.
rootnode]]], letternode ‘c’ ] letternode ‘S’, Letternode ‘C’] LetterDe ‘O’]]], LetternDe’o ‘]]], LetterDe’ O ‘]]]], LetterDe’ S ‘] ] LETTERNODE ‘O’]]]]
que é un pouco máis complicado de ler que a súa representación gráfica.
2.4 programa principal (módulo principal)
O módulo principal contén o programa principal, xa programado polo equipo docente. Famento que utilizan monads e están escritos usando a “notación de facer”, que é unha notación para facilitar a redacción de concatenacións de funcións monordras. Sen entrar demasiado. Asumir o funcionamento das Monads, explicaremos os tipos de datos definidos e que cada función
tipo de datos
- WordSN: .. Representa unha lista de palabras usaremos este tipo para referirse a unha lista de todos a mesma lonxitude e organizados en orde alfabética .
- palabras: Representa unha lista WordSn usaremos este tipo para referirse a unha lista de palabras agrupadas en listas de palabras de igual lonxitude e organizados en orde alfabética
.. función de inserción
o tipo sería insertintree :: cadea – > dicionario -. > dicionario Esta función é a unha inserción dunha palabra no dicionario, pero xa penso como unha árbore. o firstparameter debe ser O resto da palabra que segue sendo inserido eo segundo parámetro do nodododel árbore da que outra resto palabra debe ser inserido
función Insertchild
o tipo insertchild :: Char -. > – > – >. No primeiro parámetro recibe o primeiro carácter do resto da palabra a ser inserido, o segundo parámetro o resto da palabra que se inserirá (sen ese primeiro carácter), o terceiro parámetro unha lista de elementos de tipodición (que será a Nenos dun nodo). Volve a lista de fillos do nodo correctamente cambiou.
Esta función é responsable ollar para o neno dende o nodo actual, onde a inserción dos personaxes que aínda restan da palabra actual son continuados. No caso de que o neno non exista, a función de Lodeber creará. Unha vez localizado (ou creado) o neno correcto, a función debe continuar o resto dos personaxes da palabra dese neno. Neste punto, suxerimos a studentsCreate “á man” o dicionario representado na Figura 1 para unha mellor comprensión do proceso de inserción de palabras no dicionario.
2.6 Consultas ao (módulo dicionario) Dictionary
Nesta sección, imos probar as consultas ao dicionario. o noso obxectivo será o programa de investigación a secuencia que recibe unha secuencia de caracteres e un dicionario. é de retorno pola lista scutrary, ordenados alfabeticamente, que están contidos en o dicionario e que poden ser convertidos cos personaxes de secuencia
Buscar :: cadea -. > dicionario – >
por exemplo, se miramos a secuencia “Cascão” no dicionario representado na figura 1, que debe obter a seguinte lista de palabras:
Teña en conta que “casos” e ” pór do sol “, presente no dicionario, non poden ser formadas coas letras do feasque, xa que contén só un ‘S’ (e ‘problemas’ ten dous) e A ‘O’ (e “Sundo” ten dous).
Como imos tomar a busca?Imos supoñer que xa fixemos unha ruta anterior, levounos a un nodo de árbore (que non é unha folla). Polo tanto, teremos un personaxe de secuenciación que aínda non se usan e o inicio dunha palabra formada polos personaxes presentan o camiño da raíz ao nodo actual.
Agora analizamos a todos os nenos do nodo actual:
- Se un neno é un Wordnode, significará que a palabra que xa formamos pertence ao dicionario, co que, será necesario engadilo.
- Se un neno é letternode, conterá un personaxe. Só se este personaxe pertence á secuencia aínda non explorada (en calquera posición, non necesariamente o primeiro), debemos explorar de forma recursiva este neno, engadindo a palabra xa formado o carácter do Lettode e eliminando o devandito carácter da secuencia aínda non explorada .
Recomendamos de novo que os alumnos invisten un tempo na realización deste matorral na árbore da Figura 1 para a secuencia “Cascao” e comproba exactamente as palabras indicadas.
Como na sección anterior, a función de busca necesitará unha serie de funcións (que non serán visibles desde o exterior do módulo). O máis importante é o seguinte LASDOS:
Function SearchIntree
O seu tipo sería SEARCHINTREE :: STRING – > STRING – > Diccionario – >. No primeiro parámetro recibe os personaxes da secuencia aínda que non o usa Dous, no segundo recibe a palabra que xa se formou ata chegar ao nodo de árbore que se recibe como o terceiro parámetro.
Debes devolver todas as palabras contidas no dicionario cuxo inicio é o contido por Descubrindo o parámetro e continúa do nodo actual (terceiro parámetro) usando só solucións de secuencias aínda non exploradas (primeiro parámetro).
Search Function
SearchChild :: String – > string – > diccionario – >. A función recibe a secuencia aínda non explorada, o inicio da palabra xa construído (baseado na ruta empregada para chegar a este nodo da raíz) e un nodo (fillo do nodo que se está a explorar). Esta é a función que o fará aplicar o algoritmo explicado anteriormente para devolver a lista de escratas que se pode formar co inicio xa construído e cos personaxes que aínda non se usan.
Problemas sobre a práctica
A resposta A estas preguntas é opcional. Non obstante, se o alumno non responde a estas preguntas, a cualificación da práctica só pode alcanzar 6 puntos máis de 10.
- (1’5 puntos). Supoñamos unha implementación de prácticas nunha linguaxe non declarativa (como Java, Pascal, C …). Comentar as vantaxes e as desvantaxes que eu tería diante da implementación en Haskell. Relaxa estas vantaxes desde o punto de vista da eficiencia con respecto á programación e execución. Cal sería o punto principal a favor da implementación en linguas non declarativas? E a implementación en Haskell?
- (1’5 puntos). Indique, coas súas palabras, o que lle permite xestionar o predicado non lóxico predefinido, corte (!), En proll. Como se levaría a cabo este efecto en Java? Xustificar a súa resposta.
- (1 punto). Para os tipos de problemas do problema definidos en Haskell (en ambos os módulos), indican que tipo de tipos de construtores usáronse en cada caso (ver o capítulo 5 do libro da materia).
Documentación para entregar
Cada alumno debe entregar a seguinte documentación ao seu titor práctico: – Código fonte en Haskell que resolve o problema que se presenta. Para iso, os ficheiros Lyrics.HS e Dictionary.HS deben ser entregados, coas funcións descritas nesta declaración, así como todas as funcións auxiliares que son necesarias. – Unha memoria con: – Unha pequena descrición das funcións programadas. – As respostas a problemas na práctica.