Listas

📖 Teoría

Epecificación Algebráica de las listas

Parámetros genéricos

• TElemento

Tipos

• TLista

Operaciones

Constructoras generadoras

• CrearVacia: → TLista

• Construir: TElemento X TLista → TLista

Observadoras selectoras

• (PARCIAL) Primero: TLista → TElemento

• (PARCIAL) Resto: TLista → TLista

Observadoras no selectoras

• EsVacia: TLista → Boolean

• Longitud: TLista → Integer

• (PARCIAL) Ultimo: TLista → TElemento

• Pertenece: TElemento X TLista → Boolean

Constructoras no generadoras

• Concatenar: TLista X TLista → TLista

• BorrarElemento: TElemento X TLista → TLista

• InsertarFinal: TElemento X TLista → TLista

Parámetros genéricos

Igual: TElemento X TElemento → Boolean

Variables

• l , lista , lista<N> → TLista

• e , elem , elemento → TElemento

Ecuaciones de definitud

• DEF ( Primero( Construir(e, l) ) )

• DEF ( Resto( Construir(e, l) ) )

• DEF ( Ultimo( Construir(e, l) ) )

Ecuaciones

Observadoras selectoras

• Primero( Construir( e, l ) ) = e

• Resto( Construir( e, l ) ) = l

Obserbadoras no selectoras

• EsVacia
• EsVacia( CrearVacia ) = True
• EsVacia( Construir( e, l) ) = False

• Longitud
• Longitud( CrearVacia ) = 0
• Longitud( Construir( e, l ) ) = 1 + Longitud(l)

• Ultimo
• Ultimo( Construir( e, l ) ) = SI EsVacia( l ) → ( e ) || ( Ultimo( l ) )

• Pertenece
• Pertenece( e, CrearVacia ) = False
• Pertenece( e, Construir( elem, l ) ) = Igual( e, elem ) || Pertenece( e, l )

Constructoras no generadoras

• Concatenar
• Concatenar( CrearVacia, l ) = l
• Concatenar( Construir( e, l ), lista2 ) = Construir( e, Concatenar( l, lista2 ) )

• BorrarElemento
• BorrarElemento( e, CrearVacia ) = CrearVacia
• BorrarElemento( e, Construir( elem, l ) ) = SI Igual( e, elem ) → ( l ) || ( Construir( e, BorrarElemento(e, l) ) )

• InsertarFinal
• InsertarFinal( e, CrearVacia ) = Construir( e, CrearVacia )
• InsertarFinal( e, Construir(elem, l) ) = Construir( e, InsertarFinal(e, l) )

Epecificación Algebráica de las listas ordenadas

Tipos

• TListaOrd

Operaciones

InsertarOrd: TElemento X TListaOrd → TListaOrd

Mezclar: TListaOrd X TListaOrd → TListaOrd

Parámetros genéricos

EsMejor: TElemento X TElemento → Boolean

Variables

lo , lo<N>→ TListaOrd

Ecuaciones

• InsertarOrd
• InsertarOrd( e, CrearVacia ) = Construir( e, CrearVacia )
• InsertarOrd( e1, Construir(e2, lo) ) = SI EsMejor(e1, e2) → ( Construir(e1, Construir(e2, lo)) ) || ( Construir(e2, InsertarOrd(e1, lo)) )

⚙️ Implementaciones