Editor:

John Val

Bron: Learn Prolog Now!

Lijsten

Zoals de naam al suggereert is een lijst niet anders dan een lijst van dingen ( = items = elementen ). Iets precieser, het is een eindige rij van elementen. Dit zijn enkele voorbeelden:

Laten we kort de voorbeelden behandelen.

Een lijst heeft dus elementen die door komma's gescheiden zijn en die ingesloten zijn door vierkante haken. De begin haak is [ en de eind haak is ].
Het tweede voorbeeld laat zien dat alle Prolog objecten een element in een lijst kunnen zijn.
Het derde voorbeeld laat zien dat er ook een lege lijst bestaat, alleen twee haken met niets erin.
Omdat ook een lijst een Prolog object is, kan een lijst dus ook een element van een lijst zijn, dit zie je in voorbeeld vier. Het laatste voorbeeld toont de grote mogelijkheden die er zijn. Elementen mogen ook meerdere keren voorkomen.

Lijsten hebben ook een lengte. De lengte van een lijst is het aantal elementen dat een lijst bevat, maar het is een beetje oppassen geblazen. De lengte van de lijst in voorbeeld 1 is duidelijk, die is 4. Ook de lengte van de tweede lijst is 4, hier is dit al wat lastiger te zien door de samengestelde term. De derde (lege) lijst heeft lengte 0. Als er lijsten in lijsten aanwezig zijn wordt de lengte van de lijst op het hoogste niveau niet beïnvloed door de lengten van de sublijsten. De lijst in voorbeeld vier heeft dan ook de lengte 3.

Nu komen we bij een belangrijke constructie in het denken over lijsten, die straks van groot nut zal zijn in de recursie in lijsten. Iedere niet lege lijst bestaat uit een eerste element, de kop (head) en alle volgende elementen, de staart (tail). Meer precies, als we het eerste element uit de lijst weghalen houden we de staart over. De staart is altijd weer een (mogelijk lege) lijst. Bijvoorbeeld de head van

is het atoom geert en de tail is [madelief, henk, sylvia]. Evenzo is de kop van de lege lijst [] en de staart [dead(z), [2,[b,c]],[],Z,[2,[b, c]]].
Als een lijst slechts één element bevat b.v. dan is de kop uppie en de staart is de lege lijst [].
Hoe zit het nu met de lege lijst? Deze heeft kop nog staart. Ofwel de lege lijst heeft geen interne structuur; in Prolog is de [] lijst een speciale lijst en tegelijkertijd ook de meest eenvoudige lijst. Ook speelt deze lege lijst een belangrijke rol als we recursieve programma's voor lijsten gaan maken.

Om het concept kop en staart ( head en tail ) werkbaar te maken heeft Prolog een speciale ingebouwde operator, de verticale streep | . Deze kan worden gebruikt om een lijst in kop en staart te verdelen. Het is ook weer belangrijk bij het programmeren met lijsten om te weten hoe je de | operator moet gebruiken.

Het meest elementaire gebruik van | is bij het verkrijgen van informatie uit een lijst. Dit gebeurt door gebruik te maken van unificatie. Als we bijvoorbeeld de kop en de staart willen toewijzen aan variabelen dan kunnen we de volgende vraag stellen: Het anwoord is dan: Je ziet dat de variabele Head wordt geünificeerd met kop geert en Tail wordt gelijkgesteld aan de staart. Head en Tail zijn slechts duidelijke namen voor variabelen, echter zonder speciale betekenis. We hadden net zo goed kunnen vragen Eerder hadden we al opgemerkt dat alleen niet lege lijsten een kop en staart hebben. Als we met de | operator de lege lijst willen op splitsen dan gaat het fout: Prolog behandelt [] dus als een speciale lijst. Dit is een belangrijk punt. We zullen later zien waarom.

We bekijken nog een aantal voorbeelden. We kunnen de head en tail op dezelfde manier uit de volgende lijst halen

De kop wordt aan X gekoppeld, de staart aan Y en Z is aan een nog niet gevulde interne variabele gekoppeld.

Maar we kunnen nog veel meer doen met |, het is een zeer flexibel gereedschap.
Als we bijvoorbeeld willen weten wat de eerste twee elementen van een lijst zijn, en de rest van de lijst ook willen bewaren dan kunnen we de volgende vraag stellen: Het eerste element van de lijst [] wordt dus toegewezen aan X, het tweede aan Y en de staart wordt W. We kunnen de | operator overal in de lijst plaatsen onder de voorwaarde dat er links een aantal komma gescheiden variabelen komen die en rechts een variabele voor wat er overblijft.

