Το περασμένο καλοκαίρι πήρα μέρος - ένα πρόγραμμα για μαθητές από την Google. Κάθε χρόνο, οι διοργανωτές επιλέγουν πολλά έργα Ανοιχτού Κώδικα, μεταξύ άλλων από γνωστούς οργανισμούς όπως и . Η Google προσκαλεί μαθητές από όλο τον κόσμο να εργαστούν σε αυτά τα έργα.
Ως συμμετέχων στο Google Summer of Code 2019, έκανα ένα έργο μέσα στη βιβλιοθήκη με την οργάνωση , η οποία αναπτύσσει τη γλώσσα Haskell - μια από τις πιο διάσημες γλώσσες λειτουργικού προγραμματισμού. Το Alga είναι μια βιβλιοθήκη που αντιπροσωπεύει αναπαράσταση για γραφήματα στο Haskell. Χρησιμοποιείται, για παράδειγμα, σε — μια βιβλιοθήκη Github που δημιουργεί σημασιολογικά δέντρα, γραφήματα κλήσεων και εξαρτήσεων με βάση κώδικα και μπορεί να τα συγκρίνει. Το έργο μου ήταν να προσθέσω μια αναπαράσταση ασφαλούς τύπου για διμερή γραφήματα και αλγόριθμους για αυτήν την αναπαράσταση.
Σε αυτήν την ανάρτηση θα μιλήσω για την εφαρμογή μου ενός αλγορίθμου για τον έλεγχο ενός γραφήματος για διμερή χαρακτήρα στο Haskell. Παρόλο που ο αλγόριθμος είναι ένας από τους πιο βασικούς, η άρτια εφαρμογή του σε λειτουργικό στυλ χρειάστηκε πολλές επαναλήψεις και απαιτούσε αρκετή δουλειά. Ως αποτέλεσμα, συμβιβάστηκα σε μια υλοποίηση με μετασχηματιστές monad.
Δήλωση
Ονομάζομαι Vasily Alferov, είμαι τεταρτοετής φοιτητής στο HSE της Αγίας Πετρούπολης. Νωρίτερα στο blog έγραψα и . Αυτή τη στιγμή είμαι σε πρακτική άσκηση στο στη Νορβηγία, όπου εργάζομαι πάνω σε προσεγγίσεις του προβλήματος . Τα ενδιαφέροντά μου περιλαμβάνουν παραμετροποιημένους αλγόριθμους και λειτουργικό προγραμματισμό.
Σχετικά με την υλοποίηση του αλγορίθμου
πρόλογος
Οι μαθητές που συμμετέχουν στο πρόγραμμα ενθαρρύνονται ιδιαίτερα να κάνουν blog. Μου παρείχαν μια πλατφόρμα για το blog . Αυτό το άρθρο είναι μετάφραση , γραμμένο από εμένα εκεί τον Ιούλιο στα αγγλικά, με σύντομο πρόλογο.
Μπορείτε να βρείτε το αίτημα έλξης με τον εν λόγω κωδικό .
Μπορείτε να διαβάσετε για τα αποτελέσματα της δουλειάς μου (στα αγγλικά) .
Αυτή η ανάρτηση προϋποθέτει ότι ο αναγνώστης είναι εξοικειωμένος με τις βασικές έννοιες στον λειτουργικό προγραμματισμό, αν και θα προσπαθήσω να θυμηθώ όλους τους όρους που χρησιμοποιούνται όταν έρθει η ώρα.
Έλεγχος γραφημάτων για διμερή συμπεριφορά
Ένας αλγόριθμος για τον έλεγχο ενός γραφήματος για διμερή συμπεριφορά δίνεται συνήθως σε ένα μάθημα αλγορίθμων ως ένας από τους απλούστερους αλγόριθμους γραφημάτων. Η ιδέα του είναι ξεκάθαρη: πρώτα βάζουμε με κάποιο τρόπο κορυφές στο αριστερό ή το δεξί κοινόχρηστο στοιχείο και όταν βρεθεί μια αντικρουόμενη ακμή, βεβαιώνουμε ότι το γράφημα δεν είναι διμερές.
Λίγη λεπτομέρεια: πρώτα βάζουμε κάποια κορυφή στο αριστερό κοινό. Προφανώς, όλοι οι γείτονες αυτής της κορυφής πρέπει να βρίσκονται στον δεξιό λοβό. Επιπλέον, όλοι οι γείτονες των γειτόνων αυτής της κορυφής πρέπει να βρίσκονται στον αριστερό λοβό και ούτω καθεξής. Συνεχίζουμε να εκχωρούμε κοινόχρηστα στοιχεία σε κορυφές όσο υπάρχουν ακόμα κορυφές στο συνδεδεμένο στοιχείο της κορυφής με το οποίο ξεκινήσαμε και στις οποίες δεν έχουμε εκχωρήσει γείτονες. Στη συνέχεια επαναλαμβάνουμε αυτήν την ενέργεια για όλα τα συνδεδεμένα εξαρτήματα.
Εάν υπάρχει μια άκρη μεταξύ κορυφών που εμπίπτουν στο ίδιο διαμέρισμα, δεν είναι δύσκολο να βρεθεί ένας περιττός κύκλος στο γράφημα, κάτι που είναι ευρέως γνωστό (και προφανώς) αδύνατο σε ένα διμερές γράφημα. Διαφορετικά, έχουμε μια σωστή κατάτμηση, που σημαίνει ότι το γράφημα είναι διμερές.
Συνήθως, αυτός ο αλγόριθμος υλοποιείται χρησιμοποιώντας ή . Σε επιτακτική γλώσσα, η αναζήτηση πρώτα σε βάθος χρησιμοποιείται συνήθως καθώς είναι ελαφρώς απλούστερη και δεν απαιτεί πρόσθετες δομές δεδομένων. Επέλεξα επίσης την αναζήτηση σε βάθος καθώς είναι πιο παραδοσιακή.
Έτσι, καταλήξαμε στο ακόλουθο σχήμα. Διασχίζουμε τις κορυφές του γραφήματος χρησιμοποιώντας την αναζήτηση πρώτα σε βάθος και τους εκχωρούμε μερίδια, αλλάζοντας τον αριθμό του μεριδίου καθώς κινούμαστε κατά μήκος της άκρης. Αν προσπαθήσουμε να αντιστοιχίσουμε μια μετοχή σε μια κορυφή στην οποία έχει ήδη εκχωρηθεί μια μετοχή, μπορούμε να πούμε με ασφάλεια ότι το γράφημα δεν είναι διμερές. Τη στιγμή που σε όλες τις κορυφές εκχωρείται ένα κοινόχρηστο στοιχείο και έχουμε κοιτάξει όλες τις άκρες, έχουμε ένα καλό διαμέρισμα.
Καθαρότητα υπολογισμών
Στο Haskell υποθέτουμε ότι όλοι οι υπολογισμοί είναι ΚΑΘΑΡΗ. Ωστόσο, εάν αυτό ίσχυε πραγματικά, δεν θα είχαμε τρόπο να εκτυπώσουμε τίποτα στην οθόνη. Καθόλου, καθαρό οι υπολογισμοί είναι τόσο τεμπέληδες που δεν υπάρχει ούτε ένας ΚΑΘΑΡΗ λόγοι για να υπολογίσεις κάτι. Όλοι οι υπολογισμοί που πραγματοποιούνται στο πρόγραμμα επιβάλλονται με κάποιο τρόπο "ακάθαρτος" monad IO.
Οι Μονάδες είναι ένας τρόπος για να αναπαραστήσετε τους υπολογισμούς με υπάρχοντα στο Haskell. Η εξήγηση του τρόπου λειτουργίας τους ξεφεύγει από το πεδίο εφαρμογής αυτής της ανάρτησης. Μια καλή και σαφής περιγραφή μπορεί να διαβαστεί στα αγγλικά .
Εδώ θέλω να επισημάνω ότι ενώ ορισμένα monads, όπως το IO, υλοποιούνται μέσω της μαγείας μεταγλωττιστή, σχεδόν όλα τα άλλα υλοποιούνται σε λογισμικό και όλοι οι υπολογισμοί σε αυτά είναι καθαροί.
Υπάρχουν πολλά εφέ και το καθένα έχει τη δική του μονάδα. Αυτή είναι μια πολύ δυνατή και όμορφη θεωρία: όλα τα monads εφαρμόζουν την ίδια διεπαφή. Θα μιλήσουμε για τις ακόλουθες τρεις Μονάδες:
- Είτε το ea είναι ένας υπολογισμός που επιστρέφει μια τιμή τύπου a είτε ρίχνει μια εξαίρεση του τύπου e. Η συμπεριφορά αυτής της μονάδας μοιάζει πολύ με τον χειρισμό εξαιρέσεων σε επιτακτική γλώσσα: τα σφάλματα μπορούν να εντοπιστούν ή να μεταδοθούν. Η κύρια διαφορά είναι ότι το monad υλοποιείται απόλυτα λογικά στην τυπική βιβλιοθήκη στο Haskell, ενώ οι επιταγές γλώσσες χρησιμοποιούν συνήθως μηχανισμούς λειτουργικού συστήματος.
- Η κατάσταση sa είναι ένας υπολογισμός που επιστρέφει μια τιμή τύπου a και έχει πρόσβαση σε μεταβλητή κατάσταση τύπου s.
- Ισως ένα. Το Maybe monad εκφράζει έναν υπολογισμό που μπορεί να διακοπεί ανά πάσα στιγμή επιστρέφοντας το Nothing. Ωστόσο, θα μιλήσουμε για την υλοποίηση της κλάσης MonadPlus για τον τύπο Maybe, η οποία εκφράζει το αντίθετο αποτέλεσμα: είναι ένας υπολογισμός που μπορεί να διακοπεί ανά πάσα στιγμή επιστρέφοντας μια συγκεκριμένη τιμή.
Υλοποίηση του αλγορίθμου
Έχουμε δύο τύπους δεδομένων, το Γράφημα a και το Bigraph ab, ο πρώτος από τους οποίους αντιπροσωπεύει γραφήματα με κορυφές που επισημαίνονται με τιμές τύπου a και ο δεύτερος αντιπροσωπεύει διμερή γραφήματα με κορυφές στην αριστερή πλευρά που επισημαίνονται με τιμές τύπου α και δεξιά - πλευρικές κορυφές με σήμανση με τιμές τύπου b.
Αυτοί δεν είναι τύποι από τη βιβλιοθήκη Alga. Το Alga δεν έχει αναπαράσταση για μη κατευθυνόμενα διμερή γραφήματα. Έφτιαξα τέτοιους τύπους για λόγους σαφήνειας.
Θα χρειαστούμε επίσης βοηθητικές λειτουργίες με τις ακόλουθες υπογραφές:
-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]
-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Είναι εύκολο να δούμε ότι αν κατά την αναζήτηση πρώτου βάθους βρήκαμε μια αντικρουόμενη άκρη, ο περίεργος κύκλος βρίσκεται στην κορυφή της στοίβας αναδρομής. Έτσι, για να το επαναφέρουμε, πρέπει να αποκόψουμε τα πάντα, από τη στοίβα αναδρομής μέχρι την πρώτη εμφάνιση της τελευταίας κορυφής.
Υλοποιούμε την αναζήτηση πρώτα σε βάθος διατηρώντας έναν συσχετιστικό πίνακα αριθμών μετοχών για κάθε κορυφή. Η στοίβα αναδρομής θα διατηρηθεί αυτόματα μέσω της υλοποίησης της κλάσης Functor του monad που επιλέξαμε: θα χρειαστεί μόνο να βάλουμε όλες τις κορυφές από τη διαδρομή στο αποτέλεσμα που επιστρέφεται από την αναδρομική συνάρτηση.
Η πρώτη μου ιδέα ήταν να χρησιμοποιήσω το Either monad, το οποίο φαίνεται να υλοποιεί ακριβώς τα εφέ που χρειαζόμαστε. Η πρώτη υλοποίηση που έγραψα ήταν πολύ κοντά σε αυτήν την επιλογή. Στην πραγματικότητα, είχα πέντε διαφορετικές υλοποιήσεις σε ένα σημείο και τελικά συμβιβάστηκα σε μια άλλη.
Πρώτον, πρέπει να διατηρήσουμε μια συσχετιστική σειρά από αναγνωριστικά μετοχών - αυτό είναι κάτι για το State. Δεύτερον, πρέπει να μπορούμε να σταματήσουμε όταν εντοπίζεται μια σύγκρουση. Αυτό μπορεί να είναι είτε Monad για Είτε είτε MonadPlus για Ίσως. Η κύρια διαφορά είναι ότι το Either μπορεί να επιστρέψει μια τιμή εάν ο υπολογισμός δεν έχει διακοπεί και το Maybe επιστρέφει μόνο πληροφορίες σχετικά με αυτό σε αυτήν την περίπτωση. Επειδή δεν χρειαζόμαστε ξεχωριστή τιμή για επιτυχία (είναι ήδη αποθηκευμένη στην κατάσταση), επιλέγουμε Ίσως. Και τη στιγμή που πρέπει να συνδυάσουμε τα αποτελέσματα δύο μονάδων, βγαίνουν , που συνδυάζουν με ακρίβεια αυτά τα αποτελέσματα.
Γιατί επέλεξα έναν τόσο σύνθετο τύπο; Δύο λόγοι. Πρώτον, η υλοποίηση αποδεικνύεται πολύ παρόμοια με την επιτακτική. Δεύτερον, πρέπει να χειριστούμε την τιμή επιστροφής σε περίπτωση διένεξης όταν επιστρέφουμε από την αναδρομή για να επαναφέρουμε τον περίεργο βρόχο, κάτι που είναι πολύ πιο εύκολο να το κάνουμε στο Maybe monad.
Έτσι παίρνουμε αυτή την υλοποίηση.
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}
data Part = LeftPart | RightPart
otherPart :: Part -> Part
otherPart LeftPart = RightPart
otherPart RightPart = LeftPart
type PartMap a = Map.Map a Part
type OddCycle a = [a]
toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
LeftPart -> Left v
RightPart -> Right v
type PartMonad a = MaybeT (State (PartMap a)) [a]
detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
(Just c, _) -> Left $ oddCycle c
(Nothing, m) -> Right $ toBipartiteWith (toEither m) g
where
inVertex :: Part -> a -> PartMonad a
inVertex p v = ((:) v) <$> do modify $ Map.insert v p
let q = otherPart p
msum [ onEdge q u | u <- neigbours v g ]
{-# INLINE onEdge #-}
onEdge :: Part -> a -> PartMonad a
onEdge p v = do m <- get
case v `Map.lookup` m of
Nothing -> inVertex p v
Just q -> do guard (q /= p)
return [v]
processVertex :: a -> PartMonad a
processVertex v = do m <- get
guard (v `Map.notMember` m)
inVertex LeftPart v
dfs :: PartMonad a
dfs = msum [ processVertex v | v <- vertexList g ]
oddCycle :: [a] -> [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
Το μπλοκ όπου είναι ο πυρήνας του αλγορίθμου. Θα προσπαθήσω να εξηγήσω τι συμβαίνει μέσα σε αυτό.
- Το inVertex είναι το μέρος της αναζήτησης στο βάθος όπου επισκεπτόμαστε την κορυφή για πρώτη φορά. Εδώ εκχωρούμε έναν αριθμό κοινής χρήσης στην κορυφή και εκτελούμε το onEdge σε όλους τους γείτονες. Εδώ επαναφέρουμε επίσης τη στοίβα κλήσεων: αν το msum επέστρεψε μια τιμή, πιέζουμε την κορυφή v εκεί.
- Το oneEdge είναι το μέρος όπου επισκεπτόμαστε την άκρη. Καλείται δύο φορές για κάθε άκρη. Εδώ ελέγχουμε αν έχει γίνει επίσκεψη στην κορυφή στην άλλη πλευρά και αν όχι. Σε περίπτωση επίσκεψης, ελέγχουμε αν η άκρη είναι σε διένεξη. Εάν είναι, επιστρέφουμε την τιμή - την κορυφή της στοίβας αναδρομής, όπου όλες οι άλλες κορυφές θα τοποθετηθούν μετά την επιστροφή.
- Το processVertex ελέγχει για κάθε κορυφή εάν έχει επισκεφθεί και εκτελεί το inVertex σε αυτήν εάν όχι.
- Το dfs εκτελεί το processVertex σε όλες τις κορυφές.
Αυτά.
Ιστορία της λέξης INLINE
Η λέξη INLINE δεν ήταν στην πρώτη εφαρμογή του αλγορίθμου· εμφανίστηκε αργότερα. Όταν προσπάθησα να βρω μια καλύτερη υλοποίηση, διαπίστωσα ότι η μη INLINE έκδοση ήταν αισθητά πιο αργή σε ορισμένα γραφήματα. Λαμβάνοντας υπόψη ότι σημασιολογικά οι συναρτήσεις πρέπει να λειτουργούν το ίδιο, αυτό με εξέπληξε πολύ. Ακόμη πιο περίεργο, σε άλλο μηχάνημα με διαφορετική έκδοση GHC δεν υπήρχε αξιοσημείωτη διαφορά.
Αφού πέρασα μια εβδομάδα διαβάζοντας την έξοδο GHC Core, μπόρεσα να διορθώσω το πρόβλημα με μια γραμμή ρητού INLINE. Σε κάποιο σημείο μεταξύ GHC 8.4.4 και GHC 8.6.5, ο βελτιστοποιητής σταμάτησε να το κάνει αυτό από μόνος του.
Δεν περίμενα να συναντήσω τέτοια βρωμιά στον προγραμματισμό Haskell. Ωστόσο, ακόμη και σήμερα, οι βελτιστοποιητές κάνουν μερικές φορές λάθη και είναι δουλειά μας να τους δίνουμε συμβουλές. Για παράδειγμα, εδώ γνωρίζουμε ότι η συνάρτηση πρέπει να είναι ενσωματωμένη επειδή είναι ενσωματωμένη στην έκδοση επιτακτικού, και αυτός είναι ένας λόγος για να δώσουμε μια υπόδειξη στον μεταγλωττιστή.
Τι έγινε μετά?
Στη συνέχεια εφάρμοσα τον αλγόριθμο Hopcroft-Karp με άλλες μονάδες και αυτό ήταν το τέλος του προγράμματος.
Χάρη στο Google Summer of Code, απέκτησα πρακτική εμπειρία στον λειτουργικό προγραμματισμό, η οποία όχι μόνο με βοήθησε να κάνω πρακτική στην Jane Street το επόμενο καλοκαίρι (δεν είμαι σίγουρος πόσο γνωστό είναι αυτό το μέρος ακόμη και μεταξύ του γνωστού κοινού του Habr, αλλά είναι ένα από τα λίγα που μπορείτε να το καλοκαίρι για να ασχοληθείτε με τον λειτουργικό προγραμματισμό), αλλά και με εισήγαγε στον υπέροχο κόσμο της εφαρμογής αυτού του παραδείγματος στην πράξη, σημαντικά διαφορετικό από την εμπειρία μου στις παραδοσιακές γλώσσες.
Πηγή: www.habr.com