PLO-LAB 10

- listy otwarte

- listy różnicowe

Listy otwarte

Reprezentacja:

- lista pusta: Zmienna

- lista niepusta: [E1, ..., En | Zmienna]

Możemy dodać elementy do listy otwartej nie potrzebując innej zmiennej do zachowywania wyniku, bo zmienna występująca w liście otwartej będzie ukonkretniona aby reprezentować dodane elementy.

Dodanie elementu do listy:

dodaj(Elem, Lista) :- var(Lista), !, Lista = [Elem | _ ].

dodaj(Elem, [ _ | Lista]) :- dodaj(Elem, Lista).

Testujmy ten predykat, np. poleceniem:

:- dodaj(1, L), dodaj(2, L), dodaj(3, L), dodaj(4, L).

Zadania

Zdefiniuj następujące predykaty:

1) scal(L1, L2)

scalanie list: L1 = konkatenacja L1 i L2

2) domknij(L)

zamknięcie listy otwartej L (żeby stała się zwykłą listą)

3) Drzewa otwarte reprezentujemy w podobny sposób.

Zdefiniuj predykat dodajBST(E, Drzewo), który dodaje element E do drzewa otwartego Drzewo.

Listy różnicowe

Zauważmy, że aby dodać element do listy otwartej, nadal musimy przejść przez całą listę aby złapać zmienną występującą na końcu listy. Idea list różnicowych polega na tym, że tę zmienną jawnie pamiętamy na zewnątrz.

Czyli, lista różnicowa = lista otwarta + zmienna (koniec listy).

Reprezentacja:

- lista pusta: Zmienna -- Zmienna gdzie -- jest deklarowany jako operator i zauważmy, że ta sama zmienna występuje 2 razy

- lista niepusta: [E1, ..., En | Zmienna] -- Zmienna

Zadania

1) Zdefiniuj następujące predykaty dla list różnicowych

dodaj(E, Lista, NowaLista)

scal(L1, L2, Wynik)

domknij(L, wynik)

2) flatten(L, W)

3) qsort(L, W)