Có cách ngây thơ của cố nó, trông như thế này:
route :: Graph -> Label -> Label -> Bool
route g dest from | from == dest = True
route g dest from = any (route g dest) (neighbours g from)
Nhưng thất bại tại vòng lặp đồ thị. (Tôi cũng giả sử bạn có hàng xóm được xác định)
Vì vậy, phải làm gì nhưng chuyển danh sách các nút đã xem qua.
route2 :: Graph -> Label -> Label -> [Label] -> Bool
route2 g dest from seen
| dest == from = True
| otherwise = any (\x -> route2 g dest x (from:seen)) (neighbours g from)
Nhưng nếu bạn đang chạy nó trên đồ thị ở đây:. Bạn sẽ nhận được một dấu vết mà nhìn một cái gì đó như thế này (xin lỗi chương trình này, tôi đã không biết xấu hổ bị đánh cắp những bức ảnh này từ lớp cs tôi fr là find-route, và fr-l là phiên bản của nó có danh sách. Tham số thứ hai là bộ tích lũy)
Như bạn có thể thấy, nó kết thúc bằng cách truy cập các nút K và H hai lần. Điều này là xấu, cho phép xem tại sao nó làm điều đó.
Vì nó không vượt qua bất kỳ thông tin sao lưu từ các cuộc gọi đệ quy trong any
, nó không thể nhìn thấy những gì nó đã làm trong ngành thất bại, chỉ có những gì đã được trên đường dẫn đến nút hiện tại.
Bây giờ để khắc phục điều đó, có hai đường dẫn mà chúng tôi có thể thực hiện. Lớp học của tôi đã tiếp cận một cách tiếp tục đi qua khá là mới lạ, vì vậy tôi sẽ trình bày nó trước, trước phiên bản đơn điệu của tiểu bang.
routeC :: Graph -> Label -> Label -> [Label] -> ([Label] -> Bool) -> Bool
routeC g dest from seen k
| dest == from = True
| from `elem` seen = k (from:seen)
| otherwise = routeCl g dest (neighbours g from) (from:seen) k
routeCl :: Graph -> Label -> [Label] -> [Label] -> ([Label] -> Bool) -> Bool
routeCl g dest [] seen k = k seen
routeCl g dest (x:xs) seen k =
routeC g dest x seen (\newSeen -> routeCl g dest xs newSeen k)
Điều này sử dụng một cặp hàm, thay vì bất kỳ chức năng nào. routeC
chỉ cần kiểm tra xem chúng tôi có đến đích hay nếu chúng tôi đã lặp lại, nếu không nó chỉ gọi tuyến đườngCL với những người hàng xóm của nút hiện tại.
Nếu chúng tôi đã lặp, thay vì chỉ trả lại False
, chúng tôi gọi là tiếp tục, nhưng với các nút mà chúng tôi hiện đang nhìn thấy (bao gồm cả nút hiện tại).
routeCL
lấy danh sách các nút và nếu danh sách trống, hãy chạy phần tiếp theo, nếu không nó sẽ làm điều gì đó thú vị. Nó chạy routeC
trên nút đầu tiên, và chuyển nó một sự tiếp tục sẽ chạy routeCl
trên phần còn lại của danh sách, với danh sách MỚI của các nút đã thấy. Vì vậy, nó sẽ có thể nhìn thấy vào lịch sử của các chi nhánh thất bại.
(Thêm vào đó, chúng ta có thể khái quát hóa nó thêm một chút, và biến đổi nó thành kiểu chuyển tiếp tiếp tục. chữ ký là điều kinh hoàng hơn mã.)
anyK :: (a -> s -> (s -> r) -> (s -> r) -> r) ->
[a] -> s -> (s -> r) -> (s -> r) -> r
anyK p [] s tK fK = fK s
anyK p (x:xs) s tK fK = p x s tK (\s' -> anyK p xs s' tK fK)
routeK2 :: Graph -> Label -> Label -> ([Label] -> r) -> ([Label] -> r) -> r
routeK2 g dest from' trueK falseK = route from' [] trueK falseK
where route from seen tK fK
| from == dest = tK seen
| from `elem` seen = fK seen
| otherwise = anyK route (neighbours g from) (from:seen) tK fK
điều tương tự, nhưng với nhiều thông tin được thông qua tại.
Bây giờ, cho những gì bạn đã chờ đợi, phiên bản đơn nguyên nhà nước.
routeS :: Graph -> Label -> Label -> State [Label] Bool
routeS g dest from | dest == from = return True
routeS g dest from = do
seen <- get
if from `elem` seen then return False else do
put (from:seen)
anyM (routeS g dest) (neighbours g from)
Nhưng không phải dòng cuối cùng trông giống như những gì chúng tôi bắt đầu, chỉ với một số đường ống dẫn thêm? So sánh:
any (route g dest) (neighbours g from) -- Simple version
anyM (routeS g dest) (neighbours g from) -- State Version
anyK route (neighbours g from) (from:seen) tK fK -- CPS version
Ở cốt lõi, cả ba đều làm tương tự. Các monad trong phiên bản nhà nước chỉ độc đáo xử lý các hệ thống ống nước của các nút nhìn thấy cho chúng tôi.Và phiên bản CPS cho chúng ta thấy chính xác dòng chảy của kiểm soát sẽ như thế nào, trong một thời trang rõ ràng hơn nhiều so với đơn nguyên của tiểu bang.
Ồ, nhưng anyM
dường như không nằm trong thư viện chuẩn. Dưới đây là hình thức:
anyM :: (Monad m) => (a -> m Bool) -> [a] -> m Bool
anyM p [] = return False
anyM p (x:xs) = do
y <- p x
if y
then return True
else anyM p xs
@Daniel Cảm ơn bạn đã chú ý loại ... chỉ cần nhập mà không cần cắt từ các emac và dán vào đây. (^. ^) –