Διαδικασίες με λίστες

Στη προηγούμενη ενότητα είδαμε πως μπορούμε ν' αναπαραστήσουμε μία λίστα γεγονότων. Στην ενότητα αυτή θα δούμε πως μπορούμε να χειριστούμε τις λίστες κάνοντας χρήση ενός συνόλου διαδικασιών οι οποίες μας επιτρέπουν να εξάγουμε στοιχεία από μία λίστα, να εισάγουμε νέα, να διαγράψουμε στοιχεία, να ενώνουμε λίστες και να τις αντιστρέφουμε. Οι διαδικασίες αυτές θεωρούνται βασικές διότι οι περισσότερες διαδικασίες χειρισμού λιστών κάνουν χρήση αυτών.

Μέλος λίστας

Η πιο χρήσιμη διαδικασία είναι αυτή της "μέλους λίστας". Δεδομένου μίας λίστας αυτό που μας ενδιαφέρει είναι να εξετάσουμε αν ένα συγκεκριμένο στοιχείο είναι μέλος της λίστας ή όχι.

Ένα στοιχείο Χ είναι μέλος μίας λίστας L αν:
είτε είναι η κεφαλή της λίστας (δηλαδή το πρώτο στοιχείο της),
είτε είναι μέλος της ουράς τής λίστας.

Ο παραπάνω αναδρομικός τρόπος ορισμού του μέλους μίας λίστας υλοποιείται με τον ακόλουθο τρόπο:

member(X, [Y|_Tail]):- X=Y.
member(X, [Head | Tail]):- member(X, Tail).

Η πιο απλά γράφοντας:

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

