Αλγεβρικός τύπος δεδομένων

Στον προγραμματισμό υπολογιστών και συγκεκριμένα στον συναρτησιακό προγραμματισμό και τη θεωρία τύπων, ο αλγεβρικός τύπος δεδομένων (επίσης γνωστός ως variant τύπος) είναι ένας τύπος δεδομένων καθεμία από τις τιμές του οποίου είναι δεδομένο από άλλους τύπους δεδομένων που περιέχεται σε έναν από τους κατασκευαστές του τύπου δεδομένων. Οποιοδήποτε περιεχόμενο δεδομένο είναι όρισμα του κατασκευαστή. Σε αντίθεση με άλλους τύπους δεδομένων, ο κατασκευαστής δεν μπορεί να γίνει αντικείμενο επεξεργασίας και ο μόνος τρόπος επεξεργασίας των περιεχόμενων δεδομένων είναι η αφαίρεση του κατασκευαστή με ταίριασμα μορφοτύπων.
Ο πιο κοινός αλγεβρικός τύπος δεδομένων είναι η λίστα, με δύο κατασκευαστές: Nil or [] για την κενή λίστα, και Cons (μια συντομογραφία του construct), ::, ή : για το συνδυασμό ενός νέου στοιχείου με μια λίστα προς δημιουργία μιας νέας διακριτής λίστας (για παράδειγμα Cons 1 [2, 3, 4] ή 1:[2,3,4]).
Ειδικές περιπτώσεις αλγεβρικών τύπων είναι οι τύποι γινομένου όπως οι πλειάδες και οι εγγραφές (που έχουν μόνο έναν κατασκευαστή), οι τύποι αθροίσματος ή tagged unions (πολλοί κατασκευαστές με μοναδικό όρισμα) και οι τύποι απαρίθμησης (πολλοί κατασκευαστές χωρίς όρισμα). Οι αλγεβρικοί τύποι είναι ένα είδος σύνθετου τύπου (π.χ. ένας τύπος σχηματισμένος από το συνδυασμό άλλων τύπων).
Ένας αλγεβρικός τύπος μπορεί να είναι επίσης αφηρημένος τύπος δεδομένων (ΑΤΔ) αν οι κατασκευαστές του δεν είναι ορατοί έξω από το module που έχει οριστεί. Οι τιμές ενός τέτοιου τύπου μπορούν να τροποποιηθούν μόνο χρησιμοποιώντας συναρτήσεις ορισμένες στη μονάδα (module) ορισμού του τύπου.
Στη θεωρία συνόλων το ισοδύναμο ενός αλγεβρικού τύπου δεδομένων είναι μια disjoint ένωση – ένα σύνολο τα στοιχεία του οποίου είναι ζεύγη που αποτελούνται από μία ετικέτα (ανάλογη του κατασκευαστή) και ένα αντικείμενο αντίστοιχου με την ετικέτα τύπου (ανάλογα με τα ορίσματα του κατασκευαστή).

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

Για παράδειγμα, στη Haskell μπορούμε να ορίσουμε έναν νέο αλγεβρικό τύπο δεδομένων, Tree:
data Tree = Empty
          | Leaf Int
          | Node Tree Tree
Εδώ, το Empty, το Leaf και το Node καλούνται κατασκευαστές δεδομένων. Το Tree είναι κατασκευαστής τύπου – σε αυτήν την περίπτωση χωρίς παραμέτρους (nullary). Στο υπόλοιπο του άρθρου ο κατασκευαστής θα σημαίνει κατασκευαστής δεδομένων. Παρόμοια, στη σύνταξη της OCaml το ανωτέρω παράδειγμα γράφεται:
type tree = Empty
          | Leaf of int
          | Node of tree * tree
Στην πλειονότητα των γλωσσών που υποστηρίζουν αλγεβρικούς τύπους δεδομένων είναι εφικτός ο ορισμός παραμετρικών τύπων. Παραδείγματα δίνονται στη συνέχεια του άρθρου. Παρόμοια με συνάρτηση, ένας κατασκευαστής δεδομένων εφαρμόζεται σε ορίσματα κατάλληλου τύπου, επιστρέφοντας ένα στιγμιότυπο του τύπου στον οποίο ανήκει ο κατασκευαστής. Για παράδειγμα, ο κατασκευαστής δεδομένων Leaf είναι λογικά μια συνάρτηση Int -> Tree, υπό την έννοια ότι δοσμένου ενός ακεραίου ως όρισμα του Leaf παράγεται μια τιμή τύπου Tree. Καθώς το Node παίρνει δύο ορίσματα τύπου Tree, ο τύπος δεδομένων είναι αναδρομικός.
Οι πράξεις επί των αλγεβρικών τύπων δεδομένων μπορούν να ορισθούν με τη χρήση ταιριάσματος μορφοτύπων για την ανάκτηση των ορισμάτων. Για παράδειγμα, θεωρείστε μιας συνάρτησης εύρεσης του βάθους ενός Tree, όπως δίνεται εδώ σε Haskell:

 depth :: Tree -> Int
 depth Empty = 0
 depth (Leaf n) = 1
 depth (Node l r) = 1 + max (depth l) (depth r)
