ฤดูร้อนที่แล้วฉันเข้าร่วม Google ฤดูร้อนของรหัส - โปรแกรมสำหรับนักศึกษาจาก Google ทุกปี ผู้จัดงานจะคัดเลือกโครงการโอเพ่นซอร์สหลายโครงการ รวมถึงจากองค์กรที่มีชื่อเสียงเช่น Boost.org и มูลนิธิลินุกซ์. Google เชิญนักเรียนจากทั่วทุกมุมโลกมาทำงานในโครงการเหล่านี้ 

ในฐานะผู้เข้าร่วม Google Summer of Code 2019 ฉันได้ทำโปรเจ็กต์ภายในห้องสมุด สาหร่าย กับองค์กร Haskell.orgซึ่งกำลังพัฒนาภาษา Haskell ซึ่งเป็นหนึ่งในภาษาโปรแกรมเชิงฟังก์ชันที่มีชื่อเสียงที่สุด Alga เป็นห้องสมุดที่เป็นตัวแทน ประเภทปลอดภัย การแสดงกราฟใน Haskell มันถูกใช้เช่นใน ความหมาย — ไลบรารี Github ที่สร้างแผนผังความหมาย การเรียก และกราฟการพึ่งพาตามโค้ดและสามารถเปรียบเทียบได้ โครงการของฉันคือการเพิ่มการแสดงประเภทที่ปลอดภัยสำหรับกราฟสองส่วนและอัลกอริธึมสำหรับการแสดงนั้น 

ในโพสต์นี้ ฉันจะพูดถึงการใช้งานอัลกอริธึมของฉันในการตรวจสอบกราฟสำหรับการแบ่งส่วนใน Haskell แม้ว่าอัลกอริธึมจะเป็นหนึ่งในอัลกอริธึมพื้นฐานที่สุด แต่การใช้งานอย่างสวยงามในรูปแบบการใช้งานทำให้ฉันต้องวนซ้ำหลายครั้งและต้องทำงานค่อนข้างมาก ด้วยเหตุนี้ ฉันจึงตัดสินใจใช้งานกับ Monad Transformers 

คำแถลง

ฉันชื่อ Vasily Alferov ฉันเป็นนักเรียนชั้นปีที่สี่ที่ St.Petersburg HSE ก่อนหน้านี้ในบล็อกที่ฉันเขียน เกี่ยวกับโครงการของฉันเกี่ยวกับอัลกอริธึมแบบกำหนดพารามิเตอร์ и เกี่ยวกับการเดินทางไป ZuriHac. ตอนนี้ฉันกำลังฝึกงานอยู่ที่ มหาวิทยาลัยเบอร์เกน ในนอร์เวย์ ซึ่งฉันกำลังหาแนวทางแก้ไขปัญหาอยู่ รายการระบายสี. ความสนใจของฉันรวมถึงอัลกอริธึมแบบกำหนดพารามิเตอร์และการเขียนโปรแกรมเชิงฟังก์ชัน

เกี่ยวกับการนำอัลกอริทึมไปใช้

คำปรารภ

นักเรียนที่เข้าร่วมโครงการได้รับการสนับสนุนอย่างยิ่งให้บล็อก พวกเขาให้แพลตฟอร์มสำหรับบล็อกแก่ฉัน ฤดูร้อนของฮาสเคลล์. บทความนี้เป็นการแปล บทความเขียนโดยฉันที่นั่นในเดือนกรกฎาคมเป็นภาษาอังกฤษ โดยมีคำนำสั้นๆ 

ดึงคำขอพร้อมรหัสที่เป็นปัญหาได้ ที่นี่.

คุณสามารถอ่านเกี่ยวกับผลงานของฉันได้ (เป็นภาษาอังกฤษ) ที่นี่.

โพสต์นี้มีจุดมุ่งหมายเพื่อให้ผู้อ่านคุ้นเคยกับแนวคิดพื้นฐานในการเขียนโปรแกรมเชิงฟังก์ชัน แม้ว่าฉันจะพยายามจำคำศัพท์ทั้งหมดที่ใช้เมื่อถึงเวลาก็ตาม

การตรวจสอบกราฟเพื่อความเท่าเทียมกัน 

อัลกอริธึมสำหรับการตรวจสอบกราฟสำหรับความเป็นเอกภาพมักจะได้รับในหลักสูตรอัลกอริธึมซึ่งเป็นหนึ่งในอัลกอริธึมกราฟที่ง่ายที่สุด แนวคิดของเขาตรงไปตรงมา: ก่อนอื่นเราจะวางจุดยอดไว้ทางซ้ายหรือทางขวา และเมื่อพบขอบที่ขัดแย้งกัน เราก็ยืนยันว่ากราฟนั้นไม่ได้มีสองฝ่าย

