PDF de programación - Programación Funcional Lisp-Scheme

Programación Funcional

g

Lisp-Scheme

R d í

D Old
Dr. Oldemar Rodríguez Rojas
Escuela de Informática
Escuela de Informática
Universidad de Nacional

R j

¿Dónde bajar?
Lisp (EdScheme):

www schemers com
www.schemers.com

(

(

(

)

(

(

) (

))) (

Ejemplo:
je p o
=> (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
(
))
57
=> (define tamaño 2)
)
tamaño
=> tamaño
> tamaño
2
=> (+ 3 tamaño)
=> (+ 3 tamaño)
5
=> (* 2 tamaño)
=> (* 2 tamaño)
4

Ejemplo:
je p o
=> (define Pi 3.14159)
ipi
=> (define radio 10)
(
)
radio
=> (define circunferencia (* 2 Pi radio))
=> (define circunferencia ( 2 Pi radio))
circunferencia
=> circunferencia
62 8318
62.8318

Funciones en Lisp

Ejemplo:
Ejemplo:

=> (define (cuadrado x) (* x x))
))

d d

) (*

(d f

(

=> (cuadrado 2)
4

p

Ejemplo:
j
=>(define (circunferencia radio)
>(define (circunferencia radio)

(* Pi radio))

=>(circunferencia 4)
>(circunferencia 4)
12.56636

Sintaxis de las funciones:
S

(define (<nombre> <parámetros formales>)

(
))
(cuerpo))

Ejemplo:

=>(define (suma cuadrados x y)
>(define (suma_cuadrados x y)

(+ (cuadrado x) (cuadrado y)))

=>(suma cuadrados 2 3)
>(suma_cuadrados 2 3)
13

p

Ejemplo:
j
=>(define (f a)
>(define (f a)

(suma_cuadrados (+ a 1) (- a 1)))

=>(f 5)
>(f 5)
52

f

i

El modelo de sustitución para
evaluar funciones

l
(f 5)
(f 5)
(suma_cuadrados (+ 5 1) (- 5 1))
(+ (cuadrado (+ 5 1)) (cuadrado (- 5 1)))
(+ (* (+ 5 1) (+ 5 1)) (* (- 5 1) (- 5 1)))
(+ ( (+ 5 1) (+ 5 1)) ( ( 5 1) ( 5 1)))
(+ (* 6 6) (* 4 4))
(
)
(+ 36 16)
52

Sintaxis del if
f
S

(if <predicado> <consecuencia>

<alternativa>)
)

lt

ti

Ejemplo:
j

p

=>(define (f x)

(if (>= x 2) (* x x)

(if (and (< x 2) (> x -2)) (+ x 1)

(/ x 2))))
(/
))))

=>(f 4)
=>(f 4)
16
=>(f 0)
=>(f 0)
1

Expresiones condicionales y predicados
Si t
i d l d
Sintaxis del cond

(cond

(<p1> <e1>)
(<p2> <e2>)
(<p2> <e2>)
.....
(<pn> <en>)
(else <e 1>))
(else <en+1>))

Ejemplo:
j

p

=>(define (f x)
)

(d fi

(cond ((>= x 2) (+ (* x x) 1))
(
))

(

(f
((
) (
((= x 0) 2)
(else (* x x x))))
(else (* x x x))))

)

=>(f 3)
1010

Sentencias read y write - Evaluando un documento

(define (calcula-nota x y z)

(/ (+ x y z) 3))
(/ (+ x y z) 3))

(define (paso? n)
(d
)

(pa o
(>= n 70))

(define (nota)

(newline)
(write "Deme las notas")
(newline)
(calcula-nota (read) (read) (read)))

(define (resultado)

(if (paso? (nota)) (write "GANO")
(if (paso? (nota)) (write "GANO")

(write "AMPLIACION")))

=>(resultado)

"Deme las notas"
90
8080
70
"GANO"
GANO

Definiciones Internas:

(define (todo)

(define (calcula-nota x y z)
(
y )

(

(/ (+ x y z) 3))
(define (paso? n)

(>= n 70))
(define (nota)

(newline)
(write "Deme las notas")
(newline)
(calcula-nota (read) (read) (read)))

(d fi
lt d )
(define (resultado)

(

(if (paso? (nota)) (write "GANO")

(write "AMPLIACION")))
(write AMPLIACION )))

(resultado))

todo
=>(todo)
"Deme las notas"
90
4040
50
"AMPLIACION“
AMPLIACION

=>(resultado)
>(resultado)
top-level: unbound variable: resultado

// ERROR
// ERROR

Recursión y Recursión Lineal

Ejemplo 1:

Versión Recursiva

(define (factorial n)
(define (factorial n)

(

) (

(if (or (= n 0) (= n 1))
(
))

(
1
(*
1)))))
(* n (factorial (- n 1)))))