Παρατηρείστε ότι κατά τη στιγμή της ενοποίησης του Χ με το πρώτο στοιχείο της λίστας, αν η Χ είναι ελεύθερη τότε παίρνει τη τιμή του πρώτου στοιχείου της λίστας, ενώ αν η Χ είναι δεσμευμένη (δηλαδή ο χρήστης έχει δόσει ήδη τιμή σ' αυτή) τότε ελέγχει αν η Χ ταυτίζεται με το πρώτο στοιχείο της λίστας. Για το λόγω αυτό, το κατηγόρημα member/2 μπορεί να χρησιμοποιηθεί:

1. είτε για να εξάγουμε ένα-ένα τα στοιχεία μίας λίστας,
2. είτε για να ελέγχουμε αν ένα στοιχείο είναι μέλος μίας λίστας.

Στη πρώτη περίπτωση το input είναι η λίστα L, ενώ το output είναι το στοιχείο Χ. Στη δεύτερη περίπτωση το κατηγόρημα member δέχεται ως input τόσο τον όρο Χ όσο και τη λίστα L, ενώ το output είναι η απάντηση που δίνει η Prolog (δηλαδή αν το στοιχείο X είναι μέλος της λίστας ή όχι).

Για παράδειγμα αν κάνουμε την ακόλουθη ερώτηση:

?- member(X, [1,2,a,b]).

Τότε κάνοντας διαδοχικά backtracking (όποτε πατάμε το ;) η Prolog απαντά:

Χ = 1 ;
Χ = 2 ;
Χ = a ;
Χ = b ;

No

Ενώ αν κάνουμε την ερώτηση:

?- member(2, [1,2,a,b]).
Yes

Τότε η Prolog απλά ελέγχει αν το στοιχείο 2 είναι μέλος της λίστας.

Αν το πρόβλημά δεν μας επιτρέπει τη χρήση backtracking, ένας εναλλακτικός τρόπος να παίρνουμε τα στοιχεία μίας λίστας, είναι ν' αναλύσουμε τη λίστα στο πρώτο στοιχείο της και την ουρά της, να κάνουμε τη πράξη που θέλουμε και μετά να επαναλαμβάνουμε το ίδιο για τα υπόλοιπα στοιχεία της λίστας.

Για παράδειγμα, το επόμενο πρόγραμμα παίρνει ένα-ένα τα στοιχεία μίας λίστας και τα τυπώνει στην οθόνη:

print_list([X|L]):-
   writeln(X),
   print_list(L).

print_list([]).

Εισαγωγή νέου στοιχείου

Η εισαγωγή ενός νέου στοιχείου X σε μία λίστα L είναι εύκολη: αρκεί να δημιουργήσουμε μία καινούργια λίστα που ως ουρά θα έχει τη λίστα L και κεφαλή το στοιχείο X.

Η διαδικασία αυτή υλοποιείται από το γεγονός:
add(X,L, [X|L]).

Παραδείγματα:

?- add(a,[1,2,b],List).
List = [a,1,2,b]

?- add([0,8],[1,2,b],List).
List = [[0,8],1,2,b]

Διαγραφή στοιχείου

Η διαγραφή ενός στοιχείου X από μία λίστα L πραγματοποιείται αντιγράφοντας τα στοιχεία της λίστας σε μία καινούργια λίστα εκτός του στοιχείου X. Η υλοποίηση της διαδικασίας del/3 δίνεται από το παρακάτω αναδρομικό κανόνα:

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

Η del/3 διαγράφει μόνο το πρώτο στοιχείο που θα βρει στη λίστα, ενώ αν δεν βρει κανένα στοιχείο τότε αποτυχαίνει. Για παράδειγμα:

?- del(c, [a,3,c,f,c,t], List).
List = [a,3,f,c,t]

Παράθεση λιστών

Η επόμενη πιο χρήσιμη διεργασία είναι αυτή της παράθεσης δύο λιστών. Έστω δύο λίστες διαφορετικού μήκους [a1, a2, ..., aN] και [b1, b2, ..., bM] το κατηγόρημα concat/3 (concatenation) ενώνει τις δύο λίστες δημιουργώντας μία καινούργια κρατώντας τη σειρά των στοιχείων τους: [a1, a2, ..., aN, b1, b2, ..., bM].

Πιο συγκεκριμένα, μία λίστα L είναι παράθεση δύο λιστών L1 και L2 όταν:

1. είτε η πρώτη λίστα L1 είναι κενή και η δεύτερη λίστα L2 ταυτίζεται με την L,
2. είτε όταν η κεφαλή της L1 ταυτίζεται με τη κεφαλή της L και η ουρά της L είναι παράθεση της ουράς της L1 με ολόκληρη τη λίστα L2.

Η παραπάνω διαδικασία υλοποιείται από το ακόλουθο πρόγραμμα:

concat(L1, L2, L):- L1=[], L2=L.
concat(L1, L2, L):- L1=[X|Tail1], L=[Y|Tail], X=Y, concat(Tail1, L2, Tail).

ή πιο απλά από το πρόγραμμα:

concat([], L, L).
concat([X|Tail1], L2, [X|Tail]):- concat(Tail1, L2, Tail).

Όπως και με τη διαδικασία member, λόγω του ότι το σύμβολο της ενοποίησης "=" χρησιμοποιείται με διττό τρόπο το παραπάνω πρόγραμμα μπορεί να χρησιμοποιηθεί για να:

1. να ελεγχθεί αν μία λίστα είναι παράθεση δύο άλλων λιστών,
2. να ενώσει δύο λίστες σε μία,
3. να διαχωρίσει μία λίστα σε δύο.

Στη τελευταία περίπτωση η Prolog μας δίνει όλες τις δυνατές περιπτώσεις. Για παράδειγμα:

?- concat(L1,L2,[a,b,c,d]).
L1 = []
L2 = [a, b, c, d] ;
L1 = [a]
L2 = [b, c, d] ;
L1 = [a, b]
L2 = [c, d] ;
L1 = [a, b, c]
L2 = [d] ;
L1 = [a, b, c, d]
L2 = [] ;

No

Αντιστροφή λίστας

Δεδομένης μίας λίστας L το κατηγόρημα reverse/2 αντιστρέφει τη λίστα αυτή.

Η αντιστροφή λιστών μπορεί να υλοποιηθεί με δύο τρόπους:

Πρώτος τρόπος:

Ο πρώτος τρόπος κάνει χρήση της concat/3. Πιο συγκεκριμένα, με αναδρομικό τρόπο για να αντιστρέψουμε μία λίστα L:
(α) τη διασπούμε στη κεφαλή της και την ουρά της,
(β) αντιστρέφουμε την ουρά της και
(γ) ενώνουμε την ανεστραμμένη αυτή λίστα της ουράς με τη κεφαλή τής L.

Η διαδικασία αυτή υλοποιείται από το παρακάτω πρόγραμμα:

reverse([], []).
reverse([X|Tail], RList):-
       reverse(Tail, RTail),
       conca(RTail, [X], RList).

Ο δεύτερος (και πολύ πιο γρήγορος) τρόπος, κάνει χρήση μίας βοηθητικής δομής, αυτής της στοίβας. Θεωρούμε τη λίστα L ως μία στοίβα τα στοιχεία της οποίας τα εξάγουμε ένα-ένα και τα τοποθετούμε σε μία βοηθητική κενή στοίβα S.

Έτσι για ν' αντιστρέψουμε τα στοιχεία μίας λίστας L δημιουργώντας μία λίστα RList αρκεί:

(α) να διασπάσουμε τη λίστα L στη κεφαλή της και την ουρά της,
(β) να τοποθετήσουμε τη κεφαλή τής L στη κορυφή της βοηθητικής στοίβας S και τέλος
(γ) ν' αντιστρέψουμε τα υπόλοιπα στοιχεία της L (δηλαδή την ουρά τής L) ακολουθώντας πάλι τα δύο παραπάνω βήματα.

Η διαδικασία αυτή υλοποιείται από το παρακάτω πρόγραμμα:

reverse(L, RList):- reverse(L, [], RList).

reverse([], RList, RList).
reverse([X|Tail], S, RList):-
       reverse(Tail, [X|S], RList).

Για παράδειγμα:

?- reverse([1,2,3,X,a], RList).

RList = [a, X, 3, 2, 1] ;

No