รายละเอียดเพิ่มเติมอีกเล็กน้อย: ขั้นแรกเราใส่จุดยอดบางส่วนในส่วนด้านซ้าย แน่นอนว่าเพื่อนบ้านทั้งหมดของจุดยอดนี้ต้องนอนอยู่ในกลีบด้านขวา นอกจากนี้ เพื่อนบ้านทั้งหมดของเพื่อนบ้านของจุดยอดนี้จะต้องนอนอยู่ในกลีบซ้าย และอื่นๆ เรายังคงกำหนดการแบ่งใช้ให้กับจุดยอดต่อไป ตราบใดที่ยังมีจุดยอดอยู่ในองค์ประกอบที่เชื่อมต่อกันของจุดยอดที่เราเริ่มต้นโดยที่เรายังไม่ได้กำหนดเพื่อนบ้านให้ จากนั้นเราจะทำซ้ำการกระทำนี้สำหรับส่วนประกอบที่เชื่อมต่อทั้งหมด

หากมีขอบระหว่างจุดยอดที่อยู่ในพาร์ติชันเดียวกัน การค้นหาวงจรคี่ในกราฟก็ไม่ใช่เรื่องยาก ซึ่งเป็นที่รู้จักกันอย่างแพร่หลาย (และค่อนข้างชัดเจน) ว่าเป็นไปไม่ได้ในกราฟแบบสองฝ่าย มิฉะนั้น เราจะมีพาร์ติชันที่ถูกต้อง ซึ่งหมายความว่ากราฟเป็นแบบทวิภาคี

โดยทั่วไปแล้วอัลกอริทึมนี้จะถูกนำมาใช้โดยใช้ ค้นหาความกว้างก่อน หรือ ค้นหาเชิงลึกก่อน. ในภาษาที่จำเป็น การค้นหาเชิงลึกมักจะใช้เนื่องจากง่ายกว่าเล็กน้อยและไม่ต้องการโครงสร้างข้อมูลเพิ่มเติม ฉันยังเลือกการค้นหาเชิงลึกก่อนเนื่องจากเป็นการค้นหาแบบดั้งเดิมมากกว่า

ดังนั้นเราจึงได้รูปแบบดังต่อไปนี้ เราสำรวจจุดยอดของกราฟโดยใช้การค้นหาเชิงลึกก่อน และกำหนดส่วนแบ่งให้กับจุดยอดเหล่านั้น โดยเปลี่ยนจำนวนส่วนแบ่งเมื่อเราเคลื่อนที่ไปตามขอบ หากเราพยายามกำหนดส่วนแบ่งให้กับจุดยอดที่มีการกำหนดส่วนแบ่งอยู่แล้ว เราสามารถพูดได้อย่างปลอดภัยว่ากราฟนั้นไม่ใช่กราฟแบบสองฝ่าย ทันทีที่จุดยอดทั้งหมดได้รับการแบ่งใช้ และเราตรวจดูขอบทั้งหมดแล้ว เราก็มีพาร์ติชันที่ดี

ความบริสุทธิ์ของการคำนวณ

ใน Haskell เราถือว่าการคำนวณทั้งหมดเป็น ทำความสะอาด. อย่างไรก็ตาม หากเป็นกรณีนี้จริงๆ เราจะไม่มีทางพิมพ์อะไรลงบนหน้าจอได้เลย เลย สะอาด การคำนวณมันขี้เกียจมากจนไม่มีเลย ทำความสะอาด เหตุผลในการคำนวณบางสิ่งบางอย่าง การคำนวณทั้งหมดที่เกิดขึ้นในโปรแกรมจะถูกบังคับให้ทำ "ไม่สะอาด" โมนัด ไอโอ

Monads เป็นวิธีการคำนวณด้วย ผลกระทบ ในฮาสเคลล์ การอธิบายวิธีการทำงานอยู่นอกเหนือขอบเขตของโพสต์นี้ คำอธิบายที่ดีและชัดเจนสามารถอ่านเป็นภาษาอังกฤษได้ ที่นี่.

ในที่นี้ ฉันต้องการชี้ให้เห็นว่าในขณะที่ Monad บางตัว เช่น IO ถูกนำไปใช้ผ่านคอมไพเลอร์เมจิก แต่ตัวอื่นๆ เกือบทั้งหมดถูกนำไปใช้ในซอฟต์แวร์ และการคำนวณทั้งหมดในนั้นล้วนบริสุทธิ์