Επειδή ένα Tree που δίνεται στην depth μπορεί να κατασκευασθεί με χρήση οιουδήποτε κατασκευαστή εκ των Empty, Leaf ή Node, επιβάλλεται ο ορισμός της συνάρτησης για κάθε περίπτωση. Στην περίπτωση του Node, το μορφότυπο εξάγει τα υποδέντρα l και r για περαιτέρω επεξεργασία.
Οι αλγεβρικοί τύποι δεδομένων ταιριάζουν γάντι στην υλοποίηση αφηρημένης σύνταξης. Για παράδειγμα, ο ακόλουθος αλγεβρικός τύπος δεδομένων περιγράφει μια απλή γλώσσα που αναπαριστά αριθμητικές εκφράσεις:
data Expression = Number Int
                | Add Expression Expression
                | Minus Expression
                | Mult Expression Expression
                | Divide Expression Expression
Ένα στοιχείο τέτοιου τύπου θα είχε τη μορφή Mult (Add (Number 4) (Minus (Number 1))) (Number 2).
Μια συνάρτηση αποτίμησης αυτής της γλώσσας είναι απλό να γραφεί. Ωστόσο, πολυπλοκότεροι μετασχηματισμοί γίνονται επίσης εφικτοί. Για παράδειγμα, ένα πέρασμα βελτιστοποίησης σε έναν μεταγλωττιστή μπορεί να γραφεί ως μια συνάρτηση που δέχεται μια αφηρημένη έκφραση ως είσοδο και επιστρέφει την βελτιωμένη μορφή.

Εξήγηση

Ένας τύπος δεδομένων μπορεί να είναι πολλά είδη πραγμάτων. Καθένα από αυτά είναι συσχετισμένο με έναν μοναδικό κατασκευαστή που μπορεί να εκληφθεί ως ένα είδος ετικέτας και αυτό το είδος δεδομένων. Κάθε κατασκευαστής μπορεί να φέρει διαφορετικού είδους δεδομένα. Ένας κατασκευαστής μπορεί να μην φέρει καθόλου δεδομένα (π.χ. ο "Empty" στο ανωτέρο παράδειγμα), μόνο ένα δεδομένο (π.χ. ο “Leaf” έχει μία Int τιμή), ή περισσότερα δεδομένα (π.χ. ο “Node” έχει δύο Tree τιμές).
Σε περίπτωση επεξεργασίας μιας τιμής τύπου, το αποδομούμε χρησιμοποιώντας μια διαδικασία γνωστή ως ταίριασμα προτύπων. Αυτή περιλαμβάνει ταίριασμα των δεδομένων με μία σειρά προτύπων. ΤΟ παράδειγμα της συνάρτησης "depth" παραπάνω ταιριάζει τα ορίσματα με τρία πρότυπα. Κατά την κλήση της, βρίσκει το πρώτο πρότυπο που ταιριάζει με τα ορίσματά της, εκτελεί οποιαδήποτε δέσμευση (binding) μεταβλητών υπάρχουν στο πρότυπο και αποτιμά την αντίστοιχη έκφραση.
Κάθε πρότυπο έχει μορφή ανάλογη της δομής πιθανής τιμής του τύπου δεδομένων. Το πρώτο πρότυπο παραπάνω απλώς ταιριάζει με τιμές του κατασκευαστή Empty. Το δεύτερο πρότυπο ταιριάζει με τιμές του κατασκευαστή Leaf. Τα πρότυποα είναι αναδρομικά, κι έτσι τα δεδομένα που σχετίζονται με αυτό τον κατασκευαστή ταιριάζουν με το πρότυπο "n". Εν τοιαύτη περιπτώσει, ένας πεζός αναγνωριστής αναπαριστά ένα πρότυπο που ταιριάζει σε κάθε τιμή, η οποία είναι στη συνέχεια δεσμευμένη σε μια μεταβλητή με αυτό το όνομα — σε αυτή την περίπτωση, μια μεταβλητή “n” είναι δεσμευμένη στην ακέραια τιμή που περιέχεται στον τύπο δεδομένων — προς χρήση στην υπό αποτίμηση έκφραση.
Η αναδρομή στα πρότυπα αυτού του παραδείγματος είναι τετριμμένη, αλλά ένα πιο περίπλοκο αναδρομικό πρότυπο θα μπορούσε να έχει τη μορφή Node (Node (Leaf 4) x) (Node y (Node Empty z)). Τα αναδρομικά πρότυπα με πολλά επίπεδα βάθους χρησιμοποιούνται για παράδειγμα στην εξισορρόπηση των κόκκινων-μαύρων δέντρων, που περιλαμβάνουν περιπτώσεις που απαιτούν εποπτεία χρωμάτων σε αρκετά επίπεδα βάθους.
Το παραπάνω παράδειγμα είναι λειτουργικά ισοδύναμο του παρακάτω ψευδοκώδικα:

switch on (data.constructor)
  case Empty:
    return 0
  case Leaf:
    let n = data.field1
    return 1
  case Node:
    let l = data.field1
    let r = data.field2
    return 1 + max (depth l) (depth r)
Η σύγκριση αυτού με το ταίριασμα προτύπων αναδεικνύει κάποια εκ των πλεονεκτημάτων των αλγεβρικών τύπων δεδομένων και του ταιριάσματος προτύπων. Πρώτο είναι η ασφάλεια τύπων. Ο ανωτέρω ψευδοκώδικας εξαρτάται από το αν ο προγραμματιστής είναι προσεκτικός και δεν χρησιμοποιεί το πεδίο field2 όταν, για παράδειγμα, ο κατασκευαστής είναι Leaf. Επίσης ο τύπος του field1 διαφέρει για Leaf και Node (για το Leaf είναι Int, ενώ για το Node είναι Tree), επομένως το σύστημα τύπων κωλύεται να αναθέσει έναν στατικό τύπο σε αυτό σε μια κλασσική εγγραφή. Ωστόσο, στο ταίριασμα προτύπων, ο τύπος κάθε τιμής που εξάγεται ελέγχεται με βάση τους τύπους που έχουν δηλωθεί στον αντίστοιχο κατασκευαστή, και ο αριθμός των εξαγώγιμων τιμών είναι γνωστός με βάση των κατασκευαστή, οπότε δεν υπάρχουν τέτοια προβλήματα.
Επιπλέον, στο ταίριασμα προτύπων ο μεταγλωττιστής ελέγχει στατικά τον χειρισμό όλων των περιπτώσεων. Αν κάποια από τις περιπτώσεις της "depth" έλειπε, ο μεταγλωττιστής θα προειδοποιήσει ότι κάποια περίπτωση δεν χειρίζεται. Αυτό μπορεί να δείχνει εύκολο για απλές περιπτώσεις όπως η ανωτέρω, αλλά για πολλά περίπλοκα αναδρομικά πρότυπα η διαχείριση γίνεται δύσκολη για τον μέσο άνθρωπο (ή μεταγλωττιστή, αν έχει να ελέγξει τυχαία εμφωλευμένες if-else δομές). Παρόμοια, ενδεχομένως να υπάρχουν περιπτώσεις με τις οποίες δεν γίνεται ποτέ ταίριασμα (π.χ. καλύπτονται από προηγούμενες περιπτώσεις), και ο μεταγλωττιστής μπορεί τις εντοπίσει και να προειδοποιήσει για αυτές καθώς μπορεί να υποδεικνύουν λογικό σφάλμα
Δεν πρέπει να συγχέονται αυτά τα πρότυπα με τα πρότυπα κανονικών εκφράσεων που χρησιμοποιούνται στο ταίριασμα προτύπων με συμβολοσειρές. Ο σκοπός είναι παρόμοιος — να ελέγχουν αν κάποια δεδομένα υπόκεινται σε συγκεκριμένους περιορισμούς, και αν ναι, να εξάγουν σχετικά τμήματα αυτών προς επεξεργασία — αλλά ο μηχανισμός είναι πολύ διαφορετικός. Αυτού του είδους ταίριασμα προτύπων επί αλγεβρικών τύπων δεδομένων ελέγχει τις δομικές ιδιότητες ενός αντικειμένου μάλλον παρά την ακολουθία χαρακτήρων των συμβολοσειρών.