Mùa hè năm ngoái tôi đã tham gia - một chương trình dành cho sinh viên của Google. Hàng năm, ban tổ chức lựa chọn một số dự án Nguồn mở, bao gồm từ các tổ chức nổi tiếng như и . Google mời sinh viên từ khắp nơi trên thế giới làm việc trong các dự án này.
Với tư cách là người tham gia Google Summer of Code 2019, tôi đã thực hiện một dự án trong thư viện với tổ chức , đang phát triển ngôn ngữ Haskell - một trong những ngôn ngữ lập trình hàm nổi tiếng nhất. Alga là một thư viện đại diện biểu diễn đồ thị trong Haskell. Nó được sử dụng, ví dụ, trong — thư viện Github xây dựng cây ngữ nghĩa, biểu đồ cuộc gọi và phụ thuộc dựa trên mã và có thể so sánh chúng. Dự án của tôi là thêm một biểu diễn an toàn về loại cho các biểu đồ và thuật toán lưỡng cực cho biểu diễn đó.
Trong bài đăng này, tôi sẽ nói về việc triển khai thuật toán kiểm tra biểu đồ về tính lưỡng cực trong Haskell. Mặc dù thuật toán là một trong những thuật toán cơ bản nhất, nhưng việc triển khai nó một cách đẹp mắt theo phong cách chức năng đã khiến tôi phải lặp đi lặp lại nhiều lần và đòi hỏi khá nhiều công sức. Kết quả là tôi đã quyết định triển khai với các máy biến áp đơn nguyên.
Về bản thân
Tên tôi là Vasily Alferov, tôi là sinh viên năm thứ tư trường St. Petersburg HSE. Trước đó trong blog tôi đã viết и . Hiện tại tôi đang thực tập tại ở Na Uy, nơi tôi đang nghiên cứu các cách tiếp cận vấn đề . Sở thích của tôi bao gồm các thuật toán tham số hóa và lập trình chức năng.
Về việc thực hiện thuật toán
lời tựa
Học sinh tham gia chương trình được khuyến khích viết blog. Họ đã cung cấp cho tôi nền tảng cho blog . Bài viết này là một bản dịch , được tôi viết ở đó vào tháng XNUMX bằng tiếng Anh, với lời tựa ngắn gọn.
Có thể tìm thấy Yêu cầu kéo với mã được đề cập .
Bạn có thể đọc về kết quả công việc của tôi (bằng tiếng Anh) .
Bài đăng này nhằm mục đích giúp người đọc làm quen với các khái niệm cơ bản trong lập trình hàm, mặc dù tôi sẽ cố gắng nhớ lại tất cả các thuật ngữ được sử dụng khi có thời gian.
Kiểm tra biểu đồ về tính lưỡng cực
Thuật toán kiểm tra tính lưỡng cực của đồ thị thường được đưa ra trong khóa học về thuật toán như một trong những thuật toán đồ thị đơn giản nhất. Ý tưởng của anh ấy rất đơn giản: đầu tiên, bằng cách nào đó, chúng tôi đặt các đỉnh ở phần bên trái hoặc bên phải và khi tìm thấy một cạnh xung đột, chúng tôi khẳng định rằng đồ thị không phải là đồ thị lưỡng cực.
Chi tiết hơn một chút: đầu tiên chúng ta đặt một số đỉnh ở phần bên trái. Rõ ràng tất cả các đỉnh lân cận của đỉnh này đều phải nằm ở thùy phải. Hơn nữa, tất cả các lân cận của đỉnh này phải nằm ở thùy trái, v.v. Chúng tôi tiếp tục gán phần chia sẻ cho các đỉnh miễn là vẫn còn các đỉnh trong thành phần được kết nối của đỉnh mà chúng tôi đã bắt đầu mà chúng tôi chưa gán cho các đỉnh lân cận. Sau đó chúng tôi lặp lại hành động này cho tất cả các thành phần được kết nối.
Nếu có một cạnh giữa các đỉnh nằm trong cùng một phân vùng thì không khó để tìm ra một chu trình lẻ trong đồ thị, điều này được biết đến rộng rãi (và khá rõ ràng) là không thể có trong đồ thị hai bên. Ngược lại, chúng ta có một phân vùng chính xác, có nghĩa là biểu đồ là lưỡng cực.
Thông thường, thuật toán này được thực hiện bằng cách sử dụng hoặc . Trong các ngôn ngữ mệnh lệnh, tìm kiếm theo chiều sâu thường được sử dụng vì nó đơn giản hơn một chút và không yêu cầu cấu trúc dữ liệu bổ sung. Tôi cũng chọn tìm kiếm theo chiều sâu vì nó mang tính truyền thống hơn.
Vì vậy, chúng tôi đã đi đến sơ đồ sau. Chúng tôi duyệt qua các đỉnh của biểu đồ bằng cách sử dụng tìm kiếm theo chiều sâu và gán phần chia sẻ cho chúng, thay đổi số phần chia sẻ khi chúng tôi di chuyển dọc theo cạnh. Nếu chúng ta cố gắng gán một phần chia sẻ cho một đỉnh đã được gán phần chia sẻ đó, chúng ta có thể nói một cách an toàn rằng biểu đồ không phải là đồ thị lưỡng cực. Thời điểm tất cả các đỉnh được gán một phần và chúng ta đã xem xét tất cả các cạnh, chúng ta có một phân vùng tốt.
Độ tinh khiết của tính toán
Trong Haskell, chúng tôi giả định rằng tất cả các phép tính đều được sạch sẽ. Tuy nhiên, nếu điều này thực sự xảy ra thì chúng ta sẽ không có cách nào để in bất cứ thứ gì lên màn hình. Ở tất cả, làm sạch tính toán lười biếng đến nỗi không có một dọn dẹp lý do để tính toán một cái gì đó Tất cả các tính toán xảy ra trong chương trình bằng cách nào đó bị ép buộc vào "ô uế" đơn nguyên IO.
Đơn nguyên là một cách để biểu diễn các phép tính bằng các hiệu ứng trong Haskell. Giải thích cách chúng hoạt động nằm ngoài phạm vi của bài viết này. Một mô tả hay và rõ ràng có thể được đọc bằng tiếng Anh .
Ở đây tôi muốn chỉ ra rằng trong khi một số đơn nguyên, chẳng hạn như IO, được triển khai thông qua phép thuật trình biên dịch, thì hầu hết tất cả các đơn nguyên khác đều được triển khai trong phần mềm và tất cả các phép tính trong đó đều thuần túy.
Có rất nhiều hiệu ứng và mỗi hiệu ứng đều có đơn nguyên riêng. Đây là một lý thuyết rất mạnh mẽ và hay: tất cả các đơn nguyên đều thực hiện cùng một giao diện. Chúng ta sẽ nói về ba đơn nguyên sau:
- ea là phép tính trả về giá trị thuộc loại a hoặc đưa ra ngoại lệ thuộc loại e. Hành vi của đơn nguyên này rất giống với việc xử lý ngoại lệ trong các ngôn ngữ mệnh lệnh: lỗi có thể được phát hiện hoặc truyền lại. Điểm khác biệt chính là monad được triển khai hoàn toàn hợp lý trong thư viện chuẩn của Haskell, trong khi các ngôn ngữ mệnh lệnh thường sử dụng cơ chế của hệ điều hành.
- Trạng thái sa là phép tính trả về giá trị loại a và có quyền truy cập vào trạng thái có thể thay đổi của loại s.
- Có thể là một. Đơn nguyên Maybe biểu diễn một phép tính có thể bị gián đoạn bất cứ lúc nào bằng cách trả về Nothing. Tuy nhiên, chúng ta sẽ nói về việc triển khai lớp MonadPlus cho loại Maybe, thể hiện tác dụng ngược lại: đó là một phép tính có thể bị gián đoạn bất cứ lúc nào bằng cách trả về một giá trị cụ thể.
Thực hiện thuật toán
Chúng ta có hai loại dữ liệu, Graph a và Bigraph ab, loại đầu tiên biểu thị các đồ thị có các đỉnh được gắn nhãn giá trị loại a và loại thứ hai biểu thị đồ thị lưỡng cực có các đỉnh bên trái được gắn nhãn giá trị loại a và phải -các đỉnh bên được dán nhãn giá trị loại b.
Đây không phải là loại từ thư viện Alga. Alga không có biểu diễn cho đồ thị lưỡng cực vô hướng. Tôi đã thực hiện các loại như thế này cho rõ ràng.
Chúng ta cũng sẽ cần các hàm trợ giúp có chữ ký sau:
-- Список соседей данной вершины.
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)Dễ dàng nhận thấy rằng nếu trong quá trình tìm kiếm theo chiều sâu, chúng ta tìm thấy một cạnh xung đột thì chu trình lẻ nằm trên ngăn xếp đệ quy. Vì vậy, để khôi phục nó, chúng ta cần cắt bỏ mọi thứ từ ngăn xếp đệ quy cho đến lần xuất hiện đầu tiên của đỉnh cuối cùng.
Chúng tôi triển khai tìm kiếm theo chiều sâu bằng cách duy trì một mảng kết hợp các số chia sẻ cho mỗi đỉnh. Ngăn xếp đệ quy sẽ được duy trì tự động thông qua việc triển khai lớp Functor của đơn nguyên mà chúng ta đã chọn: chúng ta sẽ chỉ cần đặt tất cả các đỉnh từ đường dẫn vào kết quả trả về từ hàm đệ quy.
Ý tưởng đầu tiên của tôi là sử dụng đơn nguyên Hoặc, nó dường như thực hiện chính xác những hiệu ứng mà chúng ta cần. Triển khai đầu tiên tôi viết rất gần với tùy chọn này. Trên thực tế, tôi đã có năm cách triển khai khác nhau tại một thời điểm và cuối cùng đã quyết định thực hiện một cách khác.
Đầu tiên, chúng ta cần duy trì một mảng liên kết các mã định danh chia sẻ - đây là điều gì đó về Trạng thái. Thứ hai, chúng ta cần có khả năng dừng lại khi phát hiện xung đột. Đây có thể là Monad cho Hoặc hoặc MonadPlus cho Có thể. Sự khác biệt chính là Hoặc có thể trả về một giá trị nếu phép tính chưa bị dừng và Có thể chỉ trả về thông tin về điều này trong trường hợp này. Vì chúng ta không cần một giá trị riêng biệt để thành công (nó đã được lưu trong State), nên chúng ta chọn Maybe. Và tại thời điểm chúng ta cần kết hợp tác dụng của hai đơn nguyên, chúng xuất hiện , kết hợp chính xác những hiệu ứng này.
Tại sao tôi lại chọn một loại phức tạp như vậy? Hai lý do. Thứ nhất, việc thực hiện hóa ra rất giống với mệnh lệnh. Thứ hai, chúng ta cần thao tác giá trị trả về trong trường hợp xung đột khi quay trở lại từ đệ quy để khôi phục vòng lặp lẻ, việc này dễ thực hiện hơn nhiều trong đơn nguyên Maybe.
Vì vậy, chúng tôi có được việc thực hiện này.
{-# 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)
Khối Where là cốt lõi của thuật toán. Tôi sẽ cố gắng giải thích những gì đang xảy ra bên trong nó.
- inVertex là một phần của tìm kiếm theo chiều sâu, nơi chúng ta truy cập đỉnh lần đầu tiên. Ở đây chúng tôi chỉ định số chia sẻ cho đỉnh và chạy onEdge trên tất cả các đỉnh lân cận. Đây cũng là nơi chúng tôi khôi phục ngăn xếp cuộc gọi: nếu msum trả về một giá trị, chúng tôi sẽ đẩy đỉnh v vào đó.
- onEdge là phần mà chúng ta truy cập vào cạnh. Nó được gọi hai lần cho mỗi cạnh. Ở đây chúng ta kiểm tra xem đỉnh ở phía bên kia đã được thăm chưa và thăm đỉnh đó nếu chưa. Nếu được truy cập, chúng tôi sẽ kiểm tra xem cạnh có xung đột hay không. Nếu đúng như vậy, chúng tôi trả về giá trị - phần trên cùng của ngăn xếp đệ quy, nơi tất cả các đỉnh khác sẽ được đặt khi trả về.
- processVertex kiểm tra từng đỉnh xem nó đã được truy cập chưa và chạy inVertex trên đó nếu chưa.
- dfs chạy processVertex trên tất cả các đỉnh.
Đó là tất cả.
Lịch sử của từ INLINE
Từ INLINE không có trong lần triển khai đầu tiên của thuật toán mà xuất hiện muộn hơn. Khi tôi đang cố gắng tìm cách triển khai tốt hơn, tôi nhận thấy rằng phiên bản không TRỰC TUYẾN chậm hơn đáng kể trên một số biểu đồ. Xét rằng về mặt ngữ nghĩa thì các hàm sẽ hoạt động giống nhau, điều này làm tôi vô cùng ngạc nhiên. Điều kỳ lạ hơn nữa là trên một máy khác có phiên bản GHC khác thì không có sự khác biệt đáng chú ý nào.
Sau khi dành một tuần để đọc kết quả đầu ra của GHC Core, tôi đã có thể khắc phục sự cố bằng một dòng INLINE rõ ràng. Tại một số thời điểm giữa GHC 8.4.4 và GHC 8.6.5, trình tối ưu hóa đã ngừng tự thực hiện việc này.
Tôi không ngờ lại gặp phải những điều bẩn thỉu như vậy trong lập trình Haskell. Tuy nhiên, ngay cả ngày nay, những người tối ưu hóa đôi khi vẫn mắc lỗi và nhiệm vụ của chúng tôi là đưa ra gợi ý cho họ. Ví dụ, ở đây chúng ta biết rằng hàm phải được nội tuyến vì nó được nội tuyến trong phiên bản mệnh lệnh và đây là lý do để đưa ra gợi ý cho trình biên dịch.
Điều gì đã xảy ra tiếp theo?
Sau đó, tôi triển khai thuật toán Hopcroft-Karp với các đơn nguyên khác và thế là chương trình kết thúc.
Nhờ Google Summer of Code, tôi đã có được kinh nghiệm thực tế về lập trình chức năng, điều này không chỉ giúp tôi có được một suất thực tập tại Phố Jane vào mùa hè năm sau (Tôi không chắc nơi này nổi tiếng đến mức nào ngay cả trong số những khán giả hiểu biết của Habr, nhưng đó là một trong những nơi trong số ít nơi bạn có thể tham gia lập trình chức năng vào mùa hè), nhưng cũng giới thiệu cho tôi thế giới tuyệt vời khi áp dụng mô hình này vào thực tế, khác biệt đáng kể so với trải nghiệm của tôi về các ngôn ngữ truyền thống.
Nguồn: www.habr.com