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

Στον προγραμματισμό υπολογιστών και συγκεκριμένα στον συναρτησιακό προγραμματισμό και τη θεωρία τύπων, ο αλγεβρικός τύπος δεδομένων (επίσης γνωστός ως 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 δομές). Παρόμοια, ενδεχομένως να υπάρχουν περιπτώσεις με τις οποίες δεν γίνεται ποτέ ταίριασμα (π.χ. καλύπτονται από προηγούμενες περιπτώσεις), και ο μεταγλωττιστής μπορεί τις εντοπίσει και να προειδοποιήσει για αυτές καθώς μπορεί να υποδεικνύουν λογικό σφάλμα

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

Θεωρία

Ένας γενικός αλγεβρικός τύπος δεδομένων είναι πιθανώς ένας αναδρομικός τύπος αθροίσματος από τύπους γινομένου. Κάθε κατασκευαστής καθορίζει έναν τύπο γινόμενο για να τον διακρίνει από τους άλλους, ή αν υπάρχει μόνο ένας κατασκευαστής ο τύπος δεδομένων είναι τύπος γινομένου. Επιπροσθέτως, οι τύποι παράμετροι ενός κατασκευαστή είναι οι παράγοντες του τύπου γινομένου. Ένας κατασκευαστής χωρίς παραμέτρους αντιστοιχεί στο κενό γινόμενο. Αν ένας τύπος δεδομένων είναι αναδρομικός, ολόκληρο το άθροισμα των γινομένων εμπεριέχεται σε έναν αναδρομικό τύπο, και κάθε κατασκευαστής εσωκλείει τον τύπο δεδομένων στον αναδρομικό τύπο.

Για παράδειγμα, ο τύπος δεδομένων της Haskell:

 data List a = Nil | Cons a (List a)

αναπαρίσταται στην θεωρία τύπων ως $\lambda \alpha .\mu \beta .1+\alpha \times \beta$ με κατασκευαστές $\mathrm {nil} _{\alpha }=\mathrm {roll} \ (\mathrm {inl} \ \langle \rangle )$ και $\mathrm {cons} _{\alpha }\ x\ l=\mathrm {roll} \ (\mathrm {inr} \ \langle x,l\rangle )$.

Ο τύπος List της Haskell μπορεί επίσης να αναπαρασταθεί στην θεωρία τύπων σε μια ελαφρώς διαφορετική μορφή ως ακολούθως: $\mu \phi .\lambda \alpha .1+\alpha \times \phi \ \alpha$. (Επισημαίνεται ότι οι $\mu$ και $\lambda$ κατασκευές είναι αντεστραμμένες σε σχέση με την αρχική.) Η αρχική μορφή καθορίζει μια συνάρτηση τύπων που το σώμα της ήταν αναδρομικός τύπος, ενώ η δεύτερη εκδοχή καθορίζει μια αναδρομική συνάρτηση επί τύπων. (Χρησιμοποιούμε την μεταβλητή τύπου $\phi$ για να υποδηλώσουμε μια συνάρτηση μάλλον παρά έναν "τύπο βάσης" όπως το $\beta$) Επίσης πρέπει επίσης να εφαρμόσουμε την συνάρτηση $\phi$ στο τύπο όρισμα $\alpha$ στο σώμα του τύπου.

Για τους σκοπούς του παραδείγματος με το List, αυτές οι δύο μορφές δεν διαφέρουν σημαντικά, αλλά η δεύτερη μορφή επιτρέπει την έκφραση των επονομαζόμενων εμφωλευμένων τύπων δεδομένων, π.χ., αυτούς όπου ο αναδρομικός τύπος διαφέρει παραμετρικά από τον αρχικό. (Για περισσότερες πληροφορίες για τους εμφωλευμένους τύπους δεδομένων, βλέπε τα έργα των Richard Bird, Lambert Meertens και Ross Paterson.)

Γλώσσες προγραμματισμού με αλγεβρικούς τύπους δεδομένων

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

• Clean
• F#
• Haskell
• haXe
• Hope
• Mercury
• Miranda
• Nemerle
• OCaml
• Opa
• Racket
• Scala
• Standard ML
• Visual Prolog

Βλέπε επίσης

• Tagged union
• Disjoint union
• Θεωρία τύπων
• Generalized algebraic data type
• Initial algebra

Αναφορές

• Algebraic data type in The Free On-line Dictionary of Computing, Editor Denis Howe. (Αγγλικά)