Εισαγωγή
Δουλεύεις σε ένα έργο για την ανάπτυξη ενός συστήματος προγραμματισμού δρομολογίων για ένα πολυσύχναστο σιδηροδρομικό δίκτυο.
Σου ζητήθηκε να αναπτύξεις ένα πρωτότυπο για τα δρομολόγια των τρένων στο σύστημα προγραμματισμού. Κάθε δρομολόγιο αποτελείται από μια ακολουθία σιδηροδρομικών σταθμών στους οποίους σταματάει ένα δεδομένο τρένο.
Οδηγίες
Η ομάδα σου έχει αποφασίσει να χρησιμοποιήσει μια διπλά συνδεδεμένη λίστα για να αναπαραστήσει κάθε διαδρομή τρένου στο πρόγραμμα δρομολογίων.
Κάθε σταθμός κατά μήκος της διαδρομής του τρένου θα αναπαρίσταται από έναν κόμβο στη συνδεδεμένη λίστα.
Δεν χρειάζεται να ανησυχείς για τις ώρες άφιξης και αναχώρησης στους σταθμούς.
Κάθε σταθμός θα αναπαρίσταται απλώς από έναν αριθμό.
Οι διαδρομές μπορούν να επεκταθούν, προσθέτοντας σταθμούς στην αρχή ή στο τέλος μιας διαδρομής.
Μπορούν επίσης να συντομευτούν, αφαιρώντας σταθμούς από την αρχή ή το τέλος μιας διαδρομής.
Μερικές φορές ένας σταθμός κλείνει, και σε αυτή την περίπτωση ο σταθμός πρέπει να αφαιρεθεί από τη διαδρομή, ακόμα κι αν δεν βρίσκεται στην αρχή ή στο τέλος της διαδρομής.
Το μέγεθος μιας διαδρομής δεν μετριέται από το πόσο μακριά ταξιδεύει το τρένο, αλλά από το σε πόσους σταθμούς σταματάει.
Η συνδεδεμένη λίστα είναι μια θεμελιώδης δομή δεδομένων στην επιστήμη των υπολογιστών, που χρησιμοποιείται συχνά στην υλοποίηση άλλων δομών δεδομένων.
Όπως υποδηλώνει το όνομά της, είναι μια λίστα με κόμβους που συνδέονται μεταξύ τους.
Είναι μια λίστα με "κόμβους", όπου κάθε κόμβος συνδέεται με τον γείτονά του ή τους γείτονές του.
Σε μια απλά συνδεδεμένη λίστα κάθε κόμβος συνδέεται μόνο με τον κόμβο που τον ακολουθεί.
Σε μια διπλά συνδεδεμένη λίστα κάθε κόμβος συνδέεται τόσο με τον κόμβο που προηγείται όσο και με τον κόμβο που ακολουθεί.
Αν θέλεις να εμβαθύνεις στις συνδεδεμένες λίστες, ρίξε μια ματιά σε αυτό το άρθρο που τις εξηγεί με ωραία σχέδια.
Δομές δεδομένων με κατάσταση
Στις συναρτησιακές γλώσσες, όπως η Lean, οι περισσότερες τιμές είναι αμετάβλητες εκ σχεδιασμού.
Αυτό σημαίνει ότι οι ενημερώσεις γίνονται συνήθως παράγοντας μια νέα τιμή.
Η παλιά και η νέα τιμή συνυπάρχουν και μπορούν να αναφερθούν και να χρησιμοποιηθούν και οι δύο.
Ωστόσο, υπάρχουν πολλές περιπτώσεις όπου μια τιμή με κατάσταση είναι επιθυμητή, ή ακόμη και απαραίτητη.
Μια τιμή με κατάσταση ενημερώνεται με μετάλλαξη, αντικαθιστώντας την παλιά τιμή αντί να δημιουργεί μια νέα.
Μετά από μια μετάλλαξη, μόνο η ενημερωμένη τιμή παραμένει προσβάσιμη.
Σημείωσε ότι οι μεταλλάξεις μπορούν να σπάσουν κάποιες εγγυήσεις της γλώσσας.
Μια καθαρή συνάρτηση πρέπει πάντα να επιστρέφει το ίδιο αποτέλεσμα για το ίδιο σύνολο εισόδων, αλλά αν μια είσοδος μπορεί να αλλάξει με τον χρόνο, τότε η συνάρτηση μπορεί να επιστρέψει διαφορετικά αποτελέσματα ακόμη και όταν καλείται με τα ίδια ορίσματα.
Παρομοίως, αν μια συνάρτηση μπορεί να παράγει εξωτερικές αλλαγές πέρα από την επιστροφή ενός αποτελέσματος, ή μπορεί να διαβάσει από πηγές εκτός από τις παραμέτρους της, τότε δύο κλήσεις στην ίδια συνάρτηση μπορεί να έχουν διαφορετικά και μερικές φορές απρόβλεπτα αποτελέσματα.
Για να χειριστείς τέτοια συμπεριφορά με κατάσταση, η Lean, όπως και άλλες συναρτησιακές γλώσσες, απαιτεί οι συναρτήσεις με παρενέργειες να είναι τυλιγμένες σε ένα ειδικό είδος δομής που τις ξεχωρίζει από τις καθαρές συναρτήσεις.
Αυτές οι δομές ονομάζονται μονάδες.
Είναι σημαντικό να σημειωθεί ότι, αν και κάθε τιμή με κατάσταση ζει μέσα σε κάποια μονάδα με παρενέργειες, δεν αντιπροσωπεύει κάθε μονάδα μεταβλητή κατάσταση.
Αξιοσημείωτα παραδείγματα "καθαρών" μονάδων είναι τα Option, Except και Id.
Σε αυτή την άσκηση, θα ορίσεις μια δομή δεδομένων με κατάσταση που ονομάζεται LinkedList.
Τα στιγμιότυπα αυτής της δομής δεδομένων ενημερώνονται με μετάλλαξη.
Για να υποστηριχθεί αυτό, όλες οι συναρτήσεις είναι τυλιγμένες μέσα στη μονάδα ST.
Σε αυτή τη μονάδα, η μεταβλητή κατάσταση είναι η μόνη παρενέργεια, και οι μεταβλητές αναφορές δεν μπορούν να διαφύγουν.
Για περισσότερες πληροφορίες, μπορείς να δεις την αναφορά.
Πηγή
Κλασικό θέμα επιστήμης υπολογιστών
