Zipper

Οδηγίες

Δημιουργία ενός zipper για ένα δυαδικό δέντρο.

Τα Zippers είναι ένας καθαρά συναρτησιακός τρόπος να πλοηγείσαι μέσα σε μια δομή δεδομένων και να τη χειρίζεσαι. Περιέχουν ουσιαστικά μια δομή δεδομένων και έναν δείκτη μέσα σε αυτή τη δομή δεδομένων (που ονομάζεται εστίαση).

Για παράδειγμα, δεδομένου ενός rose tree (όπου κάθε κόμβος περιέχει μια τιμή και μια λίστα με παιδικούς κόμβους), ένα zipper μπορεί να υποστηρίζει τις εξής λειτουργίες:

• from_tree (παίρνει ένα zipper από ένα rose tree, η εστίαση είναι στον κόμβο ρίζας)
• to_tree (παίρνει το rose tree από το zipper)
• value (παίρνει την τιμή του κόμβου εστίασης)
• prev (μετακινεί την εστίαση στο προηγούμενο παιδί του ίδιου γονέα, επιστρέφει ένα νέο zipper)
• next (μετακινεί την εστίαση στο επόμενο παιδί του ίδιου γονέα, επιστρέφει ένα νέο zipper)
• up (μετακινεί την εστίαση στον γονέα, επιστρέφει ένα νέο zipper)
• set_value (ορίζει την τιμή του κόμβου εστίασης, επιστρέφει ένα νέο zipper)
• insert_before (εισάγει ένα νέο υποδέντρο πριν από τον κόμβο εστίασης, αυτό γίνεται το prev του κόμβου εστίασης, επιστρέφει ένα νέο zipper)
• insert_after (εισάγει ένα νέο υποδέντρο μετά από τον κόμβο εστίασης, αυτό γίνεται το next του κόμβου εστίασης, επιστρέφει ένα νέο zipper)
• delete (αφαιρεί τον κόμβο εστίασης και όλα τα υποδέντρα, η εστίαση μετακινείται στον κόμβο next αν είναι δυνατόν, αλλιώς στον κόμβο prev αν είναι δυνατόν, αλλιώς στον γονικό κόμβο, επιστρέφει ένα νέο zipper)

Υπάρχουν πολλοί τρόποι για να ολοκληρώσεις αυτή την άσκηση, αλλά την έχουμε προσαρμόσει για όσους θα ήθελαν να εξασκηθούν γράφοντας τους δικούς τους [ability handlers][ability-handler-docs].

Γράψε μια ability Zipper που σου επιτρέπει να περιηγηθείς σε μια δομή δεδομένων δυαδικού δέντρου.

Η ίδια η ability Zipper είναι ορισμένη για εσένα, αλλά θα χρειαστεί να υλοποιήσεις τον handler που της επιτρέπει να περιηγείται στη δομή δεδομένων δυαδικού δέντρου που έχουμε καθορίσει.

Δεδομένου του παρακάτω δυαδικού δέντρου, αν καλούσαμε τις Zipper.right, Zipper.right, Zipper.up και μετά την Zipper.left, θα έπρεπε να βρισκόμαστε στον κόμβο με τιμή 5.

     1
   /   \
  2     4
 /     /  \
3     5    7

Για τους σκοπούς αυτής της άσκησης, αν καλέσεις left ή right σε ένα δυαδικό δέντρο που δεν περιέχει αριστερό ή δεξί κλάδο, μπορείς να επιστρέψεις την τιμή του κόμβου στον οποίο βρίσκεσαι.

Πράγματα για σκέψη

Με ποιον τρόπο μοιάζει ο ίδιος ο ability handler με ένα φερμουάρ; Θα μπορούσες να θεωρήσεις το continuation μιας συνάρτησης ως δείκτη στον επόμενο "κόμβο" του προγράμματός σου; Θα μπορούσες να αποθηκεύσεις παλιές κλήσεις του continuation στον handler σου, ώστε να περιηγηθείς "πίσω" σε μια προηγούμενη κατάσταση;

Ποιες άλλες δομές δεδομένων θα μπορούσες να διατρέξεις με αυτόν τον τρόπο; Θα μπορούσες να γράψεις ένα Zipper πάνω σε JSON ή ένα πάνω στο δέντρο DOM της HTML;