Dit is ook een goed moment om de anonieme variabele te introduceren. Stel dat we alleen geïnteresseerd zijn in het tweede en het vierde element uit de lijst We kunnen dit als volgt opvragen We hebben nu de informatie die nodig was, X2 en X4 zijn gekoppeld aan de gewenste informatie. Maar we kregen ook extra informatie die we niet nodig hebben (X2,X3,Tail en Z), overbodig dus. Er is een simpele manier om die informatie te negeren door gebruik te maken van de anonieme variabele (_): We gebruiken de anonieme variabele als we een variabele nodig hebben maar niet geïnteresseerd zijn in de informatie die Prolog er aan koppelt. In het antwoord zie je dat er geen waarde aan _ gekoppeld is. Sterker nog iedere _ is "onafhankelijk" want er moeten verschillende waarden worden gekoppeld. Een ander variabele in de plaats van _ plaatsen is meestal onmogelijk.

We kijken nog naar een laatste voorbeeld. Het derde element in het voorbeeld hierboven is een lijst namelijk [ bloemen, [bedel, ketting]]. Sel we willen de staart hebben van deze interne lijst, de rest hoeven we niet te weten. De volgende vraag geeft ons deze informatie

Member

Het wordt tijd om een eerste voorbeeld te bekijken van een recursief Prolog programma dat lijsten manipuleert. Het meest basale in het wat je met lijsten wil doen, is kijken of een element in de lijst aanwezig is. Prolog heeft voor het behandelen van lijsten een aantal ingebouwde predicaten. Één daarvan is het predicaat member/2 (member = lid) dat ons vertelt of een willekeurig gekozen object X in lijst Y aanwezig is. Dit predicaat is het meest simpele programma dat recursief door lijsten heen loopt. Om het algemeen gevoel van lijst programmeren te verkrijgen zullen we diep ingaan op de werking van dit predicaat. Het predicaat member/2 zou in Prolog als volgt gedefinieerd kunnen worden:

Dit is alles, een feit ( member(X,[X|T]) ) en één clausule ( member(X,[H|T]) :- member(X,T) ). Je ziet dat de clausule recursief is ( de functor is aanwezig zowel in de head en de body ) en deze recursie verduidelijkt waarom zo'n kort programma is alles wat nodig is. Zie je al meteen waarom het werkt? Zo niet dan hopelijk wel na de volgende beschouwing.

We bekijken het eerst declaratief en als je dit doet dan merk je dat het een zinvolle betekenis heeft. De eerste clausule ( het feit ) zegt namelijk: een object X maakt deel uit van de lijst ( [X|T] ) als het object het eerste element is in de lijst. Je ziet hier weer het nut van de | operator.

De tweede clausule, de recursieve regel zegt: een object X maakt deel uit van de lijst [ H|T ] als het een element is van de staart van de lijst. Merk op dat H niet gelijk is aan X. Je ziet dat we de | operator weer gebruiken om de lijst op te delen.

Deze definitie is intuïtief duidelijk. Als X deel uitmaakt van de lijst dan is X is het eerste element in de lijst of zit verderop in de lijst. Maar ja als we de vraag stellen willen we wel weten of X er echt in zit. Is dit programma dan voldoende om dit te ontdekken? Om dit in te zien moeten we de procedurele kant van het programma bekijken. We doen dit aan de hand van een paar voorbeelden.

We stellen een eerste vraag:

Prolog komt nu gelijk met het antwoord true. Waarom? Het tweede argument in de eerste regel (het feit) is [ madelief | [roos,hyacint,tulp] ]. Omdat madelief = madelief is dit dus een waarheid.

De volgende vraag:

De eerste regel helpt nu niet (hyacint en madelief zijn verschillende atomen), dus Prolog gaat naar de tweede recursieve clausule. Dit geeft Prolog een nieuw doel, namelijk de vraag te beantwoorden. Ook hier kan niet de eerste clausule door Prolog worden ingezet ( hyacint en roos zijn verschillende atomen) en dus gaat Prolog nog een keer met de recursieve clausule aan de slag en komt er weer een nieuw doel Nu kan Prolog wel de eerste clausule inzetten en kan de vraag dus met true beantwoorden.

