Μιλούσα προχθές για τη χρήση του τελεστή ελαχιστοποίησης (βήτα τάξης) ως τυπικού αντιπαραδείγματος για τη σφαλερή διαίσθηση οτι «άν ένα συναρτησιακό είναι μέγιστο, θά 'πρεπε νά 'ναι και ολικό». Στο μεταξύ έπεσα πάνω σε μιά ερώτηση στο στάκ εξτσέιντζ της πληροφορικής, σχετικά με την αποτελεσματικότητα του ενλόγω τελεστή (ή, για ν' ακριβολογούμε, μίας εκδοχής του: για κάθε κατηγόρημα στους φυσικούς παίρνουμε και έναν ανάλογο τελεστή ελαχιστοποίησης).
Η ερώτηση στο στάκ εξτσέιντζ τίθεται στα πλαίσια του κλασικού φορμαλισμού σχετικά με την αποτελεσματικότητα (τον πιάσαμε αυτόν τον φορμαλισμό και εδώ, όταν μιλούσαμε για έν' απ' τα πέιπερ του Μπέργκερ), οπου χρειάζεσαι μία αρίθμηση των ισόπεδων φυσικών που νά 'χει κάποιες συγκεκριμένες ιδιότητες, και λές έναν τελεστή απ' το \(\mathbb{N}\) στο \(\mathbb{N}\) αποτελεσματικό όταν συνοδεύεται απο μία αναδρομική συνάρτηση (εννοούμενη πάνω στους δείκτες της αρίθμησης), έτσι ωστε να καθιστά ένα συγκεκριμένο διάγραμμα (τελεστή, αναδρομικής συνάρτησης και αρίθμησης) μεταθετικό --για λεπτομέρειες, δές εδώ. Όλ' αυτά καλά και ζόρικα, αλλα κάπου εκεί έρχεται πάλι ο Μπάουερ και απαντά στην ερώτηση με το γνωστό του τρόπο: «η υπολογισιμότητα αφορά τον υπολογισμό· έ, γιατί δε χρησιμοποιείς υπολογιστή;».
Στην απάντησή του υπενθυμίζει βασικά στοιχεία της μοντέρνας κατανόησης για τη θεωρία υπολογισιμότητας, και, συγκεκριμένα για το θέμα, οτι αποτελεσματικός τελεστής σημαίνει στην πράξη «τελεστής που συνοδεύεται απο ένα πρόγραμμα σε κάποια γλώσσα προγραμματισμού, το οποίο μετατρέπει τον (πηγαίο) κώδικα της εισόδου σε κώδικα της εξόδου». Συνεχίζει λοιπόν παρουσιάζοντας ώς απάντηση στην ερώτηση, απλά, ένα τέτοιο πρόγραμμα. Απλά και όμορφα πράματα.
Το πρόγραμμά του πάντως, στο κομμάτι που αφορά τον κώδικα εξόδου, χρησιμοποιεί εντολές ελέγχου, όπως if και while, οπότε σκέφτηκα πώς θα έμοιαζε ένας τέτοιος κώδικας σε αμιγή συναρτησιακή γλώσσα. Δέν ασχολήθηκα πολύ, αλλα νά μια απάντηση σε χάσκελ.
Ορίζουμε πρώτα ένα βοηθητικό συναρτησιακό που παίρνει μία αριθμητική συνάρτηση και επιστρέφει τη λίστα των τιμών της:
Εδώ, η λίστα iterate (+1) 0 αντιπροσωπεύει απλά τους φυσικούς αριθμούς. Κατόπιν ορίζουμε τον τελεστή ελαχιστοποίησης χρησιμοποιώντας την ήδη ορισμένη στη γλώσσα συνάρτηση findIndex, που παίρνει ένα κατηγόρημα και μία λίστα, και επιστρέφει τη θέση του πρώτου μέλους της λίστας που ικανοποιεί το κατηγόρημα.
Για παράδειγμα, με είσοδο τη συνάρτηση\[f(x) := \begin{cases}0&,\ x<52,\\x-51&,\ x\geq 52,\end{cases}\]το πρόγραμμά μας επιστρέφει
Υπόψιν οτι η χρήση της Maybe, που υπαγορεύεται απ' τον τύπο της findIndex, δέν αποτρέπει φυσικά το κρασάρισμα αν δώσουμε είσοδο τη σταθερή μηδενική συνάρτηση \(\lambda_x.0\). Δοκιμάστε το, για τη φάση:
Προσοχή: τα παραπάνω δέν είναι απάντηση στην ερώτηση του στάκ εξτσέιντζ! Απλά, μία υλοποίηση του τελεστή ελαχιστοποίησης στη χάσκελ. Αμα τη ευρέσει χρόνου (ίσον διάθεσης), μπορεί και να το ξαναπιάσουμε το θέμα.
Η ερώτηση στο στάκ εξτσέιντζ τίθεται στα πλαίσια του κλασικού φορμαλισμού σχετικά με την αποτελεσματικότητα (τον πιάσαμε αυτόν τον φορμαλισμό και εδώ, όταν μιλούσαμε για έν' απ' τα πέιπερ του Μπέργκερ), οπου χρειάζεσαι μία αρίθμηση των ισόπεδων φυσικών που νά 'χει κάποιες συγκεκριμένες ιδιότητες, και λές έναν τελεστή απ' το \(\mathbb{N}\) στο \(\mathbb{N}\) αποτελεσματικό όταν συνοδεύεται απο μία αναδρομική συνάρτηση (εννοούμενη πάνω στους δείκτες της αρίθμησης), έτσι ωστε να καθιστά ένα συγκεκριμένο διάγραμμα (τελεστή, αναδρομικής συνάρτησης και αρίθμησης) μεταθετικό --για λεπτομέρειες, δές εδώ. Όλ' αυτά καλά και ζόρικα, αλλα κάπου εκεί έρχεται πάλι ο Μπάουερ και απαντά στην ερώτηση με το γνωστό του τρόπο: «η υπολογισιμότητα αφορά τον υπολογισμό· έ, γιατί δε χρησιμοποιείς υπολογιστή;».
Στην απάντησή του υπενθυμίζει βασικά στοιχεία της μοντέρνας κατανόησης για τη θεωρία υπολογισιμότητας, και, συγκεκριμένα για το θέμα, οτι αποτελεσματικός τελεστής σημαίνει στην πράξη «τελεστής που συνοδεύεται απο ένα πρόγραμμα σε κάποια γλώσσα προγραμματισμού, το οποίο μετατρέπει τον (πηγαίο) κώδικα της εισόδου σε κώδικα της εξόδου». Συνεχίζει λοιπόν παρουσιάζοντας ώς απάντηση στην ερώτηση, απλά, ένα τέτοιο πρόγραμμα. Απλά και όμορφα πράματα.
Το πρόγραμμά του πάντως, στο κομμάτι που αφορά τον κώδικα εξόδου, χρησιμοποιεί εντολές ελέγχου, όπως if και while, οπότε σκέφτηκα πώς θα έμοιαζε ένας τέτοιος κώδικας σε αμιγή συναρτησιακή γλώσσα. Δέν ασχολήθηκα πολύ, αλλα νά μια απάντηση σε χάσκελ.
Ορίζουμε πρώτα ένα βοηθητικό συναρτησιακό που παίρνει μία αριθμητική συνάρτηση και επιστρέφει τη λίστα των τιμών της:
range :: (Int -> Int) -> [Int]
range f = map f (iterate (+1) 0)Εδώ, η λίστα iterate (+1) 0 αντιπροσωπεύει απλά τους φυσικούς αριθμούς. Κατόπιν ορίζουμε τον τελεστή ελαχιστοποίησης χρησιμοποιώντας την ήδη ορισμένη στη γλώσσα συνάρτηση findIndex, που παίρνει ένα κατηγόρημα και μία λίστα, και επιστρέφει τη θέση του πρώτου μέλους της λίστας που ικανοποιεί το κατηγόρημα.
minOperator :: (Int -> Int) -> Maybe IntminOperator f = findIndex (>0) (range f)Για παράδειγμα, με είσοδο τη συνάρτηση\[f(x) := \begin{cases}0&,\ x<52,\\x-51&,\ x\geq 52,\end{cases}\]το πρόγραμμά μας επιστρέφει
> minOperator (\x->if x<52 then 0 else x-51)Just 52Υπόψιν οτι η χρήση της Maybe, που υπαγορεύεται απ' τον τύπο της findIndex, δέν αποτρέπει φυσικά το κρασάρισμα αν δώσουμε είσοδο τη σταθερή μηδενική συνάρτηση \(\lambda_x.0\). Δοκιμάστε το, για τη φάση:
> minOperator (\x->0)<interactive>: out of memory (requested 1048576 bytes)Προσοχή: τα παραπάνω δέν είναι απάντηση στην ερώτηση του στάκ εξτσέιντζ! Απλά, μία υλοποίηση του τελεστή ελαχιστοποίησης στη χάσκελ. Αμα τη ευρέσει χρόνου (ίσον διάθεσης), μπορεί και να το ξαναπιάσουμε το θέμα.
