A verifier of the Collatz conjecture in F#, annotated with Greek comments.

collatz.fs

// Η εικασία του Collatz στην F#, με επεξηγήσεις.
// Θοδωρής Τσιρπάνης, 3/10/2017. Άδεια χρήσης: CC0

// Αυτό το πρόγραμμα έπαληθεύει την εικασία του Collatz. https://en.wikipedia.org/wiki/Collatz_conjecture
// Είναι γραμμένο στην F# και έχει εκτεταμένους σχολιασμούς με σκοπό την εισαγωγή στις δυνατότητες της γλώσσας.
// Μία βασική εξοικείωση με τον προγραμματισμό και με τα μαθηματικά απαιτείται για την πλήρη κατανόηση του προγράμματος.

// Στο System βρίσκονται οι πιο βασικές μέθοδοι του συστήματος.
// Αν και εδώ χρησιμοποιούμε μόνο το Console.ReadLine και το UInt64.TryParse.
// Η πρότυπη βιβλιοθήκη της F# είναι στο namespace "Microsoft.FSharp" το οποίο ανοίγει αυτόματα.
open System
// Ανοίγοντας αυτό το namespace, οι αριθμητικές πράξεις "κρασάρουν" αν κάνουν overflow.
open Operators.Checked

// Τα προγράμματα στην F# αποτελούνται από συναρτήσεις.
// Αυτές τις συναρτήσεις μπορείς είτε να τις δώσεις τους μία τιμή και να πάρεις μια άλλη τιμή, είτε να τις περάσεις ως παραμέτρους σε μία άλλη συνάρτηση.
// Για την F#, δεν υπάρχουν διακρίσεις μεταξύ συναρτήσεων και τιμών. Αυτό είναι το μεγάλο της πλεονέκτημα έναντι των "παραδοσιακών" γλωσσών.
// Όπως στα μαθηματικά, η συνάρτηση δέχεται κάποια είσοδο και επιστρέφει κάποια έξοδο, η οποία εξαρτάται από την είσοδο.
// Αυτή η συνάρτηση υπολογίζει ένα βήμα της συνάρτησης του Collatz.
let collatz x =
    match x with // Το match είναι σαν to switch που έχει η Java, αλλά μολύ πιο ισχυρό.
    // Με μια γραμμή ελέγχουμε αν ο αριθμός είναι ζυγός και λέμε τι θα επιστρέψει η συνάρτηση τότε.
    // Παρατήρησε πως δεν υπάρχουν "return", σε αντίθεση με την Python.
    // Επίσης δεν χρειάζονται ερωτηματικά και αγκύλες. Όπως η Python. 😊
    // Οι αριθμοί που τελειώνουν σε UL είναι ακέραιοι μεγέθους 64 bit χωρίς πρόσημο, δηλαδή από το 0 έως το 9.223.372.036.854.775.807.
    // Η F# επιτρέπει πράξεις μόνο μεταξύ αριθμών του ίδιου τύπου.
    // Για να υποστηρήξει μεγαλύτερους αριθμούς το πρόγραμμα, θα χρειαστεί περισσότερη δουλειά και βαριέμαι. 😎
    | x when x % 2UL = 0UL -> x / 2UL
    // Αν η συνθήκη δεν ικανοποιείται, υπολογίζεται αυτή η περίπτωση.
    // Μπορείς να βάλεις πολλές συνθήκες και θα εξεταστούν με την σειρά που τις δήλωσες.
    // Αν δεν ικανοποιούνται όλες οι περιπτώσεις (η αν δεν υπάρχει στο τέλος μια γενική περίπτωση), ο compiler εμφαίζει μία προειδοποίηση.
    | x -> 3UL * x + 1UL
    // Βλέπεις πως η συνάρτηση μοιάζει πολύ με το πώς ορίζεται στην πραγματικότητα (https://adilakhter.files.wordpress.com/2013/02/image1.png). 😛

