Λειτουργίες λίστας

Οδηγίες

Υλοποίησε βασικές πράξεις σε λίστες.

Στις συναρτησιακές γλώσσες, οι πράξεις σε λίστες όπως οι length, map και reduce είναι πολύ συνηθισμένες. Υλοποίησε μια σειρά από βασικές πράξεις σε λίστες, χωρίς να χρησιμοποιήσεις υπάρχουσες συναρτήσεις.

Ο ακριβής αριθμός και τα ονόματα των πράξεων που θα υλοποιήσεις εξαρτώνται από τη διαδρομή, ώστε να αποφευχθούν συγκρούσεις με υπάρχοντα ονόματα, αλλά οι γενικές πράξεις που θα υλοποιήσεις περιλαμβάνουν:

• append (με δεδομένες δύο λίστες, πρόσθεσε όλα τα στοιχεία της δεύτερης λίστας στο τέλος της πρώτης);
• concatenate (με δεδομένη μια σειρά από λίστες, συνένωσε όλα τα στοιχεία όλων των λιστών σε μία επίπεδη λίστα);
• filter (με δεδομένο ένα κατηγόρημα και μια λίστα, επίστρεψε τη λίστα με όλα τα στοιχεία για τα οποία το predicate(item) είναι αληθές);
• length (με δεδομένη μια λίστα, επίστρεψε τον συνολικό αριθμό των στοιχείων της);
• map (με δεδομένη μια συνάρτηση και μια λίστα, επίστρεψε τη λίστα με τα αποτελέσματα της εφαρμογής της function(item) σε όλα τα στοιχεία);
• foldl (με δεδομένη μια συνάρτηση, μια λίστα και έναν αρχικό συσσωρευτή, δίπλωσε (ανάγωγε) κάθε στοιχείο στον συσσωρευτή από τα αριστερά);
• foldr (με δεδομένη μια συνάρτηση, μια λίστα και έναν αρχικό συσσωρευτή, δίπλωσε (ανάγωγε) κάθε στοιχείο στον συσσωρευτή από τα δεξιά);
• reverse (με δεδομένη μια λίστα, επίστρεψε μια λίστα με όλα τα αρχικά στοιχεία, αλλά σε αντίστροφη σειρά).

Σημείωσε ότι η σειρά με την οποία περνιούνται τα ορίσματα στις συναρτήσεις δίπλωσης (foldl, foldr) έχει σημασία.

Υλοποίηση

Θα χρειαστεί να χρησιμοποιήσεις τον παραμετρικό πολυμορφισμό της Odin (πιο γνωστός ως generics) για αυτή την άσκηση. Αν δεν έχεις ξαναδεί αυτό το χαρακτηριστικό, ορίστε μια γρήγορη εισαγωγή για να ξεκινήσεις.

Ο παραμετρικός πολυμορφισμός είναι ένα χαρακτηριστικό των γλωσσών προγραμματισμού που επιτρέπει στους προγραμματιστές να είναι λιγότερο συγκεκριμένοι (πιο γενικοί, εξ ου και το όνομα) ως προς τους τύπους που χρησιμοποιούν στον κώδικά τους, διατηρώντας παράλληλα την ασφάλεια τύπων. Προφανώς αυτό έχει νόημα μόνο σε γλώσσες με ισχυρή τυποποίηση, όπως η Odin.

Ας ξεκινήσουμε με ένα παράδειγμα. Ας πούμε ότι θέλεις να αυξήσεις όλα τα στοιχεία ενός πίνακα κατά μια σταθερή τιμή, ένα αρκετά απλό πρόβλημα.