มีเอฟเฟกต์มากมายและแต่ละอันก็มี Monad ของตัวเอง นี่เป็นทฤษฎีที่แข็งแกร่งและสวยงามมาก: monads ทั้งหมดใช้อินเทอร์เฟซเดียวกัน เราจะพูดถึงพระภิกษุสามองค์ดังต่อไปนี้:

• ea คือการคำนวณที่ส่งคืนค่าประเภท a หรือส่งข้อยกเว้นประเภท e พฤติกรรมของ monad นี้คล้ายกันมากกับการจัดการข้อยกเว้นในภาษาที่จำเป็น: ข้อผิดพลาดสามารถตรวจพบหรือส่งต่อได้ ข้อแตกต่างที่สำคัญคือ monad นั้นถูกนำไปใช้อย่างมีเหตุผลอย่างสมบูรณ์ในไลบรารีมาตรฐานใน Haskell ในขณะที่ภาษาที่จำเป็นมักจะใช้กลไกของระบบปฏิบัติการ
• สถานะ sa คือการคำนวณที่ส่งคืนค่าประเภท a และมีสิทธิ์เข้าถึงสถานะที่ไม่แน่นอนของประเภท s
• บางทีก. monad ของบางทีเป็นการแสดงออกถึงการคำนวณที่สามารถถูกขัดจังหวะได้ตลอดเวลาโดยส่งคืนค่า Nothing อย่างไรก็ตาม เราจะพูดถึงการใช้งานคลาส MonadPlus สำหรับประเภท Maybe ซึ่งแสดงออกถึงผลตรงกันข้าม: เป็นการคำนวณที่สามารถหยุดได้ตลอดเวลาโดยส่งคืนค่าที่ระบุ

การนำอัลกอริทึมไปใช้

เรามีข้อมูลสองประเภท คือ กราฟ a และ Bigraph ab โดยประเภทแรกแทนกราฟที่มีจุดยอดกำกับด้วยค่าประเภท a และประเภทที่สองแทนกราฟสองฝ่ายที่มีจุดยอดด้านซ้ายระบุด้วยค่าประเภท 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 ที่เราเลือก: เราจะต้องใส่จุดยอดทั้งหมดจากเส้นทางไปยังผลลัพธ์ที่ส่งคืนจากฟังก์ชันเรียกซ้ำ

ความคิดแรกของฉันคือการใช้ Monad ทั้งสอง ซึ่งดูเหมือนว่าจะใช้เอฟเฟกต์ที่เราต้องการได้ตรงตามที่ต้องการ การใช้งานครั้งแรกที่ฉันเขียนนั้นใกล้เคียงกับตัวเลือกนี้มาก อันที่จริง ฉันมีการใช้งานที่แตกต่างกันห้าแบบ ณ จุดหนึ่งและในที่สุดก็ตกลงไปที่อีกอันหนึ่ง

อันดับแรก เราต้องรักษาอาร์เรย์ที่เชื่อมโยงของตัวระบุส่วนแบ่ง - นี่คือบางอย่างเกี่ยวกับรัฐ ประการที่สอง เราต้องสามารถหยุดได้เมื่อตรวจพบข้อขัดแย้ง นี่อาจเป็น Monad สำหรับอย่างใดอย่างหนึ่ง หรือ MonadPlus สำหรับอาจจะ ข้อแตกต่างหลักคือ สามารถส่งกลับค่าได้หากการคำนวณยังไม่ถูกหยุด และอาจส่งคืนเฉพาะข้อมูลเกี่ยวกับสิ่งนี้ในกรณีนี้ เนื่องจากเราไม่ต้องการค่าแยกต่างหากสำหรับความสำเร็จ (ค่านั้นถูกจัดเก็บไว้ในสถานะแล้ว) เราจึงเลือกอาจจะ และในขณะที่เราต้องการรวมเอฟเฟกต์ของพระสององค์เข้าด้วยกัน พวกมันก็ออกมา หม้อแปลงโมนาดซึ่งรวมเอฟเฟกต์เหล่านี้เข้าด้วยกันอย่างแม่นยำ

เหตุใดฉันจึงเลือกประเภทที่ซับซ้อนเช่นนี้ สองเหตุผล ประการแรก การนำไปปฏิบัติมีความคล้ายคลึงกับความจำเป็นอย่างมาก ประการที่สอง เราจำเป็นต้องจัดการค่าที่ส่งคืนในกรณีที่มีข้อขัดแย้งเมื่อส่งคืนจากการเรียกซ้ำเพื่อคืนค่าวงคี่ ซึ่งทำได้ง่ายกว่ามากใน Monad ของ Maybe

