match được định nghĩa trong kiểu chữ Graph, vì vậy việc triển khai hàm đó phụ thuộc vào kiểu dữ liệu thực hiện typeclass.
Các gói phần mềm đi kèm với hai triển khai, one using Patricia trees, one using regular trees. Bạn có thể xem nguồn cho chính mình.
Ví dụ, cây Patricia thực hiện:
import Data.Graph.Inductive.Graph
import Data.IntMap (IntMap)
import qualified Data.IntMap as IM
import Data.List
import Data.Maybe
import Control.Arrow(second)
newtype Gr a b = Gr (GraphRep a b)
type GraphRep a b = IntMap (Context' a b)
type Context' a b = (IntMap [b], a, IntMap [b])
type UGr = Gr()()
instance Graph Gr where
-- ...
match = matchGr
-- ...
matchGr :: Node -> Gr a b -> Decomp Gr a b
matchGr node (Gr g)
= case IM.lookup node g of
Nothing
-> (Nothing, Gr g)
Just (p, label, s)
-> let !g1 = IM.delete node g
!p' = IM.delete node p
!s' = IM.delete node s
!g2 = clearPred g1 node (IM.keys s')
!g3 = clearSucc g2 node (IM.keys p')
in
(Just (toAdj p', node, label, toAdj s), Gr g3)
lookup and delete on IntMaps have O(min(n,W)) runtime, đó là một cách hiệu quả liên tục trên máy tính, có chiều rộng bộ số nguyên (W).
Vì vậy, đó chỉ là lá clearPred, clearSucc, và toAdj:
clearSucc :: GraphRep a b -> Node -> [Node] -> GraphRep a b
clearSucc g _ [] = g
clearSucc g v (p:rest) = clearSucc g' v rest
where
g' = IM.adjust f p g
f (ps, l, ss) = (ps, l, IM.delete v ss)
clearPred :: GraphRep a b -> Node -> [Node] -> GraphRep a b
clearPred g _ [] = g
clearPred g v (s:rest) = clearPred g' v rest
where
g' = IM.adjust f s g
f (ps, l, ss) = (IM.delete v ps, l, ss)
adjust cũng là O(min(n,W)), vì vậy chúng tôi không cần phải lo lắng về điều đó. Cả hai clearSucc và clearPred recurse thông qua mỗi yếu tố trong danh sách kề, mặc dù, do đó, đó là O (độ) kết hợp.
toAdj :: IntMap [b] -> Adj b
toAdj = concatMap expand . IM.toList
where
expand (n,ls) = map (flip (,) n) ls
toAdj tạo ra một danh sách cạnh mới, đó là O (max (| V |, | E |)), nhưng điều này được xây dựng một cách lười biếng, vì vậy chúng tôi không cần phải lo lắng về vấn đề này trừ khi nó được sử dụng.
Tổng quan cấp độ rất cao - hầu hết công việc trong hàm 'match' để triển khai biểu đồ phổ biến nhất sử dụng hàm' lookup' từ mô-đun 'IntMap'. Đây là 'O (min (n, W))' trong đó 'n' là số phần tử trong bản đồ và' W' là kích thước theo bit của một int (thường là 32 hoặc 64). Vì vậy, tra cứu là tuyến tính trong n, tối đa là n = 32 hoặc n = 64, sau đó là hằng số - đặc biệt, nó là tiệm cận O (1). –