בקיץ שעבר השתתפתי קיץ של Google קוד - תוכנית לסטודנטים מגוגל. מדי שנה בוחרים המארגנים מספר פרויקטים בקוד פתוח, כולל מארגונים ידועים כמו Boost.org и קרן לינוקס. גוגל מזמינה תלמידים מכל העולם לעבוד על הפרויקטים האלה. 

כמשתתף ב-Google Summer of Code 2019, עשיתי פרויקט בתוך הספרייה אצה עם הארגון Haskell.org, אשר מפתחת את שפת Haskell - אחת משפות התכנות הפונקציונליות המפורסמות ביותר. אצה היא ספרייה שמייצגת סוג בטוח ייצוג לגרפים ב- Haskell. הוא משמש, למשל, ב סמנטי - ספריית Github שבונה עצים סמנטיים, גרפי שיחות ותלות המבוססים על קוד ויכולה להשוות ביניהם. הפרויקט שלי היה להוסיף ייצוג בטוח לסוגים עבור גרפים דו-צדדיים ואלגוריתמים עבור הייצוג הזה. 

בפוסט זה אדבר על היישום שלי של אלגוריתם לבדיקת גרף עבור דו-צדדיות ב- Haskell. למרות שהאלגוריתם הוא אחד הבסיסיים ביותר, ליישם אותו בצורה יפה בסגנון פונקציונלי לקח לי מספר איטרציות ודרש די הרבה עבודה. כתוצאה מכך, הסתפקתי ביישום עם שנאי מונדות. 

על עצמי

שמי ואסילי אלפרוב, אני סטודנט שנה רביעית בסנט פטרבורג HSE. מוקדם יותר בבלוג כתבתי על הפרויקט שלי על אלגוריתמים עם פרמטרים и על הטיול לZuriHac. כרגע אני בהתמחות ב אוניברסיטת ברגן בנורבגיה, שם אני עובד על גישות לבעיה צביעה רשימה. תחומי העניין שלי כוללים אלגוריתמים עם פרמטרים ותכנות פונקציונלי.

על יישום האלגוריתם

פְּתִיחַ

סטודנטים המשתתפים בתוכנית מוזמנים מאוד לכתוב בלוג. הם סיפקו לי פלטפורמה לבלוג קיץ של האסקל. מאמר זה הוא תרגום מאמרים, שנכתב על ידי שם ביולי באנגלית, עם הקדמה קצרה. 

ניתן למצוא Pull Request עם הקוד המדובר כאן.

אתה יכול לקרוא על תוצאות העבודה שלי (באנגלית) כאן.

פוסט זה נועד להכיר לקורא את המושגים הבסיסיים בתכנות פונקציונלי, אם כי אנסה להיזכר בכל המונחים בהם נעשה שימוש בבוא הזמן.

בדיקת גרפים לדו-צדדיות 

אלגוריתם לבדיקת גרף לדו-חלקיות ניתן בדרך כלל בקורס על אלגוריתמים כאחד מאלגוריתמי הגרפים הפשוטים ביותר. הרעיון שלו פשוט: תחילה אנו איכשהו שמים קודקודים בחלק השמאלי או הימני, וכאשר נמצא קצה סותר, אנו טוענים שהגרף אינו דו-חלקי.

קצת יותר פירוט: ראשית שמנו קודקוד כלשהו בחלק השמאלי. ברור שכל השכנים של הקודקוד הזה חייבים לשכב באונה הימנית. יתר על כן, כל השכנים של השכנים של קודקוד זה חייבים לשכב באונה השמאלית, וכן הלאה. אנו ממשיכים להקצות שיתופים לקודקודים כל עוד יש קודקודים ברכיב המחובר של הקודקוד איתו התחלנו שלא הקצינו להם שכנים. לאחר מכן נחזור על פעולה זו עבור כל הרכיבים המחוברים.

אם יש קצה בין קודקודים שנופלים לאותה מחיצה, לא קשה למצוא מחזור אי זוגי בגרף, דבר הידוע (ודי ברור) בלתי אפשרי בגרף דו-חלקי. אחרת, יש לנו מחיצה נכונה, מה שאומר שהגרף הוא דו-חלקי.

