Upload
humberto-chalate
View
10
Download
2
Embed Size (px)
DESCRIPTION
programacion funcional y scheme
Citation preview
Técnicas Avanzadas de Programación
Ingeniería en Informática
Programación Funcional
Lenguajes basados en funciones matemáticas
Funciones MatemFunciones Matemááticasticas⇒ Definen un conjunto de valores, más que el procedimiento de calculo⇒ Establece una correspondencia entre los miembros de un conjunto llamado Dominio a otro conjunto llamado Rango.⇒ La correspondencia es definida por una expresión o en algunos casos por una tabla.
Programación Funcional
Funciones MatemFunciones Matemááticas ticas –– CaracterCaracteríísticassticas
⇒ El orden de evaluación es controlado por condicionales y recursión, en vez de secuencias y repeticiones.
⇒ No hay efectos de borde (No hay definición de variables en el sentido de lenguajes imperativos)
Programación Funcional
Funciones Matemáticas – Formas Funcionales
Composiciónf(x) ~ x + 2g(x) ~ 3* xh(x) ~ f(g(x)) => h(x) ~ (3 * x) + 2
Construccióng(x) ~ x * xh(x) ~ 2 * xi(x) ~ x/2
[g,h,i] (4) ~ (16,8,2)
Programación Funcional - Scheme
• Es un dialecto de LISP creado en el MIT en 1975.
• Se caracteriza por su tamaño pequeño y por su tratamiento de funciones como entidades de 1º clase.
• Sintaxis y Semántica simple.
Programación Funcional - Scheme
• Nombres pueden tener letras, dígitos y caracteres especiales
• Scheme es un ciclo infinito de leer, evaluar, escribir
• Ejemplosexpresión valor
42 42(* 3 7) 21(+ 5 7 8) 20(- 5 6) -1(-15 7 2) 6(-24 (* 4 3)) 12
Programación Funcional - Scheme
• Scheme siempre trata de evaluar los parámetros, si queremos evitar la evaluación se utiliza el quote (‘)
• (Quote A) ~ A• (‘A) ~ A• (´ (A B C)) ~ (A B C)
• Las listas son delimitadas por paréntesis– ( A B C D) 4 elementos
– ( A (B C) D (E (F G))) 4 elementos
Scheme
• Operaciones básicas sobre listascar – Devuelve el 1º elemento de una listacdr – Cola de una lista eliminado el 1º elemento
• Ejemplos car(car ‘(A B C)) Devuelve A(car ‘((A B) C D)) Devuelve (A B)(car ‘A) Devuelve error A no es una lista(car ‘(A)) Devuelve A
• Ejemplos cdr(cdr ‘(A B C)) Devuelve (B C)(cdr ‘((A B) C D)) Devuelve (C D)(cdr ‘A) Devuelve error A no es una lista(cdr ‘(A)) Devuelve ( )
Scheme
• cons sirve para construir listas, recibe 2 parámetros
• Ejemplos cons(cons ‘A ‘()) Devuelve (A)(cons ‘(A B) ‘(C D)) Devuelve ((A B) C D)(cons ‘() ‘(A B)) Devuelve ( () A B)
• El 1º parámetro usualmente es un átomo, pero puede ser una lista. El 2º parámetro es usualmente una lista. La acción es insertar el primer parámetro como nuevo elemento de la 2º lista.
Scheme
• list construye listas dado un número variable de parámetros(list ‘x ‘y ‘z) Devuelve (x y z)
Es equivalente a (cons ‘x (cons ‘y (cons ‘z ‘())))
• Predicados de comparación eq? null? list?- eq? Devuelve #t si ambos parámetros son átomos y son iguales, sino devuelve #f (revisar eqv?,
equal?)(eq? ‘A ‘A) Devuelve #t(eq? ‘A ‘B) Devuelve #f
- null? Devuelve #t si el parámetro dado es la lista vacía(null? ‘(A B)) Devuelve #f(null ‘()) Devuelve #t(null? ‘A) Devuelve #f
- list? Devuelve #t si el parámetro dado es una lista(list? ‘(x y)) Devuelve #t(list ‘x) Devuelve #f(list ‘()) Devuelve #t
Scheme
• Para las comparaciones con data numérica se usa: =, <, >, <=, >=, even?, odd?, zero?
• Para visualización(display expresión)(newline)
• Definición de simbolos y constantes(define simbolo expresion)
Ejemplos:(define pi 3.14159)(define alfa (* 2 pi))
Scheme• Definición de funciones
(define (nombre-funcion parametros)cuerpo
)o(define nombre-funcion
(lambda (parametros)cuerpo
))
• Ejemplos(define (segundo lst)
( car (cdr lst)))>(segundo ‘(A B C))B
(define cuadrado (lambda (numero)
(* numero numero))
)> (cuadrado 6)36
Scheme
• Flujos de Control– Condicional - Clausula if
• (if condicion expression_then expresion_else)
1 si n = 0factorial(n) ~
n * f(n-1)
(define (factorial n)(if (= n 0)
1(* n (factorial (- n 1)))
))
Scheme
• Flujos de Control– Multiples Condiciones
• (cond(condicion1 expresion1)(condicion2 expresion2)...(condicionN expresionN)(else expresion)
)
Las condiciones son evaluadas secuencialmente hasta encontrar a la primera verdadera y esa es la expresión que se devuelve
Scheme
• Flujos de Control– Multiples Condiciones
• Realice una función que determine si un átomo es miembro de una lista.
(define (miembro atomo lista)(cond
((null? lista) #f)((eq? atomo (car lista)) #t)(else (miembro atomo (cdr lista)))
))
Scheme
• Ejemplos– Realice una función que determine si 2 listas de átomos son
iguales.
(define (igualdadLis lis1 lis2)(cond
((null? lis1) (null? lis2))((null? lis2) #f)(eq? (car lis1) (car lis2))(igualdadLis (cdr lis1) (cdr lis2))(else #f)
))
Scheme
• Ejemplos– Realice una función que concatene 2 listas.
(define (concat lis1 lis2)(cond
((null? lis1) lis2)(else (cons (car lis1) (concat (cdr lis1) lis2)))
))
> (concat ‘(A B C) ‘(D E F))(A B C D E F)>
Scheme
• Funcion Let• (let (
(nombre1 expresion1)(nombre2 expresion2)...(nombreN expresionN)cuerpo
)
La función let permite hacer asignaciones temporales de valores a subexpresiones
Scheme
• Ejemplos– Realice una función que calcule las raíces cuadradas de una
ecuación
(define (raices a b c)(let (
(parte_raiz (/ (sqrt (- (* b b) (* 4 a c))) (* 2 a)))(parte_menos ( / (- 0 b) (* 2 a)))
)(display (+ parte_menos parte_raiz))(newline)( display (- parte_menos parte_raiz))
))
Scheme
• Ejercicios– Realice una función que sume los elementos de una
lista de enteros.– Realice una función que cuente los átomos de una
lista, donde todos los elementos son átomos.– Realice una función que cuente los átomos de una
lista, donde cada uno de los elementos puede ser un átomo o una lista.
– Realice una función que devuelva el máximo de 3 números