// Άλλη μια συνάρτηση, αλλά λίγο διαφορετική.
// Όπως και πριν, αυτή η συνάρτηση δέχεται μία τιμή τύπου "uint64".
// Αλλά δημιουργεί μια λίστα με τα βήματα της συνάρτησης του Collatz από τον αριθμό που της δώσαμε, μέχρι να φτάσει στο ένα.
// Η λίστα είναι μία δομή δεδομένων που διαβάζονται με την σειρά (σε αντίθεση με τα arrays που έχουν οι άλλες γλώσσες και διαβάζονται τυχαία).
// Το rec βγαίνει από το recursive και σημαίνει ότι η συνάρτηση είναι αναδρομική, δηλαδή μπορεί να καλέσει τον εαυτό της.
// Γλώσσες όπως η F# δεν έχουν while loops, αλλά έχουν την αναδρομή.
// Επειδή είναι τόσο σύνηθης, ο compiler φροντίζει να την βελτιστοποιεί κατάλληλα στις πιο πολλές περιπτώσεις, όπου η απόδοσή της είναι συγκρίσιμη με το while loop.
let rec makeCollatzList =
    function // Αντί να πω "let something x = match x with | 0 -> ...", μπορώ να πω "let something = function | x -> ..."
    | 0UL -> [] // Το μηδέν δεν είναι έγκυρη είσοδος, οπότε επιστρέφει μία κενή λίστα.
    | 1UL -> [1UL] // Αν η συνάρτηση του Collatz φτάσει στο ένα, τότε έχει τελειώσει. Επομένως επιστρέφεται μία λίστα με μόνο στοιχείο το ένα.
    | x -> x :: (x |> collatz |> makeCollatzList) // Αν η είσοδος είναι ένας άλλος αριθμός (θυμίσου, δεν υπάρχουν αρνητικοί αριθμοί για αυτήν την συνάρτηση)...
    // Η συνάρτηση επιστρέφει μία λίστα με πρώτο στοιχείο την τιμή που της δώσαμε, και για τα υπόλοιπα στοιχεία της, υπολογίζει την λίστα με τα βήματα της συνάρτησης του Collatz από τον αριθμό που δώσαμε, αν του εφαρμώσουμε την συνάρτηση του Collatz!
    // Κάποτε η συνάρτηση του Collatz θα φτάσει το ένα και τότε οι συναρτήσεις θα σταματήσουν να επιστρέφουν το αποτέλεσμα του εαυτού τους. Και θα δημιουργηθεί μία μία λίστα από όλους τους αριθμούς που διένυσε, μέχρι να φτάσει στο ένα.
    // Αν δεν φτάσει ποτέ, είτε η εικασία του Collatz έχει καταρριφθεί, είτε υπάρχει κάποιο πρόβλημα με το πρόγραμμα.
    // Το σύμβολο "|>" βοηθάει στις εξής περιπτώσεις. Αντί να πούμε "f (g (x))", μπορούμε να πούμε "x |> g |> f". Χωρίς παρενθέσεις και δείχνει την "ροή" των δεδομένων, καθώς "περνούν" μέσα από τις συναρτήσεις.

// Τέλος οι συναρτήσεις, τώρα ο πραγματικός κώδικας.

printf "Write a number to test: " // To printf κάνει αυτό που νομίζεις ότι κάνει. Το printfn επί τη ευκαιρία, αλλάζει την γραμμή στην κονσόλα μετά το μήνυμα.