ดังนั้นเราจึงได้รับการนำไปใช้นี้

{-# 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 กับเพื่อนบ้านทั้งหมด นี่คือที่ที่เราคืนค่า call stack: หาก msum ส่งกลับค่า เราจะกด vertex v ไปตรงนั้น
• onEdge คือส่วนที่เราไปเยี่ยมชม Edge มันถูกเรียกสองครั้งสำหรับแต่ละขอบ ที่นี่เราจะตรวจสอบว่ามีการเยี่ยมชมจุดยอดอีกด้านหนึ่งหรือไม่ และหากไม่เป็นเช่นนั้น หากเยี่ยมชมเราจะตรวจสอบว่าขอบขัดแย้งกันหรือไม่ ถ้าเป็นเช่นนั้น เราจะคืนค่า - ด้านบนสุดของสแต็กการเรียกซ้ำ โดยที่จุดยอดอื่นๆ ทั้งหมดจะถูกวางเมื่อส่งคืน
• processVertex ตรวจสอบแต่ละจุดยอดว่ามีการเยี่ยมชมหรือไม่ และรัน inVertex บนจุดนั้นหรือไม่
• dfs รัน processVertex บนจุดยอดทั้งหมด

นั่นคือทั้งหมดที่

ประวัติความเป็นมาของคำว่า INLINE

คำว่า INLINE ไม่ได้อยู่ในการนำอัลกอริทึมไปใช้ครั้งแรก แต่ปรากฏในภายหลัง เมื่อฉันพยายามค้นหาการใช้งานที่ดีกว่า ฉันพบว่าเวอร์ชันที่ไม่ใช่แบบอินไลน์นั้นช้าลงอย่างเห็นได้ชัดในบางกราฟ เมื่อพิจารณาว่าฟังก์ชันต่างๆ ควรทำงานเหมือนกันในทางความหมาย สิ่งนี้ทำให้ฉันประหลาดใจอย่างมาก แม้แต่คนแปลกหน้าในเครื่องอื่นที่มี GHC เวอร์ชันอื่นก็ไม่มีความแตกต่างที่เห็นได้ชัดเจน

หลังจากใช้เวลาหนึ่งสัปดาห์ในการอ่านเอาต์พุต GHC Core ฉันสามารถแก้ไขปัญหาด้วย INLINE ที่ชัดเจนหนึ่งบรรทัดได้ ณ จุดหนึ่งระหว่าง GHC 8.4.4 และ GHC 8.6.5 เครื่องมือเพิ่มประสิทธิภาพหยุดทำสิ่งนี้ด้วยตัวเอง

ฉันไม่ได้คาดหวังว่าจะต้องเผชิญกับสิ่งสกปรกเช่นนี้ในการเขียนโปรแกรม Haskell อย่างไรก็ตาม แม้กระทั่งทุกวันนี้ เครื่องมือเพิ่มประสิทธิภาพบางครั้งก็ทำผิดพลาด และหน้าที่ของเราคือให้คำแนะนำแก่พวกเขา ตัวอย่างเช่น เรารู้ว่าฟังก์ชันควรอยู่ในบรรทัดเนื่องจากฟังก์ชันอยู่ในบรรทัดในเวอร์ชันที่จำเป็น และนี่คือเหตุผลที่ต้องให้คำแนะนำแก่คอมไพเลอร์

เกิดอะไรขึ้นต่อไป

จากนั้นฉันก็ใช้อัลกอริธึม Hopcroft-Karp กับ Monad อื่นๆ และนั่นคือจุดสิ้นสุดของโปรแกรม

ขอบคุณ Google Summer of Code ที่ทำให้ฉันได้รับประสบการณ์จริงในการเขียนโปรแกรมเชิงฟังก์ชัน ซึ่งไม่เพียงแต่ช่วยให้ฉันได้ฝึกงานที่ Jane Street ในฤดูร้อนถัดมา (ฉันไม่แน่ใจว่าสถานที่นี้เป็นที่รู้จักดีเพียงใดในหมู่ผู้ชมที่มีความรู้ของ Habr ด้วยซ้ำ แต่เป็นหนึ่งในนั้น ในไม่กี่แห่งที่คุณสามารถมีส่วนร่วมในการเขียนโปรแกรมเชิงฟังก์ชั่นได้) แต่ยังทำให้ฉันได้รู้จักกับโลกมหัศจรรย์ของการนำกระบวนทัศน์นี้ไปใช้ในทางปฏิบัติ ซึ่งแตกต่างอย่างมากจากประสบการณ์ของฉันในภาษาดั้งเดิม

ที่มา: will.com