▼Pre  PLAI:   Scheme y Programación Funcional
►2 Estructuras de Datos
On this page:
2.1 Pares
2.2 Listas
2.3 Vectores
    ← prev  up  next → 

2 Estructuras de Datos

Éric Tanter

Aparte de los datos primitivos simples que hemos visto, Scheme soporta múltiples estructuras compuestas, como pares, listas, y vectores.

2.1 Pares

La estructura más básica es el par, que pega dos valores juntos.

> (cons 1 2)

'(1 . 2)

> (car (cons 1 2))

1

> (cdr (cons 1 2))

2

Ejercicio: defina la función (pair-add1 p) que recibe un par de números y retorna un nuevo par dónde los dos elementos fueron incrementados en "1".

2.2 Listas

Toda estructura se puede codificar con pares. En particular, las listas pueden ser construidas encadenando pares (con cons), usando empty (o null, o '()) como último elemento.

> empty

'()

> (cons 2 empty)

'(2)

> (cons 1 (cons 2 (cons 3 empty)))

'(1 2 3)

Es posible crear listas en forma más conveniente con list:
> (define l (list 1 2 3 4 5 6))
> l

'(1 2 3 4 5 6)

Las listas se concatenan con append:
> (append (list 1 2 3) (list 4 5 6))

'(1 2 3 4 5 6)

Lo cual es muy distinto de cons:
> (cons (list 1 2 3) (list 4 5 6))

'((1 2 3) 4 5 6)

Como una lista es en realidad unos pares encadenados, se puede usar car y cdr (y sus combinaciones) para acceder a cualquier elemento de una lista:

> (car l)

1

> (cdr l)

'(2 3 4 5 6)

> (car (cdr l))

2

> (cadr l)

2

> (cadddr l)

4

Existen funciones con nombres más amigables para hacer lo anterior:
> (first l)

1

> (rest l)

'(2 3 4 5 6)

> (second l)

2

> (fourth l)

4

Se habrá dado cuenta que pares y listas aparecen con un ’ (quote) en los resultados del evaluador. Recuerde que ya hemos visto que ’ se usa para los símbolos:
> x

x: undefined;

 cannot reference undefined identifier

> 'x

'x

Resulta que quote en realidad dice a Scheme: "no evalúa lo que sigue, consideralo como un dato". Notará que la sintáxis de una lista es muy parecida a la de una aplicación de función. De hecho:
> (1 2 3)

application: not a procedure;

 expected a procedure that can be applied to arguments

  given: 1

  arguments...:

   2

   3

Scheme se queja que 1 no es una función. O sea, (1 2 3) realmente significa aplicar la función 1 (que no existe) a los argumentos 2 y 3, al igual que en (+ 2 3). Para considerar (1 2 3) como una lista literal, no hay que evaluar:
> '(1 2 3)

'(1 2 3)

> (second '(1 2 3))

2

Una lista literal (es decir, creada con quote) es distinta a una lista creada con list, porque al aplicar list, se evaluan sus argumentos:
> (list 1 2 (+ 1 2))

'(1 2 3)

> '(1 2 (+ 1 2))

'(1 2 (+ 1 2))

Otro ejemplo:
> (second '(define (inc x) (+ 1 x)))

'(inc x)

Esa facilidad que tiene Scheme de representar programas como datos abre puertas fascinantes como generación de programas, extension de lenguajes, reflexión, etc. Solamente veremos un poco de eso en la última parte del curso donde usaremos macros para definir sistemas de programación con objetos dentro de Scheme mismo. ¡Paciencia! ☺

En Racket, las listas y los pares son immutables. Existen versiones mutables de pares y listas, aúnque no las usaremos en el curso.

Finalmente, existen muchas funciones predefinidas para manipular (pares y) listas. Por ejemplo, length para obtener el largo de una lista, list-ref para acceder a una posición dada, reverse para invertir una lista, etc. También existen funciones para iterar, filtrar y buscar.

Ejercicio: defina la función list-pick-random que retorna un elemento al azár dentro de una lista. (La función (random k) retorna un número aleatorio entre 0 y k-1.)

2.3 Vectores

Un vector en Scheme es (casi) como un arreglo en C. La diferencia importante es que el acceso a un vector es seguro: si el índice es fuera del rango del vector, se lanza un error. La mayor diferencia entre arreglos y listas es que el acceso a cualquier posición se hace en tiempo constante (con vector-ref). Por comparación, dado que una lista es una estructura encadenada, el acceso a cualquier posición se hace en tiempo lineal.

> (define v (vector 1 2 3))
> (vector-ref v 2)

3

Por convención, las funciones que modifican de manera imperativa el estado del programa tienen un nombre que termina con el símbolo !.

Otra característica de los vectores es que son, por lo general, mutables:
> (vector-set! v 2 "hola")
> v

'#(1 2 "hola")

La única excepción son los vectores literales, que son immutables:
> (define v2 #(1 2 3))
> (vector-set! v2 0 -10)

vector-set!: contract violation

  expected: (and/c vector? (not/c immutable?))

  given: '#(1 2 3)

  argument position: 1st

  other arguments...:

   0

   -10

Finalmente, es posible convertir vectores en listas y vice-versa:
> (vector->list v2)

'(1 2 3)

> (list->vector '(1 2 3))

'#(1 2 3)

Ejercicio: defina la función vector-set-random! que cambia un elemento al azár dentro de un vector por un valor dado.

    ← prev  up  next →