// Ορίζουμε τώρα μία τιμή. ΔΕΝ ορίσαμε μεταβλητή, καθώς οι τιμές στις γλώσσες σαν την F# δεν αλλάζουν.
// Δεν είναι τυχαίο που χρησιμοποιούμε την ίδια λέξη-κλειδί για να ορίσουμε μία συνάρτηση και μια τιμή. Οι συναρτήσεις είναι κι' αυτές τιμές με ίσα διακιώματα 😮.
let input = Console.ReadLine() // Εδώ θα χρησιμοποιήσουμε μια μέθοδο της C# για να διαβάσουμε από την κονσόλα μια γραμμή. Η F# δεν έχει "scanf" ή κάτι παρόμοιο.
// Το input όμως είναι κείμενο, όχι αριθμός. Θα πάρουμε την μέθοδο UInt64.TryParse για να το μετατρέψουμε.
// Όμως κάποιος μπορεί να γράψει κάτι που δεν είναι αριθμός. Με το UInt64.Parse, το πρόγραμμα θα κράσαρε. Όμως μπορούμε να το κάνουμε να σταματήσει λιγότερο βίαια.
// Ο τύπος του TryParse είναι ο εξής: "string -> bool * uint64". Δέχεται ένα string και επιστρέφει μία λογική τιμή (αν πέτυχε η μετατροπή ή όχι) και το αποτέλεσμα.
match UInt64.TryParse input with
// Όπως ανέφερα προηγουμένως, το match είναι πολύ ισχυρό. Μπορούμε να κάνουμε match σε πάνω από μία τιμές ταυτόχρονα.
// Μπορούμε να εξετάσουμε αν κάποια από τις τιμές αυτές είναι ίση με μία σταθερά, και αν ναι, να κάνουμε κάτι με τις άλλες τιμές.
| true, x -> // Εδώ εξετάζουμε αν η πρώτη τιμή είναι true (δηλαδή αν πέτυχε η μετατροπή), και δίνουμε στην δεύτερη τιμή (τον αριθμό) το όνομα x.
    let result = makeCollatzList x // Υπολογίζουμε τα βήματα.
    let stepCount = List.length result // Η συνάρτηση List.Length μάντεψε τι υπολογίζει... 😛
    let steps = // Ας κάνουμε ένα string με τα βήματα χωρισμένα με κόμμα.
        result
        |> List.map string
        // Η συνάρτηση List.map παίρνει μία λίστα και εφαρμόζει μία συνάρτηση σε κάθε στοιχείο της λίστας και επιστρέφει μία λίστα με τα καινούργια στοιχεία (θυμήσου, οι τιμές δεν αλλάζουν).
        // Η συνάρτηση string μετατρέπει (σχεδόν) οτιδήποτε σε string.
        |> String.concat ", " // Η συνάρτηση String.concat παίρνει μία λίστα με string και επιστρέφει ένα νέο string με τα στοιχεία αυτά και ένα άλλο string ανάμεσά τους.
    // Εδώ τώρα υπάρχουν πολλά ενδιαφέροντα σημεία. Κατ' αρχήν στην F# μπορεί κάποιος να κλείσει μέσα σε τριπλά εισαγωγικά ένα string που αποτελείται από πολλές γραμμές χωρίς να καταφεύγει σε ειδικούς χαρακτήρες όπως το "\n".
    printfn """Number %d reaches 1 after %d steps.
Detailed steps: %s""" x stepCount steps
    // Ο τύπος της συνάρτησης printfn είναι περίπλοκος. Εξαρτάται από το string που θα της δώσεις. Για παράδειγμα, για κάθε %s, η συνάρτηση θα ζητάει ένα string, για κάθε %d, έναν ακέραιο αριθμό, για κάθε %f, έναν δεκαδικό σριθμό και άλλα.
| false, _ -> printfn "Sorry, can't recognize that number. :-(" // Αν η πρώτη τιμή είναι false (η δεύτερη δεν μας ενδιαφέρει και δεν πήρε όνομα), μπορούμε να εμφανίσουμε ένα μήνυμα φιλικό στον χρήστη.

// Κι' εδώ τελειώνει το πρόγραμμα.
// Παρατήρησε ότι είναι μόνο 24 γραμμές κώδικα. Αυτό σημαίνει: ευκολότερο στην κατανόηση, με περισσότερη εκφραστικότητα και με λιγότερα bugs. Το έχω τρέξει μόνο τρεις φορές, αλλά είμαι αισιόδοξος ότι θα δουλέψει. Δεν το έχω κάνει debug· δεν πιστεύω πως χρειάζεται. Φαντάσου ένα μεγαλύτερο πρόγραμμα πόσο θα μίκρυνε!
// Αυτό το πρόγραμμα είναι ένας τρόπος για να εξηγηθούν κάποια στοιχεία της γλώσσας χωρίς να έχει σκοπό να την διδάξει σε κάποιον. Ένα πολύ καλό tutorial υπάρχει στο https://fsharpforfunandprofit.com/.