Lists II

Έχουμε ήδη δει ότι στην Haskell οι λίστες μπορούν να δημιουργηθούν με τον τελεστή cons (:) και την κενή λίστα []. Στη συνέχεια θα δούμε χαρακτηριστικά της Haskell όπως οι άπειρες λίστες, οι περιφραστικές λίστες και οι συναρτήσεις υψηλότερης τάξης.

Ανακατασκευή λιστών

Στη συνέχεια παρουσιάζεται μια συνάρτηση που διπλασιάζει κάθε στοιχείο μιας λίστας.

doubleList :: [Integer] -> [Integer]
doubleList [] = []
doubleList (n:ns) = (2 * n) : doubleList ns

doubleList.hs

Ας δούμε τη σταδιακή αποτίμηση της έκφρασης doubleList [1,2,3,4]

doubleList 1:[2,3,4] = (1*2) : doubleList (2 : [3,4])
                     = (1*2) : (2*2) : doubleList (3 : [4])
                     = (1*2) : (2*2) : (3*2) : doubleList (4 : [])
                     = (1*2) : (2*2) : (3*2) : (4*2) : doubleList []
                     = (1*2) : (2*2) : (3*2) : (4*2) : []
                     = 2 : 4 : 6 : 8 : []
                     = [2, 4, 6, 8]

Αξίζει να σημειωθεί ότι η στιγμή στην οποία θα γίνει ο υπολογισμός των γινομένων δεν επηρεάζει το αποτέλεσμα. Η Haskell ως γλώσσα οκνηρής αποτίμησης (lazy evaluation) καθυστερεί την αποτίμηση μέχρι να ζητηθεί το τελικό αποτέλεσμα (που μερικές φορές δεν συμβαίνει ποτέ). Από την πλευρά του προγραμματιστή η σειρά αποτίμησης συνήθως δεν έχει σημασία.

Γενίκευση

Για να τριπλασιάσουμε κάθε στοιχείο μιας λίστας μπορούμε να γράψουμε τη συνάρτηση tripleList αντίστοιχα με την doubleList.

tripleList :: [Integer] -> [Integer]
tripleList [] = []
tripleList (n:ns) = (3 * n) : tripleList ns

tripleList.hs

ή μπορούμε να γενικεύσουμε με μια συνάρτηση που καλύπτει όλες τις περιπτώσεις πολλαπλασιαστών.

multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList _ [] = []
multiplyList m (n:ns) = (m * n) : multiplyList m ns

multiplyList.hs

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

Μεγαλύτερη γενίκευση

Ας γενικεύσουμε περισσότερο τη συνάρτηση multiplyList έτσι ώστε να χρησιμοποιεί διαφορετικό τελεστή.

Currying Όταν στην Haskell γράφουμε 5 * 7 η συνάρτηση (*) δεν λαμβάνει 2 ορίσματα απευθείας, αλλά πρώτα λαμβάνει το όρισμα 5 και επιστρέφει τη νέα συνάρτηση 5*. Στη συνέχεια η συνάρτηση 5* δέχεται ως όρισμα το 7 και επιστρέφει το αποτέλεσμα που αποτιμάται στην τελική τιμή (35).

Όλες οι συναρτήσεις στην Haskell δέχονται μόνο ένα όρισμα πραγματικά. Ωστόσο, όταν γνωρίζουμε πόσες ενδιάμεσες συναρτήσεις θα δημιουργηθούν για να φτάσουμε στο τελικό αποτέλεσμα, μπορούμε να θεωρήσουμε ότι οι συναρτήσεις λαμβάνουν ακριβώς τόσα ορίσματα.

Η διαδικασία δημιουργίας ενδιάμεσων συναρτήσεων, καθώς μια συνάρτηση δέχεται ορίσματα ονομάζεται currying (από τον Haskell Curry).

Η συνάρτηση map

Μια ακόμα γενίκευση συναρτήσεως όπως οι προηγούμενες είναι η συνάρτηση map.

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

Με την map εύκολα μπορούμε να υλοποιήσουμε διαφορετικές συναρτήσεις όπως τις ακόλουθες:

multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList m = map ((*) m)

heads :: [[a]] -> [a]
heads = map head

Prelude> heads [[1,2,3,4],[4,3,2,1],[5,10,15]]
[1,4,5]

Συναρτήσεις όπως η map που λαμβάνουν ως παραμέτρους άλλες συναρτήσεις ονομάζονται συναρτήσεις υψηλότερης τάξης.

Διάφορα κόλπα

Μερικές χρήσιμες γνώσεις για τις λίστες.

Συμβολισμός dot dot

Η Haskell διαθέτει έναν βολικό σύντομο συμβολισμό για τη συγγραφή διαταγμένων λιστών ακεραίων με κανονικά διαστήματα μεταξύ τους. Για παράδειγμα:

Code             Result
----             ------
[1..10]          [1,2,3,4,5,6,7,8,9,10]
[2,4..10]        [2,4,6,8,10]
[5,4..1]         [5,4,3,2,1]
[1,3..10]        [1,3,5,7,9]

Ο ίδιος συμβολισμός μπορεί να χρησιμοποιηθεί σε λίστες χαρακτήρων ή και για λίστες αριθμών κινητής υποδιαστολής (προσοχή όμως στα λάθη στρογγυλοποίησης).

['a'..'z']
"abcdefghijklmnopqrstuvwxyz"
 [0,0.1..1]
[0.0,0.1,0.2,0.30000000000000004,0.4,0.5,0.6000000000000001,0.7000000000000001,0.8,0.9,1.0]

Άπειρες λίστες

Λόγω της οκνηρής αποτίμησης οι λίστες της Haskell μπορούν να είναι άπειρες. Για παράδειγμα το [1..] δημιουργεί μια άπειρη λίστα ακεραίων που ξεκινά με το 1.

Στις περισσότερες περιπτώσεις μπορούμε να χειριστούμε τις άπειρες λίστες ως μια κοινή λίστα. Αν και δεν μπορούμε να ταξινομήσουμε ή να εκτυπώσουμε μια άπειρη λίστα ωστόσο μπορούμε αν γράψουμε κάτι όπως το ακόλουθο:

evens = doubleList [1..]

δηλαδή να ορίσουμε τους άρτιους ως την άπειρη λίστα [2,4,6,8,..] και να περάσουμε το evens σε άλλες συναρτήσεις που χρειάζεται να αποτιμήσουν μέρος της λίστας για τον υπολογισμό του τελικού αποτελέσματος.

Μερικά σχόλια για τις head και tail

Έχουμε την επιλογή να χρησιμοποιούμε είτε το pattern (:) είτε τις συναρτήσεις head/tail για τη διάσπαση λιστών. Ωστόσο, οι head/tail αποτυγχάνουν όταν η λίστα είναι κενή. Υπάρχει βέβαια η συνάρτηση null :: [a] -> Bool που επιστρέφει True αν η λίστα είναι κενή ή False αλλιώς. Γενικά όμως προτιμάται το pattern (:) καθώς είναι προτιμότερη η συγγραφή κώδικα που ταιριάζει την κενή λίστα, παρά η συγγραφή εκφράσεων if-then-else με το null.