Aplicaciones de las listas PDF

Preview

Summary

Instituto Tecnologico de TijuanaIngeniería en Sistemas ComputacionalesMateriaProgramación Lógica y FuncionalInvestigaciónProfesor:Luis JavierAlumnoAlbertoFecha11/11/Índice Desarrollo 2 Aplicaciones de las listas 2 Árboles 2 Evaluación perezosa Referencias 2 ÁrbolesUn árbol es una estructura jerárqui...

Description

Instituto Tecnologico de Tijuana Ingeniería en Sistemas Computacionales Materia Programación Lógica y Funcional Investigación Profesor: Luis Javier

Alumno Alberto

Fecha 11/11/2020

Índice

Desarrollo 2.5 Aplicaciones de las listas 2.6 Árboles 2.7 Evaluación perezosa

3 3 4 5

Referencias

7

Desarrollo 2.5 Aplicaciones de las listas Otra de las características fundamentales del paradigma funcional es la utilización de listas. Ya hemos visto en el seminario de Scheme las funciones más importantes para trabajar con ellas. Vamos a revisarlas de nuevo en este apartado, antes de ver algún ejemplo de cómo usar la recursión con listas. Ya hemos visto en dicho seminario que Schema es un lenguaje débilmente tipado. Una variable o parámetro no se declara de un tipo y puede contener cualquier valor. Sucede igual con las listas: una lista en Scheme puede contener cualquier valor, incluyendo otras listas Algunas funciones: 1. Caracteres (tipo Char) 2. Cadenas (tipo String) 3. Tipos numéricos: Int,Float Componentes: 1. Los parámetros, que son los valores que recibe la función como entrada; 2. El código de la función, que son las operaciones que hace la función; 3. El resultado(o valor de retorno), que es el valor final que entrega la función.

2.6 Árboles Un árbol es una estructura jerárquica, organizada y dinámica aplicada sobre una colección de objetos llamados nodos. Jerárquica porque los componentes están a distinto nivel. Organizada porque importa la forma en que esté dispuesto el contenido. Dinámica porque su forma, tamaño y contenido pueden variar durante la ejecución. Existen diferentes formas de representación de un árbol, entre las más comunes se tienen las siguientes: Mediante círculos y flechas Mediante paréntesis anidados Mediante notación decimal de Dewey

Propiedades Un árbol de expresión es un árbol binario con las siguientes propiedades: 1. Cada hoja está operando. 2. Los nodos raíz y los nodos internos son operadores. 3. Los subárboles son subexpresiones cuyo nodo raíz es un operador.

Conceptos básicos Raíz: El nodo superior de un árbol. Hijo: Un nodo conectado directamente con otro cuando se aleja de la raíz. Padre: La noción inversa de hijo. Hermanos: Un conjunto de nodos con el mismo padre. Descendiente: Un nodo accesible por descenso repetido de padre a hijo. Ancestro: Un nodo accesible por ascenso repetido de hijo a padre. Hoja: Un nodo sin hijos. Nodo interno: Un nodo con al menos un hijo. Grado: Número de subárboles de un nodo.

2.7 Evaluación perezosa Es una estrategia de evaluación que retrasa el cálculo de una expresión hasta que su valor sea necesario, y que también evita repetir la evaluación en caso de ser necesaria en posteriores ocasiones. Esta compartición del cálculo puede reducir el tiempo de ejecución de ciertas funciones de forma exponencial, comparado con otros tipos de evaluación. Los beneficios de la evaluación perezosa son: El incremento en el rendimiento al evitar cálculos innecesarios, y en tratar condiciones de error al evaluar expresiones compuestas. La capacidad de construir estructuras de datos potencialmente infinitas. La capacidad de definir estructuras de control como abstracciones, en lugar de operaciones primitivas.

Número de reducciones según las estrategias ● Para los ejemplos se considera la función cuadrado :: Int -> Int cuadrado n = n * n ● Evaluación mediante paso de parámetros por valor: cuadrado (1+2) = cuadrado 3 [por def. +] = 3*3 [por def. cuadrado] =9

[por def. de *]

● Evaluación mediante paso de parámetros por nombre: cuadrado (1+2) = (1+2)*(1+2) [por def. cuadrado] = 3*(1+2) [por def. de +] = 3*3 [por def. de +] =9

[por def. de *]

Evaluación perezosa e impaciente ● En la evaluación mediante paso de parámetros por nombre los argumentos pueden evaluarse más veces que en el paso por valor. ● Se puede usar punteros para compartir valores de expresiones. ● La evaluación mediante el paso de parámetros por nombre usando punteros para compartir valores de expresiones se llama evaluación perezosa. ● La evaluación mediante paso de parámetros por valor se llama evaluación impaciente

Referencias http://www.dccia.ua.es/dccia/inf/asignaturas/LPP/teoria/Tema03-ProgramacionFunci onal.html https://vdocuments.mx/unidad-2-programacion-funcional.html https://domingogallardo.github.io/apuntes-lpp/teoria/tema02-programacion-funcional/ tema02-programacion-funcional.html http://di002.edv.uniovi.es/~labra/FTP/PLF/pf.pdf...