(f

t

i

l (

e s ó
ea )
Versión Recursiva Lineal (Recursión Lineal)

ea ( ecu s ó

ecu s a

(define (factorial1 n)
(define (factorial1 n)

(fac-iter 1 1 n))

(define (fac-iter resultado i n)

(if (
)
(if (> i n)

i

resultado
(fac-iter (* resultado i) (+ i 1) n)))

Modelo de Sustitución
ode o de Sust tuc ó
(factorial1 4)
(factorial1 4)
(fac-iter 1 1 4)
(fac-iter 1 2 4)
(fac-iter 2 3 4)
(fac iter 2 3 4)
(fac-iter 6 4 4)
(fac-iter 24 5 4)

Ejemplo 2:

Versión Recursiva

(define (fib n)
(define (fib n)

(cond ((= n 0) 0)
(
)

((

)
((= n 1) 1)
( l
2))))))
(else (+ (fib (- n 1)) (fib (- n 2))))))

1)) (fib (

(+ (fib (

(define (fib1 n)
(
)

(

(fib-iter1 0 1 0 n))

(define (fib-iter1 ant res i n)
(
)

(

(if (>= i n)

ant
(fib-iter1 res (+ res ant) (+ i 1) n)))
(fib iter1 res (+ res ant) (+ i 1) n)))

Versión Recursiva Lineal (Recursión Lineal)

(define (fib1 n)
(define (fib1 n)
(fib-iter 1 0 n))

(define (fib-iter a b n)

(if (= n 0)

bb
(fib-iter (+ a b) a (- n 1))))

Funciones como Parámetro
u c o es co o a á et o

Ejemplo 1:
Ejemplo 1:

(define (serie1 a n)

(if (> a n)
(if (> a n)

0
(+ a (serie1 (+ a 1) n))))

Ejemplo 2:
j

p

d fi
)
define (serie2 a n)

i 2
(if (> a n)
)
(

(
(
0
(+ (* a a) (serie2 (+ a 1) n))))

Ejemplo 3:

(define (serie3 a n)
(
)

(

(if (> a n)

00
(+ (/ 1 (+ (* a a) 1)) (serie3 (+ a 1) n))))

Toda serie es de la forma:

Programa general
Programa general

(define (serie f a n)

(if (>
)
(if (> a n)
0
(+ (f a) (serie f (+ a 1) n))))

Ejemplo:

(define (cuadrado a)

(* a a))

(define (sum f a n)
(define (sum f a n)
(if (> a n)
0
(+ (f a) (sum f (+ a 1) n))))

(define (serie2 a n)
(define (serie2 a n)

(sum cuadrado a n))

(d fi
i)
(define (termino i)

(t
(/ i (+ (cubo i) 1)))

i

(define (serie3 a n)

(sum termino a n))

Funciones Lambda

Las funciones Lambdapermiten definir
Funciones Anónimas con la siguiente
Funciones Anónimas, con la siguiente
sintaxis:

(lambda (<parámetros>) <cuerpo>)
(lambda (<parámetros>) <cuerpo>)

Ejemplo:

Ejemplo:

(lambda (x) (+ x 4))

=>(define cubo

(lambda (x) (* x x x)))
(lambda (x) ( x x x)))

cubo
>(cubo 3)
=>(cubo 3)
27

Ejemplo:

(

(define (serie f a n)
(
)
(if (> a n)

00
(+ (f a) (serie f (+ a 1) n))))

(define (serie1 a n)
(define (serie1 a n)
(serie (lambda (i) (/ i (+ (cubo i) 1))) a n))

Uso del let
Uso de et

Sintaxis:
Sintaxis:

(let ((<var1> <exp1>)
(<var2> <exp2>)
(<var2> <exp2>)

. . . . . .

<varn> <expn>))
<cuerpo>)
<cuerpo>)

Ejemplo: Una función que calcula el sueldo
neto:
neto:

sueldo=HT*SPH - 20% deducciones
sueldo HT SPH 20% deducciones

(define (salario HT SPH)

(let ((sal-bruto (* HT SPH))
(let ((sal bruto ( HT SPH))

(deduccion (* (* HT SPH) 0.2)))

(- sal-bruto deduccion)))

Funciones que retornan funciones
Ejemplo: Escriba una función que recibe HT, SPH y
retorna una función que recibe como parámetro el
porcentaje de deducción para calcular el salario neto:
porcentaje de deducción para calcular el salario neto:

(define (salario HT SPH)
(define (salario HT SPH)

(lambda (x)

(- (* HT SPH) (* (* HT SPH) x))))
( (
))))

) (

(

)

=>((salario 10 100) 0.2)
800.0
=>(salario 10 100)
#[compound 8896152]

l

l

f

Ejemplo: Escribiremos una función que
calcula la derivada de una función, que
como se sabe es una función definida
como sigue:

l d i d d

ió

cuando h es pequeño
cuando h es pequeño.

Código:
C g
(

(define (derivada f h)
(
)

(lambda (x)

(/ ( (f (+ x h)) (f x)) h)))
(/ (- (f (+ x h)) (f x)) h)))

=>((derivada cubo 0.0001) 5)
75.0015000099324
=>(derivada cubo 0.0001)
#[compound 8897184]
#[compound 8897184]

Pares y Aritmética Simbólica

estructura

Lisp posee una
compuesta
denominada par las cuales de manipulan
con las funciones: cons, cdr y car
Ejemplos:
=>(define x (cons 1 2))
x
=>x
(1 . 2)
=>(car x)
)
1
>( d )
=>(cdr x)
2

(

2
2

......

x

1
1

=>(define y (cons 3 -8))
yy
=>y
(3 . -8)
=>(define z (cons x y))
z
=>z
((1 . 2) 3 . -8)
=>(car z)
(1 . 2)
=>(cdr z)
)
( d
(3 . -8)

(

=>(car (car z))
1
=>(caar z)
)
1
=>(cdr (car z))
>(cdr (car z))
2
=>(cdar z)
=>(cdar z)
2
=>(cddr z)
>(cddr z)
-8

Ejemplo: La aritmética de los Racionales Q

; CONSTRUCTOR

(define (racional a b)

(
b))
(cons a b))

(define (denominador r)

(cdr r))
(
))

(define (numerador r)
(define (numerador r)

(car r))

; DEFINE SUMA DE NUMEROS RACIONALES

(define (suma r1 r2)

(racional (+ (* (numerador r1) (denominador r2))
(
))

(
(* (denominador r1) (numerador r2)))
(* (denominador r1) (denominador r2))))
(
))))

) (

) (

(

(

(

; DEFINE RESTA DE NUMEROS RACIONALES

(define (resta r1 r2)

(racional (- (* (numerador r1) (denominador r2))

(*(denominador r1) (numerador r2)))
(* (denominador r1) (denominador r2))))

; DEFINE PRODUCTO DE NUMEROS RACIONALES

(define (producto r1 r2)

(racional (* (numerador r1) (numerador r2))
(racional ( (numerador r1) (numerador r2))

(* (denominador r1) (denominador r2))))

; DEFINE LA DIVISIÓN NUMEROS RACIONALES

(define (division r1 r2)

(racional (* (numerador r1) (denominador r2))
(racional ( (numerador r1) (denominador r2))
(* (denominador r1) (numerador r2))))

; IMPRIMENUMEROSRACIONALES
; IMPRIME NUMEROS RACIONALES

(define (imprime r)
(define (imprime r)

(newline)
(write (numerador r))
(write (numerador r))
(write-char #\/ )
(write (denominador r)))
(write (denominador r)))

Ejemplos de Uso

=>(define r1 (racional 1 2))
r1
=>(define r2 (racional 3 4))
r2
=>(imprime r1)
>(imprime r1)
1/2
=>(imprime r2)
3/43/4
=>(define z (suma r1 r2))
z
=>(imprime z)
10/8
=>(define p (producto r1 z))
>(define p (p od cto 1 ))
p
=>(imprime p)
p)
10/16

( p

Listas Enlazadas vrs Pares

=>(cons 3 4)
=>(cons 3 4)
(3 . 4)

Primera

4

3

......

Listas Enlazadas vrs Pares
=>(cons (cons 3 4) (cons 7 8))
((3 . 4) 7 . 8)

Primera
Primera

88

7

4

3

E t
Li t
Esto no es una Lista

Listas Enlazadas vrs Pares

=>(cons 3 (cons 4 (cons 7 (cons 8 '()))))
=>(cons 3 (cons 4 (cons 7 (cons 8 ()))))
(3 4 7 8)

Primera

3

4

7

8

Esto si es una lista

La función para construir listas es:

(list a1 a2 a3 . . . . an)

Ejemplo:
j

p

(li t 3 4 7 8)
=>(list 3 4 7 8)
(3 4 7 8)
(
)
; es equivalente a (cons 3 (cons 4 (cons 7 (cons 8 '()))))

Más Ejemplos:

p

j

(

(

=>(define L1 (list 'dos 'mas 'tres 'es 4))
))
l1
=>L1=>L1
(dos mas tres es 4)
=>(car L1)
dos
=>(cdr L1)
(mas tres es 4)
(mas tres es 4)

Operaciones con listas
Ope ac o es co
stas

(

define (longitud L)
)

g
(if (null? L)

00
(+ 1 (longitud (cdr L)))))

(define (n-esimo n L)

(if ( n 1)
(if (= n 1)
(car L)
(
))))
(n-esimo (- n 1) (cdr L))))
i

1) ( d

(

(define (suma-lista L)
(define (suma lista L)

(if (null? L)

00
(+ (car L) (suma-lista (cdr L)))))

(define (pega L1 L2)
(define (pega L1 L2)

(if (null? L1)

L2L2
(cons (car L1) (pega (cdr L1) L2))))

(define