Download Clase 22

Lenguajes y
Paradigmas de
Programación
Clase 22
Tema 10: Tipos de datos mutables
Índice
•
•
•
Valores, referencias, mutadores e igualdad
cons, set-car! y set-cdr! no son primitivas
Mutadores y estructuras de datos
Ejemplos con diagramas caja y puntero
Modificación de los tipos de datos ya
vistos: listas, árboles, árboles binarios
Nuevos tipos de datos: tabla hash y lista de
asociación
•
•
•
Diagramas caja y
puntero y mutadores
(define x
(define y
(set-car!
(define z
(set-cdr!
'((a b) c d))
'(e f))
x y)
(cons y (cdr x)))
x y)
Datos compuestos
• Los datos compuestos (parejas) se
referencian desde variables
(define x (cons 2 3))
• En programación funcional no podíamos
cambiar el valor de una pareja
• Ahora sí, y eso va a traer muchos cambios
En Scheme las variables pueden
contener datos simples o
referencias a datos compuestos.
Copia de valor y de
referencia
(define x (cons 2 3))
(define y x)
(define z (cons (car x) (cdr x)))
En programación funcional no había diferencia
entre y y z. Ahora sí, por la mutación:
(set-car! x 10)
Datos simples
• Los datos simples no pueden ser
referenciados
(define x ‘hola)
(define y x)
(set! x ‘adios)
y
Llamadas a funciones
• En Scheme siempre se pasa como
parámetro el contenido de la variable (o
sea, la referencia a lo que está apuntando la
variable o su valor si es un dato simple)
(define (cambia x)
(set-car! x 10))
Igualdad
• Ahora es necesario definir dos tipos de
igualdad, igualdad de referencia (eq?) e
igualdad de contenido (equal?)
Ejemplo: set-to-wow!
(define x (cons 1 2))
(define y x)
(define z (cons (car x)
(cdr x))
(eq? x y) (equal? x y)
(eq? x z) (equal? x z)
¡Hay que tener cuidado!
(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))
(define (make-cycle x)
(set-cdr! (last-pair x) x))
(define z (make-cycle (list 'a 'b 'c)))
(last-pair z)
¿son primitivos cons,
set-car! y set-cdr!?
(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(lambda (m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else
(error "No definido -- CONS" m)))))
Mutadores y tipos de
datos
!
!
!
!
!
!
!
!
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define (set-car! z new-value)
((z 'set-car!) new-value)
z)
(define (set-cdr! z new-value)
((z 'set-cdr!) new-value)
z)
• Listas: inserción, cabecera de la lista
• Árboles: modificar contenido
• Árboles binarios: inserción
• Tablas hash
• Listas de asociación