Khả năng phát hiện danh sách tuần hoàn trong Haskell có phá vỡ bất kỳ thuộc tính nào của ngôn ngữ không?

Question

Trong Haskell, một số danh sách là cyclic:

ones = 1 : ones 

Những người khác không:

nums = [1..] 

Và sau đó có những điều như thế này:

more_ones = f 1 where f x = x : f x 

này biểu thị giá trị tương tự như ones và chắc chắn giá trị đó là một chuỗi lặp lại. Nhưng cho dù nó được thể hiện trong bộ nhớ như là một cấu trúc dữ liệu tuần hoàn là nghi ngờ. (An thực hiện có thể làm như vậy, nhưng this answer explains that "it's unlikely that this will happen in practice".)

Giả sử chúng ta hãy thực hiện Haskell và hack vào nó một built-in chức năng isCycle :: [a] -> Bool để quan sát cấu trúc của đại diện trong bộ nhớ của đối số. Nó trả về True nếu danh sách là theo chu kỳ vật lý và False nếu đối số có độ dài hữu hạn. Nếu không, nó sẽ không chấm dứt. (Tôi tưởng tượng "hack nó trong" vì nó không thể viết chức năng đó trong Haskell.)

Sự tồn tại của chức năng này có phá vỡ bất kỳ thuộc tính thú vị nào của ngôn ngữ không?

Answer 1

Sự tồn tại của hàm này có phá vỡ bất kỳ thuộc tính thú vị nào của ngôn ngữ không?

Có. Nó sẽ phá vỡ referential transparency (xem thêm the Wikipedia article). Biểu thức Haskell có thể luôn được thay thế bằng giá trị của nó. Nói cách khác, nó chỉ phụ thuộc vào các đối số đã qua và không có gì khác. Nếu chúng tôi có

isCycle :: [a] -> Bool 

như bạn đề xuất, các biểu thức sử dụng sẽ không thỏa mãn bất động sản này nữa. Chúng có thể phụ thuộc vào biểu diễn bộ nhớ trong của các giá trị. Do đó, các luật khác sẽ bị vi phạm. Ví dụ identity law cho Functor

fmap id === id 

sẽ không nắm giữ bất kỳ hơn: Bạn sẽ có thể phân biệt giữa ones và fmap id ones, vì sau đó sẽ là mạch hở. Và tối ưu hóa trình biên dịch như áp dụng luật trên sẽ không còn giữ lại thuộc tính chương trình nữa.

Tuy nhiên một câu hỏi khác sẽ có chức năng

isCycleIO :: [a] -> IO Bool 

như IO hành động được cho phép để kiểm tra và thay đổi bất cứ điều gì.

Một giải pháp thuần túy có thể là để có một kiểu dữ liệu mà trong nội bộ phân biệt hai:

import qualified Data.Foldable as F 

data SmartList a = Cyclic [a] | Acyclic [a] 

instance Functor SmartList where 
    fmap f (Cyclic xs) = Cyclic (map f xs) 
    fmap f (Acyclic xs) = Acyclic (map f xs) 

instance F.Foldable SmartList where 
    foldr f z (Acyclic xs) = F.foldr f z xs 
    foldr f _ (Cyclic xs) = let r = F.foldr f r xs in r 

Tất nhiên nó sẽ không thể nhận ra nếu một danh sách chung là cyclic hay không, nhưng đối với nhiều hoạt động có thể bảo toàn kiến ​​thức về việc có các giá trị Cyclic.

Answer 2

Trong trường hợp chung, không bạn không thể xác định danh sách vòng tuần hoàn. Tuy nhiên nếu danh sách đang được tạo ra bởi một hoạt động mở ra sau đó bạn có thể. Data.List chứa nội dung này:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

Đối số đầu tiên là hàm lấy đối số "trạng thái" loại "b" và có thể trả về phần tử của danh sách và trạng thái mới. Đối số thứ hai là trạng thái ban đầu. "Không có gì" có nghĩa là danh sách kết thúc.

Nếu trạng thái bao giờ tái diễn thì danh sách sẽ lặp lại từ thời điểm trạng thái cuối cùng. Vì vậy, nếu thay vào đó chúng ta sử dụng một hàm khác được mở ra để trả về một danh sách các cặp (a, b), chúng ta có thể kiểm tra trạng thái tương ứng với mỗi phần tử. Nếu cùng một trạng thái được nhìn thấy hai lần thì danh sách là tuần hoàn. Tất nhiên điều này giả định rằng nhà nước là một ví dụ của Eq hoặc một cái gì đó.