Programación FuncionalgLisp-Scheme

D Old R d í R jDr. Oldemar Rodríguez RojasEscuela de InformáticaEscuela de Informática Universidad de Nacional

¿Dónde bajar?Lisp (EdScheme):

www schemers comwww.schemers.com

Ejemplo:je p o=> (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))( ( ( ( ) ( ))) ( ( ) ))57=> (define tamaño 2)( )tamaño=> tamaño> tamaño2=> (+ 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=> circunferencia62 831862.8318

Funciones en Lisp

Ejemplo:

(d f ( d d ) (* ))

Ejemplo:

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

=> (cuadrado 2)4

Ejemplo:j p=>(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

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

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

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

El modelo de sustitución para l f ievaluar funciones

(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 ifS f

(if <predicado> <consecuencia>lt ti )<alternativa>)

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 predicadosSi t i d l dSintaxis del cond

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

Ejemplo:j p

(d fi (f )=>(define (f x)(cond ((>= x 2) (+ (* x x) 1))( (( ) ( ( ) ))

((= 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"90808070"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"90404050"AMPLIACION“AMPLIACION

>(resultado) // ERROR=>(resultado) // ERRORtop-level: unbound variable: resultado

Recursión y Recursión LinealEjemplo 1:

Versión Recursiva

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

1(* (f t i l ( 1)))))(* n (factorial (- n 1)))))

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

(define (factorial1 n)(define (factorial1 n)(fac-iter 1 1 n))

(define (fac-iter resultado i n)(if ( i )(if (> i n)

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

Modelo de Sustituciónode 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 (+ (fib ( 1)) (fib ( 2))))))(else (+ (fib (- n 1)) (fib (- n 2))))))

(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ámetrou c o es co o a á et oEjemplo 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 ( i 2 )define (serie2 a n)(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 generalPrograma 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 (t i i)(define (termino i)(/ i (+ (cubo i) 1)))

(define (serie3 a n)(sum termino a n))

Funciones LambdaLas funciones Lambda permiten definir Funciones Anónimas con la siguienteFunciones Anónimas, con la siguiente sintaxis:

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

Ejemplo:(lambda (x) (+ x 4))

Ejemplo:

=>(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 letUso de etSintaxis: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% deduccionessueldo 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 funcionesEjemplo: 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]

Ejemplo: Escribiremos una función que l l l d i d d f iócalcula la derivada de una función, que

como se sabe es una función definida como sigue:

cuando h es pequeñocuando 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ólicaLisp posee una estructura compuestadenominada par las cuales de manipulancon las funciones: cons, cdr y carEjemplos:=>(define x (cons 1 2))x=>x(1 . 2)

( ) 2

x

=>(car x)1

>( d )

......

1

2

=>(cdr x)2

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)

( d )=>(cdr z)(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))))

; IMPRIME NUMEROS RACIONALES; 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 (p od cto 1 ))=>(define p (producto r1 z))p=>(imprime p)( p p)10/16

Listas Enlazadas vrs Pares

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

Primera

......3

4

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

PrimeraPrimera

88

7

4

E t Li t3

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:j p=>(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 listasOpe ac o es co stasdefine (longitud L)( g )(if (null? L)

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

(define (n-esimo n L)(if ( n 1)(if (= n 1)

(car L)( i ( 1) ( d ))))(n-esimo (- n 1) (cdr L))))

(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 (cuadrado-lista L)(if (null? L)

'()'()(cons (* (car L) (car L)) (cuadrado-lista (cdr L)))))

(define (multiplica-listas L1 L2)(if (null? L1)

'()( (* ( L1) ( L2)) ( lti li li t ( d L1) ( d L2)))))(cons (* (car L1) (car L2)) (multiplica-listas (cdr L1) (cdr L2)))))

Ejemplos:=>(define L1 (list 3 4 5 -1))l1

>(define L2 (list 1 1 2 2))=>(define L2 (list 1 1 2 2))l2=>(longitud L1)( g )4=>(n-esimo 3 L1)55=>(pega L1 L2)(3 4 5 -1 1 1 2 2)=>(cuadrado-lista L1)(9 16 25 1)=>(suma-lista L2)=>(suma lista L2)6=>(multiplica-listas L1 L2)(3 4 10 -2)

(define (aplica f L) Más Ejemplos(define (aplica f L)(if (null? L) '()

(cons (f (car L)) (aplica f (cdr L)))))(cons (f (car L)) (aplica f (cdr L)))))

(define (c enta pa es L)(define (cuenta-pares L)(if (null? L) 0

(if (= (modulo (car L) 2) 0)(+ 1 (cuenta-pares (cdr L)))(+ 0 (cuenta-pares (cdr L))))))

(define (invierte L)(if (null? L) '()(if (null? L) ()

(append (invierte (cdr L)) (list (car L)))))