Tot nu toe alles goed, maar we moeten ook nog even kijken wat er gebeurt als we een vraag stellen die geen positiev antwoord heeft. Bijvoorbeeld de vraag:

Het is duidelijk, zonnebloem zit er niet in dus falsemoet het antwoord zijn. Maar hoe komt Prolog daartoe en komt Prolog niet in een oneindige recursieve lus?

Laten we het eens systematisch doordenken. De eerste clausule werkt in eerste instantie niet en zal Prolog net als in het vorige voorbeeld achterelkaar de recursieve clausule inzetten: ?- member(zonnebloem,[roos,hyacint,tulp]). ⇒ ?- member(zonnebloem,[hyacint,tulp]). ⇒ ?- member(zonnebloem,[tulp]).. Ook bij de laatste vraag kan Prolog de eerste clausule niet inzetten en clausule twee geeft dan de doelvraag:

Hier wordt het interessant. Ook hier werkt de eerste clausule niet, maar ook de tweede clausule werkt niet want de lege lijst [] kan niet in een kop en staart worden verdeeld. Er is nu geen enkele clausule meer over die Prolog kan gebruiken, dus geeft Prolog het antwoord false. Precies wat we willen.

Het predicaat member/2 kunnen we dus als volgt samenvatten. Member/2 is een recursief predicaat, dat systematisch een zoektocht van links naar rechts ( of van kop naar staart ) op zoek gaat naar de het gewenste object. In de zoektocht wordt stapsgewijs de lijst waarin gezocht wordt steeds kleiner gemaakt. Dit woordt veroorzaakt door de recursie in de tweede clausule. De reden dat dit een veilig predicaat is (eindig) komt door de ondeelbaarheid van de lege lijst.

We hebben nu gezien waarom member/2 werkt, maar het predicaat kan ons nog meer leveren dan de ja/nee antwoorden bij de vragen uit ons bloemen voorbeeld. Net als in de familiestamboom kunnen we ook vragen met variabelen stellen. De vraag

geeft de antwoorden Prolog geeft ons hier dus alle elementen uit de lijst als antwoord. Het gebruik van het member/2 predicaat met een variabele wordt heel vaak ingezet in Prolog programmeren met lijsten. In heel veel Prolog applicaties moeten er elementen uit lijsten worden gehaald en dit is meestal de manier om dit te doen.

Nog een laatste opmerking. De manier waarop we member/2 hebben gedefinieerd is zeker goed, maar in één opzicht een beetje rommelig. De eerste clausule is er om alleen iets te doen met de kop (head) van de lijst. De staart is compleet irrelevant. Evenzo is in de tweede recursieve clausule de head onbelangrijk. We kunnen in de definitie de anonieme variabele (_) inzetten om dit te verduidelijken

In deze definitie zie je in de clausules direct de belangrijkste argumenten.

Recursie door lijsten

Het member/2 predicaat hierboven werkt zich dus recursief door de lijst heen van kop (links) tot het puntje van de staart (rechts). Recursie door lijsten is hèt proces dat het meest gebruikt wordt in serieuze vormen van het gebruik van Prolog. In de hoofdstukken over taalverwerking zul je daarmee overspoeld worden. Het is dus van belang dat je dat recursieve programmeren goed in de vingers krijgt. Laten we dus nog maar een voorbeeld bekijken om je meer vertrouwd te maken.

Als je met lijsten werkt wil je vaak lijsten met elkaar vergelijken, delen van één lijst kopiëren naar een andere, lijsten vertalen of iets dergelijks. Stel we hebben een predicaat a_op_b/2 dat twee lijsten als argument heeft. Het predicaat is succesvol als de lijst in het eerste argument alleen uit a's bestaat en de tweede alleen uit b's bestaat en beide lijsten even lang zijn. Als we de vraag

stellen moet Prolog true als antwoord geven, maar bij de vragen en willen we dat Prolog false als antwoord geeft.

Als je zo'n taak moet programmeren, is meestal de best manier om te beginnen met het meest simpele geval. Als je met lijsten werkt moet je bij de het meest simpele geval denken aan de lege lijst ([]). In ons voorbeeld is dit zeker het geval. Want wat is de kortste lijst die alleen maar a's bevat? Dat is de lege lijst, die bevat namelijk 0 a's. Evenzo is de lege lijst de lijst met het minste aantal b's. Twee lege lijsten hebben bovendien allebei lengte 0. Dus hebben we als eerste clausule het feit: Je zult zien dat dit feit een belangrijke rol speelt in ons programma.

