Θυμάστε πώς είχαμε υλοποιήσει τους πύργους του Ανόι σε C στη σχολή όταν πρωτοπήγαμε; Ορίστε πόσο απλή είναι η έκδοση του σε συναρτησιακό προγραμματισμό (με χρήση της F#).
Κατ’αρχάς μερικές νύξεις στο VS Studio 2010 που έχει ενσωματωμένα templates και debugging tools για αυτή τη νέα γλώσσα. Ανοίγουμε το VS Studio 2010 Beta 2 που μπορούμε να το κατεβάσουμε δωρεάν όσο διαρκεί η φάση Beta και διαλέγουμε να δημιουργήσουμε ένα Console Application σε F#.
Στην συνέχεια κάνουμε paste τον παρακάτω κώδικα (προσέξτε το indentation στον κώδικα καθώς έχει σημασία να είναι σωστά στοιχειοθετημένες οι εντολές. Δεν γίνεται compile αν δεν ακολουθηθούν οι αντίστοιχοι απλοί κανόνες) που ορίζει δύο συναρτήσεις, την move (μετακίνησε από στύλο σε στύλο, στην ουσία απλά κάνει print την κίνηση για να βλέπουμε την αλλαγή της κατάστασης) και την hanoi η οποία υλοποιεί την αναδρομική συνάρτηση. Όποτε δοκιμάζω να μάθω την F#, μου αρέσει να στέλνω ότι γράφω στο interactive environment της. Ότι γράφεται σε αυτό το παράθυρο μοιάζει να περνάει από interpreter, αλλά στην ουσία γίνεται δυναμικά compile on-the-fly βλέποντας την αποτίμηση κάποιας έκφρασης, εκείνη τη στιγμή στο παράθυρο.
let move = printfn "Μετακίνησε δίσκο από %c στο %c"
let rec hanoi f x t = function
| 1 -> move f t
| n -> hanoi f t x (n - 1)
move f t
hanoi x f t (n - 1)
Το παραπάνω κομμάτι κώδικα ορίζει μία απλή συνάρτηση και μία αναδρομική.
Μόλις γίνει η μεταφορά του κώδικα στο interactive παράθυρο, μας παρουσιάζονται δύο γραμμές:
val move : (char -> char -> unit)
//Η δήλωση της move που παίρνει δύο παραμέτρους τύπου char
//Η παραπάνω δήλωση ερμηνεύεται ως εξής λόγω του currying: το move είναι μία συνάρτηση που παίρνει ένα argument και επιστρέφει μία συνάρτηση με τύπο (char->unit).
val hanoi : char -> char -> char -> int –> unit
//Η δήλωση της hanoi που παίρνει τρεις χαρακτήρες και ένας ακέραιο.
//Ομοιοτρόπως και σε αυτή τη δήλωση. To int σε αυτή τη περίπτωση είναι μία επίδραση του keyword function, το οποίο λόγω της ιδιότητάς του δημιουργεί μία έμμεση μεταβλητή.
Η δήλωση unit σημαίνει ότι δεν επιστρέφεται τίποτα από αυτή τη συνάρτηση. Το unit αποτελεί έναν primitive type που δεν περιέχει καμία απολύτως πληροφορία και η μόνη του τιμή είναι το ().
Πάμε στην αναδρομική συνάρτηση. Ξεκινάμε με το keyword let, με το οποίο δηλώνουμε πως ότι θα γράψουμε, θα δεθεί με το όνομα hanoi, γίνεται δηλαδή binding του ονόματος με την έκφραση της συνάρτησης. Στη συνέχεια, με το keyword rec αναφέρουμε πως το binding αυτό μπορεί να αναφερθεί στον εαυτό του ή πιο απλά, ότι έχουμε μία αναδρομική συνάρτηση. Ορίζονται το όνομα και οι μεταβλητές μας (χωρίς να ορίζουμε τύπο-γίνεται infer από την F#). Με την λέξη κλειδί function ανακοινώνουμε ότι έχουμε μία συνάρτηση η οποία μπορεί να αναγνωρίσει πρότυπα πάνω στα ορίσματά της (pattern matching), έτσι η F# καταλαβαίνει ότι στα ορίσματα υπεισέρχεται ακόμα ένας τύπος ακεραίου (o ακέραιος εκείνος που μας έδειξε το interactive window παραπάνω). Τι είναι pattern matching εν συντομία; Pattern matching είναι η δυνατότητα που προσφέρει η δομή function… και η δομή match…with… να εκτιμά το αποτέλεσμα μίας έκφρασης και να συγκρίνει αυτό το αποτέλεσμα με μία σειρά από κανόνες. Στην περίπτωσή μας, οι κανόνες πηγάζουν από την αναδρομική λύση του προβλήματος. Αν παρατηρήσουμε τη μαθηματική λύση και το παραπάνω κώδικα, θα δούμε ότι οι παραπάνω εκφράσεις είναι η μετάφραση της μαθηματικής λύσης αυτούσια από το συλλογισμό μας, στην F#. Παρατηρήστε την αναδρομική λύση του προβλήματος. Έχει τρία βήματα που λένε:
- - Μετέφερε n-1 δίσκους από τον πρώτο στύλο στο δεύτερο (οπότε απομένει ο δίσκος με τον αριθμό n – ο μεγαλύτερος στον πρώτο στύλο)
- Μετέφερε τον δίσκο n από τον πρώτο στύλο στον τρίτο
- Μετέφερε n-1 δίσκους από τον δεύτερο στύλο στον τρίτο. - - Τι γίνεται όταν έχουμε τον δίσκο υπ’ αριθμόν 1 (τον μικρότερο δηλαδή); Μετέφερέ τον στον τρίτο στύλο!
Ακριβώς δηλαδή ότι είναι γραμμένο στο παραπάνω κομμάτι κώδικα!
Εκτελώντας τον κώδικα για διαφoρετικούς ακεραίους, μία για 2 δίσκους και μία για 4 δίσκους, βλέπουμε τη λύση στο interactive window.
Cheers!
