Sąrašai Spausdinti
( 2 Votes )
Parašė Aurimas Šimkus   

Prolog kalboje, vietoj elementarių konstantų ar kintamųjų, taip pat yra naudojami sąrašai (angl. list). Jie dažnai naudojami kaip parametrai faktuose ir taisyklėse arba argumentai užklausose.

Prolog sąrašo struktūra:

[elementas1, elementas2, elementas3, ...]

Sąrašas formuojamas tarp laužtinių skliaustų, o jo elementai skiriami kableliais. Kiekvienas elementas gali būti konstanta, kintamasis arba sąrašas. Atskiras sąrašo atvejis - tuščiasis sąrašas []. Taigi Prolog sąrašas atitinka maždaug tai, kas yra masyvas interaktyviosiose programavimo kalbose.

 

Sąrašo skaidymas

Viena dažnaiusių operacijų su sąrašu - jo skaidymas. Jo principas: sąrašas priskiriamas dviems kintamiesiems - [A | B], aprašomiems sąraše ir skiriamiems |. Pirmasis elementas priskiriamas pirmąjam kintamąjam, visi likę - kaip sąrašas antrajam.

Sąrašo skaidymo pavyzdys:

[1, 2, 3, 4, 5] = [A | B].
     A = 1,
     B = [2, 3, 4, 5].

Taigi kintamajam A priskiriamas tik pirmas elementas - 1, o B - likusi dalis [2, 3, 4, 5].

Pora kitų įsimintinų atvejų:

[1] = [A | B].
     A = 1,
     B = [].
[] = [A | B].
     false.

 

Paieška sąraše 

Kita dažna operacija - paieška. Jai realizuoti reikės aprašyti rekursiją. Vienas paprastesnių pavyzdžių - nustatymas, ar elementas yra sąraše.

Elemento paieškos pavyzdys:

yra_sarase(Elementas, [Elementas | Likusi_dalis]).
yra_sarase(Elementas, [Pirmasis | Likusi_dalis]) :-
                     yra_sarase(Elementas, Likusi_dalis).

Paieškos principas. Paieškos metu pirmasis sąrašo elementas yra lyginamas su ieškomoju elementu. Kai jie sutampa - paieška baigta. Ši operacija aprašyta pirmoje eiluteje (ieskojomo elemento kintamojo ir pirmojo sąrašo elemento kintamojo pavadinimai sutampa, likusi sąrašo dalis - nebesvarbi). Antrojoje eiluteje aprašomas sąrašo skaidymas ir rekursija (pakartotinis tikrinimas su apkarpytu sarašu. Šioje eilutėje kinamasis Pirmasis, kuriam priskiriamas pirmasis gaunamo sąrašo elementas, yra nebepanaudojamas. Į naują užklausą (rekursiją) siunčiami tik ieskomasis elementas ir likusi sąrašo dalis.

Pavyzdžiui, jei siųsime užklausą yra_sarase(10, [1, 5, 10, 15]), bus gražintas atsakymas true. Tokios užklausos vykdymas būtų toks:

  1. (Elementas, [Elementas | Likusi_dalis]) = (10, [1, 5, 10, 15]) gražins false, nes 10 nėra 1.
  2. Siunčiama nauja suformuota užklausa yra_sarase(10, [5, 10, 15]).
  1. (Elementas, [Elementas | Likusi_dalis]) = (10, [5, 10, 15]) gražins false, nes 10 nėra 5.
  2. Siunčiama nauja suformuota užklausa yra_sarase(10, [10, 15]).
  1. (Elementas, [Elementas | Likusi_dalis]) = (10, [10, 15]) gražins true, nes 10 yra 10, vadinasi, elementas rastas sąraše.