Haskell: Sở hữu chung Corecursive sai lầm

Question

Vì vậy, tôi đã suy nghĩ về một thuật toán đồ thị khoảng cách tối nay, và đã đưa ra này trong khi tôi đang lái xe trong xe:

module GraphDistance where 
import Data.Map 

distance :: (Ord a) => a -> Map a [a] -> Map a Int 
distance a m = m' 
    where m' = mapWithKey d m 
     d a' as = if a == a' then 0 else 1 + minimum (Prelude.map (m'!) as) 

Lúc đầu, tôi đã khá tự hào về bản thân mình, vì nó có vẻ rất tao nhã. Nhưng sau đó tôi nhận ra nó sẽ không hoạt động - corecursion có thể gặp khó khăn trong một vòng lặp.

tôi phải mã hóa nó lên để thuyết phục bản thân mình:

ghci> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])] 
fromList [(0,1),(1,0),(2,^CInterrupted. 

Nhưng bây giờ tôi nghĩ rằng tôi đã khá nhiều nghĩ rằng nó thông qua.

Có danh sách các lỗi phổ biến và chống mẫu khi xử lý dữ liệu corecursive mà tôi có thể đọc lên trên, để tôi có thể rèn luyện não của mình để suy nghĩ một cách corecursively? Kinh nghiệm đã đào tạo tôi khá tốt cho việc suy nghĩ thông qua dữ liệu không mang tính corecursive , nhưng tôi muốn học hỏi từ những sai lầm khác nếu tôi có thể.

Answer 1

Vâng, thực sự chỉ có một sai lầm cơ bản khi xử lý dữ liệu corecursive, và đó là bất cẩn bằng cách sử dụng đệ quy trên nó!

Corecursion ngụ ý rằng dữ liệu đang được tạo tăng dần theo một nghĩa nào đó. Hàm khoảng cách biểu đồ của bạn là hướng dẫn ở đây, vì có vẻ như nó nên hoạt động, vì vậy hãy nghĩ về nơi phần gia tăng phải là: Điểm bắt đầu là khoảng cách 0 từ nút đến chính nó, nếu không lớn hơn khoảng cách tối thiểu trong láng giềng ngay lập tức của riêng mình. Do đó, chúng tôi mong đợi mỗi giá trị khoảng cách sẽ tăng dần, có nghĩa là chúng tôi cần chúng phải được tự phân tích phù hợp.

Các đệ quy tại vấn đề, sau đó, đang diễn ra do sự kết hợp của (+) và minimum: khi tìm kiếm tối thiểu, 1 sẽ luôn luôn được ít hơn 1 + n, mà không cần phải lo lắng về những gì n là ... nhưng không có cách nào để so sánh Int giây mà không tính toán toàn bộ giá trị.

Tóm lại, thuật toán hy vọng có thể so sánh số lần (1 +) được áp dụng cho 0 chỉ khi cần thiết; đó là để nói, nó muốn số tự nhiên lười biếng được xác định bằng cách sử dụng "số không" và "người kế nhiệm".

Kìa:

data Nat = Z | S Nat 

natToInt :: Nat -> Int 
natToInt Z = 0 
natToInt (S n) = 1 + natToInt n 

instance Show Nat where show = show . natToInt 

instance Eq Nat where 
    Z == Z = True 
    (S n1) == (S n2) = n1 == n2 
    _ == _ = False 

    Z /= Z = False 
    (S n1) /= (S n2) = n1 /= n2 
    _ /= _ = True 


instance Ord Nat where 
    compare Z Z = EQ 
    compare Z (S _) = LT 
    compare (S _) Z = GT 
    compare (S n1) (S n2) = compare n1 n2 

Và sau đó trong GHCi:

> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])] 
fromList [(0,1),(1,0),(2,1),(3,2)] 

Proof rằng thuật toán của bạn hoạt động ^[0]; việc bạn triển khai nó chỉ là không chính xác.

---

Bây giờ, khi sự thay đổi nhỏ, chúng ta hãy áp dụng thuật toán của bạn để một đồ thị khác nhau:

> distance 1 $ fromList [(0,[1]),(1,[0]),(2,[3]),(3,[2])] 

... làm những gì chúng tôi mong đợi điều này để làm gì? Khoảng cách từ nút 1 cho các nút 2 hoặc 3 là bao nhiêu?

Chạy nó trong GHCi có kết quả rõ ràng:

fromList [(0,1),(1,0),(2,^CInterrupted. 

Tuy nhiên, thuật toán hoạt động chính xác trên biểu đồ này. Bạn có thấy vấn đề không? Tại sao nó treo trong GHCi?

---

Nói tóm lại, bạn cần phải phân biệt rõ ràng giữa hai hình thức mà không thể được trộn lẫn một cách tự do:

• Lazy, dữ liệu có thể là vô hạn, tạo ra corecursively
• dữ liệu hữu hạn, tiêu thụ một cách đệ quy

Cả hai biểu mẫu đều có thể được chuyển đổi theo cách không cấu trúc (ví dụ: map hoạt động trên danh sách hữu hạn và vô hạn cả hai). Codata có thể được tiêu thụ dần dần, được thúc đẩy bởi một thuật toán corecursive; dữ liệu có thể được tạo đệ quy, bị hạn chế bởi một thuật toán đệ quy.

Những gì bạn không thể làm sử dụng mã đệ quy đệ quy (ví dụ, gấp bên trái danh sách vô hạn) hoặc tạo dữ liệu corecursively (hiếm trong Haskell, do lười biếng).

[0]: Thực tế, nó sẽ không thành công trên một số yếu tố đầu vào (ví dụ: một số đồ thị bị ngắt kết nối), nhưng đó là một vấn đề khác.