בדרך כלל, אלגוריתם זה מיושם באמצעות רוחב חיפוש ראשון או עומק חיפוש ראשון. בשפות הכרחי, בדרך כלל נעשה שימוש בחיפוש עומק ראשון מכיוון שהוא מעט פשוט יותר ואינו דורש מבני נתונים נוספים. בחרתי גם בחיפוש עומק-ראשון מכיוון שהוא מסורתי יותר.

לפיכך, הגענו לתכנית הבאה. אנו חוצים את קודקודי הגרף באמצעות חיפוש עומק ראשון ומקצים להם שיתופים, משנים את מספר השיתוף תוך כדי תנועה לאורך הקצה. אם ננסה להקצות שיתוף לקודקוד שכבר הוקצה לו שיתוף, נוכל לומר בבטחה שהגרף אינו דו-חלקי. ברגע שכל הקודקודים מוקצים שיתוף ובדקנו את כל הקצוות, יש לנו מחיצה טובה.

טוהר החישובים

בהסקל אנו מניחים שכל החישובים הם לְנַקוֹת. עם זאת, אם זה היה באמת המקרה, לא הייתה לנו דרך להדפיס שום דבר למסך. בכלל, נקי החישובים כל כך עצלנים שאין אחד נקי סיבות לחשב משהו. כל החישובים המתרחשים בתוכנית נאלצים איכשהו להיכנס "טָמֵא" מונאדה IO.

מונאדות הן דרך לייצג חישובים איתה אפקטים בהאסקל. הסבר כיצד הם פועלים הוא מעבר לתחום הפוסט הזה. תיאור טוב וברור ניתן לקרוא באנגלית כאן.

כאן אני רוצה לציין שבעוד כמה מונאות, כמו IO, מיושמות באמצעות קסם מהדר, כמעט כל האחרות מיושמות בתוכנה וכל החישובים בהן טהורים.

יש הרבה אפקטים ולכל אחד יש את המונאדה שלו. זוהי תיאוריה מאוד חזקה ויפה: כל המונאות מיישמות את אותו ממשק. נדבר על שלוש המונאדות הבאות:

• או ea הוא חישוב שמחזיר ערך מסוג a או זורק חריג מסוג e. ההתנהגות של המונאדה הזו דומה מאוד לטיפול בחריגים בשפות ציווי: ניתן לתפוס שגיאות או להעביר אותן הלאה. ההבדל העיקרי הוא שהמונאדה מיושמת באופן הגיוני לחלוטין בספרייה הסטנדרטית ב- Haskell, בעוד ששפות ציווי משתמשות בדרך כלל במנגנוני מערכת ההפעלה.
• מצב sa הוא חישוב שמחזיר ערך מסוג a ויש לו גישה למצב ניתן לשינוי מסוג s.
• אולי. המונאדה אולי מבטאת חישוב שניתן להפריע בכל עת על ידי החזרת כלום. עם זאת, נדבר על הטמעת מחלקה MonadPlus לסוג Maybe, המבטא את ההשפעה ההפוכה: מדובר בחישוב שניתן להפריע בכל עת על ידי החזרת ערך ספציפי.

יישום האלגוריתם

יש לנו שני סוגי נתונים, גרף a ו-Bigraph ab, הראשון שבהם מייצג גרפים עם קודקודים המסומנים בערכים מסוג a, והשני מייצג גרפים דו-חלקיים עם קודקודים בצד שמאל המסומנים בערכים מסוג a וימין -קודקודי צד המסומנים בערכים מסוג b.

אלו לא טיפוסים מספריית אצה. לאגה אין ייצוג לגרפים דו-צדדיים בלתי מכוונים. הכנתי את הסוגים האלה בשביל הבהירות.

נזדקק גם לפונקציות עוזר עם החתימות הבאות:

-- Список соседей данной вершины.
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 של המונאדה שבחרנו: נצטרך רק להכניס את כל הקודקודים מהנתיב לתוצאה המוחזרת מהפונקציה הרקורסיבית.

הרעיון הראשון שלי היה להשתמש במונאדה "Ether", שנראה כי מיישמת בדיוק את ההשפעות שאנו צריכים. היישום הראשון שכתבתי היה קרוב מאוד לאפשרות הזו. למעשה, היו לי חמישה יישומים שונים בשלב מסוים ובסופו של דבר הסתפקתי באחד אחר.