Maar hoe nu verder? Het idee is als volgt: voor langere lijsten denk recursief op zo'n manier dat iedere stap de lijst korter wordt. Als a_op_b waar moet zijn bij langere lijsten dan moet in ieder geval het eerste element (head) van het eerste argument een a zijn en het eerste element (head) van het tweede argument een b. Als dit zo is strippen we de koppen van de lijsten en vervolgen we onze zoektocht naar de waarheid in de staarten.

Het hele programma wordt dan: Deze definitie is declaratief gezien zinvol. De basis clausule houdt zich bezig met de lege lijst en de tweede met niet lege lijsten. Hoe werkt dit programma nu procedureel? Om dit te beantwoorden geven we weer een paar voorbeeld vragen. Eerst maar een vraag die een positief antwoord geeft: Weet je al wat er door Prolog wordt gedaan om dit antwoord te produceren? Is jouw antwoord volledig positief, geweldig, je hebt al in de vingers. Zo niet, lees dan verder.

[a,a,a] en [b,b,b] zijn geen lege lijsten dus wordt de tweede clausule ingezet. Nu is [a,a,a] gelijk aan [a|[a,a]] en is [b,b,b] gelijk aan [b|[b,b]] De vraag is dan gelijkwaardig met de vraag Beide lijsten voldoen dus aan de eisen in de argumenten van de clausule. Het volgende doel wordt dan Nog steeds geen lege lijst in beeld, dus weer door met de recursieve clausule via naar het doel De lijsten [a] (=[a|[]]) en [b] (=[b|[]) zijn niet leeg steeds en moet Prolog de recursieve clausule weer toepassen. De vraag leidt nu tot het doel Dit is de eerste clausule dus Prolog beantwoordt de oorspronkelijke vraag dus met true.

We kunnen het proces als volgt samenvatten. Prolog startte het proces met twee lijsten. In het recursieve proces werden steeds de eerste elementen van beide lijsten afgehaald omdat die met de juiste elementen begonnen. Uiteindelijk waren er twee lege lijsten over en wad het basis clausule die het succes voor zijn rekening nam.

Het is ook belangrijk om na te denken wat er gebeurt als een vraag een negatief resultaat heeft. Wat gebeurt er bijvoorbeeld bij de vraag

Prolog komt tot het juiste resultaat false door eerst een aantal keren succesvol de recursieve clausule in te zetten: Bij de laatste vraag kan Prolog geen van de beschikbare clausules inzetten. De basis clausule heeft twee lege lijsten nodig en de recursieve twee niet lege lijsten. Nu hebben we een niet lege en een lege lijst als argument. Dus kan Prolog geen positieve conclusie trekken en geeft dus false als antwoord.

Anders verloopt het bij de vraag

De eerste keer kan Prolog de tweede clausule toepassen want de eerste lijst begint met een a en de tweede met een b , dit leidt tot het tussendoel Nu kan Prolog niets meer doen. De lijsten zijn niet leeg en de atomen 2 en a zijn niet gelijk ( niet te unificeren). Wederom kan Prolog geen positieve conclusie trekken.

Kunnen we a_op_b/2 net als member/2 ook nog gebruiken met variabelen? Ook dat is mogelijk.

geeft als antwoord X=[b,b,b,b]. De lijst van a's is dus vertaald naar een lijst van b's. Met de vraag is die vertaling juist andersom, X=[a,a,a,a] is de lijst. Kun je ook bedenken wat de antwoorden zijn op de volgende vragen (maak de antwoorden in Swish)? Wat hebben we geleerd? a_op_b is een eenvoudig voorbeeld van een programma dat op een recursieve manier door een tweetal lijsten heen gaat. Maar laat je niet misleiden door deze eenvoudigheid. Deze manier van programmeren vormt het fundament van Prolog. Zowel de declaratieve vorm ( een basis clausule die de lege lijst beschouwd en een recursieve voor de niet lege lijst) als het procedurele idee ( doe iets met de head van de lijst, doe vervolgens recursief het zelfde met de tail ) komen keer op keer naar voren in Prolog programmeren. Sterker nog, in de loop van jouw carrière als Prolog programmeur, zul je ervaren dat je eigenlijk iedere keer weer het a_op_b/2 predicaat of een iets complexere variant aan het schrijven bent, maar dan onder een andere naam.

Vragen

vragen