Λίστες

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

Μέχρι το κεφάλαιο αυτό για να αναπαραστήσουμε μία λίστα αντικειμένων χρησιμοποιούσαμε τη δομή του ατομικού τύπου γράφοντας κάθε στοιχείο της λίστας ως ξεχωριστό γεγονός. Για παράδειγμα, αν θέλαμε ν' αναπαραστήσουμε τη λίστα kostas, marios, petros, vangelis ως ξαδέλφια του dimitris θα γράφαμε τα γεγονότα:

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

Ένας άλλος αναδρομικός τρόπος αναπαράστασης μίας λίστας, είναι αυτός με τη χρήση σύνθετου όρου της μορφής:

όπου i1 είναι το πρώτο στοιχείο της λίστας και Χ είναι είτε μία λίστα της ίδιας μορφής list(iκ, X) είτε ένα άτομο το οποίο να συμβολίζει το τέλος της λίστας (για παράδειγμα end_list).

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

Έτσι η λίστα του παραπάνω παραδείγματος μπορεί ν' αναπαρασταθεί από τo σύνθετο όρο:

cousine(kostas, cousine(marios, cousine(petros, cousine(vangelis,end_list))))

Ενώ το γεγονός ότι ο Δημήτρης έχει ξαδέλφια τα παραπάνω πρόσωπα αναπαρίσταται από το σύνθετο όρο:

cousines_of(dimitris, cousine(kostas, cousine(marios, cousine(petros, cousine(vangelis,end_list))))).

Όπως θα δούμε στην επόμενη ενότητα, η αναπαράσταση μίας λίστας με τον τρόπο αυτό έχει ως αποτέλεσμα τον πιο εύκολο χειρισμό των στοιχείων της μέσω μίας ομάδας πράξεων.

Η δομή της λίστας

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

[item1, item2, ..., itemn]

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

cousins_of(dimitris, [kostas, marios, petros, vangelis]).

Γενικότερα, μία λίστα στη Prolog αναπαριστάται ως:

[Head | Tail]

Όπου Head αναπαριστά τον πρώτο όρο (κεφαλή) της λίστας και και Tail τα υπόλοιπα στοιχεία της λίστας (η ουρά της λίστας). Ως κεφαλή μίας λίστας μπορεί να είναι ένας οποιοσδήποτε όρος της Prolog (μεταβλητή, σταθερά, ατομικός τύπος, σύνθετος όρος ή ακόμα και μία λίστα), ενώ ως ουρά της λίστας είναι πάντα μία λίστα της ίδιας μορφής [Head| Tail]. Μία λίστα χωρίς στοιχεία την αναπαριστούμε με [].

Κάνοντας χρήση του αναδρομικού αυτού ορισμού της λίστας συμπεραίνουμε ότι κάθε στοιχείο μίας λίστας μπορεί να είναι είτε μία μεταβλητή, είτε μία σταθερά, είτε ένας ατομικός τύπος, είτε ένας σύνθετος όρος και άρα είτε μία λίστα (κενή ή όχι).

Οι παρακάτω αναπαραστάσεις μίας λίστας είναι ισοδύναμες (δηλαδή ταυτίζονται μεταξύ τους):

[item1,item2,item3,item4]

[item1|[item2,item3,item4]]

[item1,item2|[item3,item4]]

[item1,item2,item3|[item4]]

[item1,item2,item3,item4|[]]

[item1|[item2|[item3,item4]]]

[item1|[item2,item3|[item4]]]

[item1|[item2,item3,item4|[]]]

[item1,item2|[item3|[item4]]

[item1,item2|[item3,item4|[]]]

[item1,item2,item3|[item4|[]]]

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

[item1,item2,item3,item4]

[item1,[item2,item3],item4]

[item1,[item2,item3,item4]]

[item1,item2,item3,item4,[]]

γιατί η πρώτη λίστα έχει τέσσερα στοιχεία ενώ η δεύτερη έχει τρία (το item1, τη λίστα [item2,item3] και το item4), η τρίτη έχει δύο στοιχεία (το item1 και τη λίστα [item2,item3,item4]) και η τέταρτη έχει πέντε στοιχεία (σε αντίθεση με τη λίστα [item1,item2,item3,item4|[]] που έχει τέσσερα στοιχεία).

Αν για μία λίστα γνωρίζουμε τα N πρώτα στοιχεία της αλλά όχι τα υπόλοιπά στοιχεία της (ή απλά δεν μας ενδιαφέρουν) τότε η ουρά της λίστας αναπαριστάτε με μία μεταβλητή, δηλαδή γράφουμε:

[item1,item2,...,itemN | List ]

Για παράδειγμα αν έχουμε το παρακάτω γεγονός το οποίο αναπαριστά τις ποσότητες υλικού που παρήγγειλε ένας πελάτης:

orders_of( client(papadopoulos), [order(cpu,43), order(motherboard,23), order(monitor,61), order(hard_disk,72), order(memory,41) ] ).

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

?- orders_of(client(papadopoulos), [order(Item1,X), order(Item2,Y) | _RestList ]).

Ενώ αν θέλουμε να προσθέσουμε μία ακόμα ποσότητα για ένα υλικό τότε γράφουμε:

?- retract( orders_of(client(papadopoulos), List) ),
   assert( orders_of(client(papadopoulos), [order(keyboard,50) | List]) ).

Η εντολή retract έχει ως αποτέλεσμα να διαγράψει το γεγονός αυτό από τη βάση, ενώ η εντολή assert έχει ως αποτέλεσμα να επανεισάγει το γεγονός ενημερωμένο με τη νέα παραγγελία order(keyboard,50).