ראשית, אנחנו צריכים לשמור על מערך אסוציאטיבי של מזהי שיתוף - זה משהו לגבי State. שנית, אנחנו צריכים להיות מסוגלים לעצור כאשר מתגלה קונפליקט. זה יכול להיות Monad עבור כל אחד, או MonadPlus עבור אולי. ההבדל העיקרי הוא שאחד מהם יכול להחזיר ערך אם החישוב לא הופסק, ואולי מחזיר רק מידע על זה במקרה זה. מכיוון שאנחנו לא צריכים ערך נפרד להצלחה (הוא כבר מאוחסן ב-State), אנחנו בוחרים אולי. וברגע שבו אנחנו צריכים לשלב את ההשפעות של שתי מונאדות, הן יוצאות החוצה שנאי מונאות, המשלבים בדיוק את ההשפעות הללו.

למה בחרתי בסוג כל כך מורכב? שתי סיבות. ראשית, היישום מתברר כדומה מאוד לציווי. שנית, עלינו לתמרן את ערך ההחזרה במקרה של קונפליקט כאשר חוזרים מהרקורסיה כדי לשחזר את הלולאה האי זוגית, מה שהרבה יותר קל לעשות במונאדה אולי.

כך אנו מקבלים את היישום הזה.

{-# 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.
• onEdge הוא החלק שבו אנו מבקרים בקצה. זה נקרא פעמיים עבור כל קצה. כאן אנו בודקים אם הקודקוד בצד השני ביקר, ומבקרים בו אם לא. אם ביקרנו, אנו בודקים אם הקצה סותר. אם כן, נחזיר את הערך - החלק העליון של ערימת הרקורסיה, שם כל שאר הקודקודים יוצבו לאחר החזרה.
• processVertex בודק עבור כל קודקוד אם ביקר בו ומפעיל עליו inVertex אם לא.
• dfs מריץ את processVertex על כל הקודקודים.

זה הכל.

היסטוריה של המילה INLINE

המילה INLINE לא הייתה ביישום הראשון של האלגוריתם; היא הופיעה מאוחר יותר. כשניסיתי למצוא יישום טוב יותר, גיליתי שהגרסה הלא-INLINE הייתה איטית יותר בכמה גרפים. בהתחשב בכך שמבחינה סמנטית הפונקציות צריכות לעבוד אותו הדבר, זה מאוד הפתיע אותי. אפילו מוזר יותר, במכונה אחרת עם גרסה אחרת של GHC לא היה הבדל ניכר.

לאחר שביליתי שבוע בקריאת פלט GHC Core, הצלחתי לתקן את הבעיה עם שורה אחת של INLINE מפורשת. בשלב מסוים בין GHC 8.4.4 ל-GHC 8.6.5 האופטימיזר הפסיק לעשות זאת בעצמו.

לא ציפיתי להיתקל בלכלוך כזה בתכנות Haskell. עם זאת, גם היום, מטעמי אופטימיזציה לפעמים עושים טעויות, ותפקידנו לתת להם רמזים. לדוגמא, כאן אנו יודעים שהפונקציה צריכה להיות מוטבעת מכיוון שהיא מוטבעת בגרסת הציווי, וזו סיבה לתת רמז למהדר.

מה קרה אחר כך?

ואז יישמתי את האלגוריתם של הופקרופט-קארפ עם מונאות אחרות, וזה היה סוף התוכנית.

הודות ל-Google Summer of Code, רכשתי ניסיון מעשי בתכנות פונקציונלי, שלא רק עזר לי לקבל התמחות בג'יין סטריט בקיץ שלאחר מכן (אני לא בטוח עד כמה המקום הזה מוכר אפילו בקרב הקהל הבקיא של האבר, אבל זה אחד מהבודדים שבהם אתה יכול לקיץ לעסוק בתכנות פונקציונלי), אבל גם הכיר לי את העולם המופלא של יישום הפרדיגמה הזו בפועל, שונה באופן משמעותי מהניסיון שלי בשפות מסורתיות.

מקור: www.habr.com