Tôi chỉ giữ bộ được truy cập làm nhóm và chuyển nó làm tham số. Có hiệu quả thời gian đăng nhập thực hiện của bộ của bất kỳ loại lệnh và bộ hiệu quả thêm các số nguyên.
Để đại diện cho biểu đồ, tôi sử dụng danh sách kề, hoặc tôi sẽ sử dụng bản đồ hữu hạn ánh xạ từng nút đến danh sách người kế thừa của nó. Nó phụ thuộc vào những gì tôi muốn làm.
Thay vì Abelson và Sussman, tôi khuyên bạn nên sử dụng số Purely Functional Data Structures của Chris Okasaki. Tôi đã liên kết với luận án của Chris, nhưng nếu bạn có tiền, anh ta mở rộng nó thành một excellent book.
Chỉ dành cho nụ cười, đây là một tìm kiếm theo chiều sâu đầu tiên tìm kiếm theo chiều ngược lại đáng sợ được thực hiện theo kiểu chuyển tiếp liên tục trong Haskell. Đây là ngay từ thư viện trình tối ưu hóa Hoopl:
postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e)
=> LabelMap (block C C) -> e -> LabelSet -> [block C C]
postorder_dfs_from_except blocks b visited =
vchildren (get_children b) (\acc _visited -> acc) [] visited
where
vnode :: block C C -> ([block C C] -> LabelSet -> a)
-> ([block C C] -> LabelSet -> a)
vnode block cont acc visited =
if setMember id visited then
cont acc visited
else
let cont' acc visited = cont (block:acc) visited in
vchildren (get_children block) cont' acc (setInsert id visited)
where id = entryLabel block
vchildren bs cont acc visited = next bs acc visited
where next children acc visited =
case children of [] -> cont acc visited
(b:bs) -> vnode b (next bs) acc visited
get_children block = foldr add_id [] $ targetLabels bloc
add_id id rst = case lookupFact id blocks of
Just b -> b : rst
Nothing -> rst
Nguồn
2010-06-08 22:58:32
Tôi đã lấy các liên kết này từ trang thư viện đồ thị chức năng: Điều này giải thích lý thuyết: http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01 Tài liệu này lập chi tiết chương trình: http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf Cùng với nhau, những giấy tờ này trả lời tốt nhất câu hỏi của tôi, đặc biệt là câu hỏi thứ hai, thực tế hơn một chút. Cảm ơn! – brad