Οι δομές δεδομένων χρησιμοποιούνται για να οργανώσουν δεδομένα μ' έναν κατανοητό τρόπο και είναι σημαντικές στον προγραμματισμό γενικά, αλλά και στον προγραμματισμό ειδικότερα. Τα δομημένα αντικείμενα (structured objects) ή απλά δομές (structures), είναι αντικείμενα τα οποία έχουν αρκετά τμήματα (components) τα οποία, με τη σειρά τους, ενδέχεται να είναι δομές. Στο λογικό προγραμματισμό υπάρχουν δύο είδη δομών: οι σύνθετοι όροι (compound terms) και οι λίστες (lists). Η λίστα αποτελεί ειδική περίπτωση σύνθετου όρου.
Ας εξετάσουμε δύο τρόπους αναπαράστασης ενός γεγονότος που αφορά ένα μαθητή που ονομάζεται Tom Smith, έχει γεννηθεί την
πρώτη του Μάη του 1980 και παρακολουθεί μαθήματα Θεωρίας Αλγορίθμων (algorithms), προγραμματισμού σε Prolog καθώς και
τηλεπικοινωνιών (telecommunications).
Η πρώτη αναπαράσταση περιέχει τα προαναφερθέντα δεδομένα σε μη δομημένη μορφή. Η δεύτερη περιέχει σύνθετους όρους για να παραστήσει ακριβώς τα ίδια δεδομένα, αλλά σε πιο δομημένη μορφή.
'Ενα από τα σημαντικότερα χαρακτηριστικά του λογικού προγραμματισμού είναι η ικανότητά του να χειρίζεται λίστες όρων. Οι λίστες
υλοποιούνται χρησιμοποιώντας ένα ειδικό δυαδικό (τάξης 2) σύμβολο συνάρτησης, το ``.'', και μια ειδική σταθερά, τη ``nil'', η
οποία παριστάνει την κενή λίστα. Μια λίστα είναι είτε κενή (nil), είτε το πρώτο όρισμά της είναι ένα στοιχείο ενώ το δεύτερο μια λίστα.
'Ετσι, η λίστα τριών στοιχείων p, q, r, παριστάνεται από τον όρο .(a, .(b, .(c, nil))). Για να απλουστεύσουμε το συμβολισμό
μας, χρησιμοποιούμε μια ειδική σύνταξη κατά την οποία ο όρος .(X, Y) γράφεται [X|Y]. Το X ονομάζεται
κεφαλή (head) της λίστας και το Y ουρά (tail).
Σαν παράδειγμα χρήσης λιστών, δίνουμε ένα πρόγραμμα που συνενώνει δύο λίστες [Head|Tail1] και List δίνοντας
τη λίστα [Head|Tail2]:
Ο στόχος
?- append([s, t, u], [x, y], L).
παράγει την απάντηση
L = [s, t, u, x, y].