incr_array_int :: proc(a: []int, by: int) -> []int {

    new_array := make([]int, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Τι γίνεται όμως αν τώρα χρειάζεσαι την ίδια λειτουργικότητα και για αριθμούς κινητής υποδιαστολής;

incr_array_f64 :: proc(a: []f64, by: f64) -> []f64 {

    new_array := make([]f64, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Και μετά για ανυπόγραφους ακέραιους, δεκαδικούς 32 bit και ούτω καθεξής;

Σε λίγο καταλήγεις με μια πλειάδα διαδικασιών που κάνουν ακριβώς την ίδια δουλειά αλλά για διαφορετικό τύπο. Αν χρειαστεί ποτέ να ενημερώσεις τη λογική, τότε πρέπει να βεβαιωθείς ότι το κάνεις για όλες τις παραλλαγές, κάτι που μπορεί να γίνει πολλή δουλειά συντήρησης. Το άλλο ενοχλητικό είναι ότι πρέπει να δίνεις διαφορετικά ονόματα σε καθεμία από τις διαδικασίες, αφού η Odin δεν υποστηρίζει σιωπηρή υπερφόρτωση διαδικασιών (θα μπορούσες να χρησιμοποιήσεις ρητή υπερφόρτωση, αλλά αυτό είναι ιστορία για άλλη άσκηση).

Η Odin, όντας μια πρακτική γλώσσα, προσφέρει μια λύση με τον παραμετρικό πολυμορφισμό. Αρκεί ο μεταγλωττιστής να μπορεί να καταλάβει τον τύπο μιας παραμέτρου σε χρόνο μεταγλώττισης, και μπορείς να της δώσεις ένα γενικό όνομα, όπως T. Ας ξαναγράψουμε τη διαδικασία παραπάνω:

incr_array :: proc(a: []$T, by: T) -> []T {

    new_array := make([]T, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Πρόσεξε ότι αντικαταστήσαμε όλες τις δηλώσεις τύπων (int ή f64) με T και ότι πριν από την πρώτη εμφάνιση του T υπάρχει ένα σύμβολο δολαρίου ($T). Ο τύπος $T λέει στον μεταγλωττιστή της Odin ότι το όνομα T είναι ένα γενικό όνομα για τον τύπο, που θα αντικατασταθεί με το πραγματικό όνομα κατά τη μεταγλώττιση. Και αφού ο μεταγλωττιστής γνωρίζει πλέον τον γενικό τύπο T, οι επόμενες εμφανίσεις του ίδιου τύπου χρειάζεται μόνο να σημειωθούν με το όνομα του τύπου που επιλέχθηκε (T).

Τώρα μπορείς να γράψεις κώδικα όπως:

a_int := incr_array([]int{1, 2, 3}, 10)
a_f64 := incr_array([]f64{1.0, 2.0, 3.0}, 10.0)

Στην πρώτη εντολή, ο μεταγλωττιστής της Odin θα ταυτίσει τον τύπο της πρώτης παραμέτρου ([]int) με τον τύπο της γενικής παραμέτρου ([]$T), θα συμπεράνει ότι T = int και θα προχωρήσει στη μεταγλώττιση μιας έκδοσης όπου όλες οι επόμενες εμφανίσεις του T έχουν αντικατασταθεί από int (ισοδύναμης με την εξειδικευμένη έκδοση incr_array_int() παραπάνω). Αν παρέλειπες το σύμβολο του δολαρίου στον ορισμό της πρώτης παραμέτρου, ο μεταγλωττιστής θα έψαχνε στο τρέχον πακέτο και στη λίστα των εισαγωγών για έναν τύπο με το όνομα T και κατά πάσα πιθανότητα θα επέστρεφε το σφάλμα μεταγλώττισης Error: Undeclared name: T.

Η δεύτερη εντολή λειτουργεί ακριβώς όπως η πρώτη, μόνο που ο μεταγλωττιστής αναγνωρίζει το T ως f64.

Συνηθίζεται να δίνουμε στους γενικούς τύπους ονόματα με ένα μόνο γράμμα (τα T και E χρησιμοποιούνται συχνά)

Τώρα θα πρέπει να ξέρεις αρκετά για τους παραμετρικούς πολυμορφισμούς, γνωστούς και ως γενικούς τύπους, ώστε να αντιμετωπίσεις την άσκηση Πράξεις με λίστες.