Listor i Prolog

En av de enklaste och mest anvandbara strukturerna i prolog ar listor. En lista ar en sekvens av n antal av foremal t.ex. kalle, slalom, olle, tennis kan skrivas som [kalle ,slalom, olle, tennis] nar de representeras i en lista.

• Det forsta foremalet i en lista kallas huvud. Huvudet i foregaende lista ar kalle

• Den resterande delen kallas svansen I ovan exempel [slalom, olle, tennis]

Huvudet kan egentligen vara vad som helst ett trad eller variabel men svansen maste vara en lista. En lista kan skrivas pa detta vis

.(Head, Tail)

Sa var exempellista tidigare ser nu ut pa detta vis

.(kalle, .(slalom, .(olle, .(tennis, []))))

Dar [] ar den tomma listan.

Operationer som kan goras pa en lista

• Testa om ett element ar medlem av listan
• Sla ihop tva listor (concatinate)
• Lagga till ett objekt i listan
• Ta bort ett objekt fran listan

Om vi nu implementerar medlemskaps relationen som

medlem(X, List

Dar X ar ett object och List ar en lista, medlem blir sann om X ar en medlem av listan.

medlem(b, [a, b]

blir sann, men

medlem(b, [a, [a, b]]

blir falsk for b ingar i mangden av [a, b]och vi kan inte hitta b daremot blir

medlem([a, b], [a, [a, b]]

sann.
Programmet for medlems relationen baseras pa foljande fakta
X ar en medlem av List om:

1.

X ar huvudet pa listan

2.

X ar en medlem av svansen pa listan

Detta kan skrivas ned i programmet med hjalp av ett predikat med tva klausuler

medlem( X, [X | Tail]).

medlem(X, [Head | Tail]) :-
medlem(X, Tail).

Detta sager att om X inte ar det forsta elementet i listan sa kan det vara ett element i resten av listan och om det ar sant sa ar aven det forsta pastaendet sant.

Sammanslagning av tva listor

For sammanslagningen (concatination) av tva listor definieras relationen

conc(L1, L2, L3)

Dar L1 och L2 ar tvalistor och L3 ar sammanslagningen av dessa

conc([a, b], [c, d], [a, b, c, d])

blir sann

conc([a, b], [c, d], [a, b, a, c, d])

blir falsk

I definitionen pa conc finns det tva fall beroende pa det forsta argumentet

1.

Om det forsta argumentet ar den tomma listan da maste det andra och tredja argumentet vara samma lista (jmfr: 0 + 1 = 1 ) Detta uttrycks i prolog som

conc([], L, L)

Vilket enbart betyder om den tomma listan slas ihop med L fas L

2.

Om det forsta argumentet i conc inte ar tomt da har listan ett huvud och en svans och kan skrivas som

[X | L1]

Resultatet av sammanslagningen ar listan [X | L3] dar L3 ar sammanslagningen av L1 & L2. I prolog skrivs det som

conc(X | L1], L2, [X | L3]) :-
conc(L1, L2, L3).

Detta program kan nu anvandas for att sla samman listor och exempel pa provkorning av programmet visas nedan

21 ?- conc([a, b, c], [1, 2, 3], L).

L = [a, b, c, 1, 2, 3] 


Yes
22 ?- conc([a, [b, c], d], [a, [], b], L).

L = [a, [b, c], d, a, [], b]

Programmet kan aven anvandas for att finna ett speciellt monster i en lista t.ex
Vi kan finna den dag som infaller fore och den dag som infaller efter en given dag i veckan som i nedanstaende fraga:

23 ?- conc(Before, [ onsdag | After],
|    [mandag, tisdag, onsdag, torsdag, fredag, lordag, sondag]).

Before = [mandag, tisdag]
After = [torsdag, fredag, lordag, sondag] ;

Eller kan vi fraga om den dag som kommer fore och efter vald dag (i denna korning fredag):

24 ?- conc(_, [Dagfore, fredag, Dagefter | _],
|    [mandag, tisdag, onsdag, torsdag, fredag, lordag, sondag]).

Dagfore = torsdag
Dagefter = lordag

Lagga till ett objekt i en lista

For att lagga till ett objekt i en lista ar det enklast att lagga objektet i borjan pa listan sa att det blir det nya huvudet. Om X ar det nya objektet och listan som X skall laggas in i ar L da blir den resulterande listan.
<#137#>[X | L]
Om vi skall definiera en procedure som lagger objektet forst i listan ser det ut pa detta vis:
add(X, L, [X | L]).
Vilket kan tolkas som
lagga till X till Y ger den nya listan [X | L] med X som huvud.

Ta bort ett objekt i en lista

Nar man tar bort ett objekt fran en lista kan det programmeras som en relation:
del(X, L, L1).
Kan lasas som
Ta bort X fran listan L vilket ger den nya listan L1
delete relationen kan programmeras pa liknade satt som medlemsrelationen vi har igen tva fall:

1.

Om X ar huvudet pa listan da blir resultatet efter bortagningen svansen pa listan L.

2.

Om X finns i svansen pa listan da skall den tas bort darifran.

del(X, [X | Tail], Tail).
del(X, [Y | Tail], Y |Tail1]) :- del(X, Tail, Tail1).

Liksom medlem kan inte del avgora om det ar ratt objekt som den vill ta bort. Om det finns flera mojligheter av X kan inte prolog avgora vilken som skall tas bort och det resulterar i vilket som helst av objekten tas bort men bara ett den tar inte bort alla forekomster av X.
Ett exempel pa detta ges i nedanstaende programkorning

2 ?- del(a, [a, b, a, a], L).

L = [b, a, a] ;

L = [a, b, a] ;

L = [a, b, a] ;

No
3 ?-

del kan ocksa anvandas i motsatt riktning for att lagga till ett objekt i listan genom att placera den var som helst i listan t.ex om vi vill placera in a vart som helst i listan [a, b, c] kan vi gora det genom att fraga Hur ser listan ut efter att ha tagit bort a fran L och vi far.

3 ?- del(a, L, [b, c, d]).

L = [a, b, c, d] ;

L = [b, a, c, d] ;

L = [b, c, a, d] ;

L = [b, c, d, a] ;

No
4 ?-

Detta som att placera in X vart som helst i listan kan aven skrivas som klausulen:

insert(X, List, Biggerlist) :-
del(X, BiggerList, List).