Αναδρομή

Οι αναδρομικές συναρτήσεις έχουν κεντρικό ρόλο στην Haskell.

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

Αριθμητική αναδρομή

Θα εξετάσουμε τη συνάρτηση παραγοντικό (factorial) που δέχεται ως όρισμα έναν μη αρνητικό ακέραιο n και πολλαπλασιάζει όλους τους ακέραιους που είναι μικρότεροι ή ίσοι του ακεραίου n.

π.χ. 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720

Το παραγοντικό οποιουδήποτε μη αρνητικού ακεραίου είναι το γινόμενο του ακεραίου με το παραγοντικό του κατά ένα μικρότερου ακεραίου, με εξαίρεση το παραγοντικό του μηδενός το οποίο εξ’ ορισμού είναι 1.

Άρα, η συνάρτηση του παραγοντικού ορίζεται ως εξής:

• Το παραγοντικό του 0 είναι 1.
• Το παραγοντικό οποιουδήποτε αριθμού είναι ο αριθμός αυτός πολλαπλασιασμένος με το παραγοντικό του κατά ένα μικρότερου αριθμού.

Ο παραπάνω ορισμός μπορεί να μεταφραστεί απευθείας στην Haskell:

factorial 0 = 1
factorial n = n * factorial (n - 1)

factorial.hs

Προσοχή πρέπει να δοθεί στις παρενθέσεις, αν δεν υπήρχαν η συντακτική ανάλυση θα γινόταν ως (factorial n) -1 καθώς η εφαρμογή της συνάρτησης έχει προτεραιότητα από οτιδήποτε άλλο όταν δεν ορίζεται κάποια άλλη ομαδοποίηση με παρενθέσεις. Η εφαρμογή συναρτήσεων προσδένεται ισχυρότερα (binds more tightly) από οτιδήποτε άλλο.

Ας δούμε σταδιακά την εκτέλεση του factorial 3:

• Το 3 δεν είναι 0, οπότε υπολογίζουμε το παραγοντικό του 2
  • Το 2 δεν είναι 0, οπότε υπολογίζουμε το παραγοντικό του 1
    • Το 1 δεν είναι 0, οπότε υπολογίζουμε το παραγοντικό του 0
      • Το 0 είναι 0, οπότε επιστρέφει 1
    • Για να ολοκληρώσουμε τον υπολογισμό του factorial 1, πολλαπλασιάζουμε τον τρέχοντα αριθμό, 1, με το παραγοντικό του 0, που είναι 1, λαμβάνοντας 1 (1 * 1)
  • Για να ολοκληρώσουμε τον υπολογισμό του factorial 2, πολλαπλασιάζουμε τον τρέχοντα αριθμό, 2, με το παραγοντικό του 1, που είναι 1, λαμβάνοντας 2 (2 * 1 * 1)
• Για να ολοκληρώσουμε τον υπολογισμό του factorial 3, πολλαπλασιάζουμε τον τρέχοντα αριθμό, 3, με το παραγοντικό του 2, που είναι 2, λαμβάνοντας 6 (3* 2 * 1 * 1)

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

> ghci
GHCi, version 8.10.7: https://www.haskell.org/ghc/  :? for help
Prelude> :l factorial.hs
[1 of 1] Compiling Main             ( factorial.hs, interpreted )
Ok, one module loaded.
*Main> factorial 100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
*Main> factorial (-1)

Βρόχοι, αναδρομή και συσσωρευτικοί παράμετροι

Οι προστακτικές γλώσσες τυπικά χρησιμοποιούν επαναλήψεις. Για παράδειγμα η ακόλουθη συνάρτηση στη C υπολογίζει το παραγοντικό.

int factorial(int n) {
  int res = 1;
  for ( ; n > 1; n--)
    res *= n;
  return res;
}

factorial.c

Ο παραπάνω κώδικας δεν μπορεί να γραφεί απευθείας στη Haskell καθώς δεν είναι δυνατή η αλλαγή της τιμής των μεταβλητών res και n. Ωστόσο, μπορεί να μετατραπεί μια επανάληψη σε μια ισοδύναμη αναδρομική μορφή κάνοντας κάθε μεταβλητή της επανάληψης όρισμα της αναδρομικής συνάρτησης. Για παράδειγμα η παραπάνω συνάρτηση στη C μπορεί να γραφεί ``ισοδύναμα’’ και στην Haskell.

Παράδειγμα: Χρήση αναδρομής για προσομοίωση επανάληψης

factorial n = go n 1
    where
    go n res
        | n > 1     = go (n - 1) (res * n)
        | otherwise = res

factorialAcc.hs

Η go είναι μια βοηθητική συνάρτηση η οποία στην πράξη πραγματοποιεί τον υπολογισμό του παραγοντικού. Δέχεται το επιπλέον όρισμα, res, που χρησιμοποιείται ως συσσωρευτική παράμετρος (accumulating parameter), στην οποία δημιουργείται το τελικό αποτέλεσμα.

Άλλες αναδρομικές συναρτήσεις

Πολλές άλλες αριθμητικές συναρτήσεις, πέρα του παραγοντικού, μπορούν να διατυπωθούν αναδρομικά. Για παράδειγμα ο πολλαπλασιασμός.

Παράδειγμα: Αναδρομικός ορισμός πολλαπλασιασμού

mult _ 0 = 0                      -- οτιδήποτε επί  0 κάνει 0
mult n m = (mult n (m - 1)) + n   -- αναδρομή: πολλαπλασίασε με ένα λιγότερο, και πρόσθεσε ένα επιπλέον αντίγραφο

Αναδρομή βασισμένη σε λίστες

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

Παράδειγμα: ο αναδρομικός ορισμός της length

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

myLength.hs

Ο τελεστής συνένωσης ++ συνενώνει δύο λίστες.

Παράδειγμα: Ο αναδρομικός ορισμός του ++

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "Hello " ++ "world" -- Strings are lists of Chars
"Hello world"

(++) :: [a] -> [a] -> [a]
[] ++ ys     = ys
(x:xs) ++ ys = x : xs ++ ys

Ο τύπος περιγράφει ότι η (++) δέχεται δύο λίστες του ίδιου τύπου και επιστρέφει μια λίστα του ίδιου τύπου. Η βασική περίπτωση περιγράφει ότι η συνένωση της κενής λίστας με μια άλλη λίστα ys δίνει την ίδια τη λίστα ys. Τέλος, η αναδρομική περίπτωση πρώτα διασπά την πρώτη λίστα σε κεφαλή x, και ουρά xs και λέει ότι για να συνενωθούν οι δύο λίστες, συνενώνουμε την ουρά της πρώτης λίστας με τη δεύτερη λίστα, και στη συνέχεια προσαρτούμε την κεφαλή x στην αρχή.

Μην ενθουσιάζεστε υπερβολικά με τη συγγραφή αναδρομικών συναρτήσεων…

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

factorial n = product [1..n]

factorialProd.hs