Bạn có thể nhận ra danh sách vô hạn trong chương trình Haskell không?

Question

thể trùng lặp:
How to tell if a list is infinite?

Trong Haskell, bạn có thể xác định một danh sách vô hạn, ví dụ [1..]. Có chức năng tích hợp trong Haskell để nhận biết danh sách có độ dài hữu hạn không? Tôi không tưởng tượng có thể viết một hàm do người dùng cung cấp để thực hiện việc này, nhưng biểu diễn bên trong các danh sách của Haskell có thể hỗ trợ nó. Nếu không có trong Haskell chuẩn, có phần mở rộng cung cấp tính năng này không?

Answer 1

Không, điều này là không thể. Sẽ không thể viết một hàm như vậy, bởi vì bạn có thể có các danh sách có độ mịn có thể chưa được biết: hãy xem xét một vòng lặp đệ quy tạo ra một danh sách tất cả các twin primes nó có thể tìm thấy. Hoặc, để theo dõi những gì Daniel Pratt đã đề cập trong phần bình luận, bạn có thể có một danh sách tất cả các bước mà universal Turing machine thực hiện trong khi thực thi, kết thúc danh sách khi máy dừng lại. Sau đó, bạn có thể chỉ cần kiểm tra xem danh sách đó có vô hạn hay không và giải quyết Halting problem!

Câu hỏi duy nhất khi triển khai Câu hỏi là danh sách có tuần hoàn hay không: nếu một trong các con trỏ đuôi trỏ trở lại ô trước của danh sách. Tuy nhiên, điều này là cụ thể cho việc triển khai thực hiện (Haskell không chỉ định bất kỳ thứ gì về cách triển khai phải đại diện cho các giá trị), không tinh khiết (các cách viết khác nhau cùng một danh sách sẽ đưa ra các câu trả lời khác nhau) và thậm chí phụ thuộc vào những thứ như danh sách bạn chuyển vào một hàm như vậy đã được đánh giá. Thậm chí sau đó, nó vẫn sẽ không thể phân biệt danh sách hữu hạn từ danh sách vô hạn trong trường hợp chung!

(Tôi đề cập đến điều này bởi vì, bằng nhiều ngôn ngữ (như thành viên của họ Lisp), danh sách vòng là chỉ loại danh sách vô hạn, không có cách nào để diễn đạt một cái gì đó như "danh sách tất cả số nguyên". vì vậy, trong những ngôn ngữ, bạn có thể kiểm tra xem một danh sách là hữu hạn hay không.)

Answer 2

không có cách nào để kiểm tra tính hữu hạn của danh sách khác hơn iterating trên danh sách để tìm kiếm thức [] trong bất kỳ thực hiện tôi biết. Và nói chung, không thể nói một danh sách là hữu hạn hay vô hạn mà không thực sự đi tìm kết thúc (điều này tất nhiên có nghĩa là mỗi khi bạn nhận được câu trả lời, điều đó đều có hạn).

Answer 3

Bạn có thể viết một loại bao bọc xung quanh danh sách mà theo dõi infiniteness, và giới hạn mình để "decidable" hoạt động chỉ (bằng cách nào đó tương tự như NonEmpty, mà tránh danh sách trống):

import Control.Applicative 

data List a = List (Maybe Int) [a] 

infiniteList (List Nothing _) = true 
infiniteList _ = false 

emptyList = List (Just 0) [] 
singletonList x = List (Just 1) [x] 
cycleList xs = List Nothing (cycle xs) 
numbersFromList n = List Nothing [n..] 
appendList (List sx xs) (List sy ys) = List ((+) <$> sx <*> sy) (xs ++ ys) 
tailList (List s xs) = List (fmap pred s) (tail xs) 
... 

Answer 4

Như ehird viết: hy vọng duy nhất của bạn là tìm ra một danh sách có theo chu kỳ hay không. Một cách làm như vậy là sử dụng phần mở rộng cho Haskell được gọi là "chia sẻ quan sát". Xem ví dụ: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4053

Answer 5

Khi nói về "đại diện nội bộ của danh sách", từ quan điểm của việc triển khai Haskell, không có danh sách vô hạn. "Danh sách" bạn hỏi về thực sự là một mô tả về quá trình tính toán, không phải là một đối tượng dữ liệu. Không có đối tượng dữ liệu nào là vô hạn bên trong máy tính. Một điều như vậy đơn giản là không tồn tại.

Như những người khác đã nói với bạn, dữ liệu danh sách nội bộ có thể theo chu kỳ và việc triển khai thường có thể phát hiện ra điều này, có khái niệm về bình đẳng con trỏ. Nhưng bản thân Haskell không có khái niệm như vậy.

Đây là hàm Lisp chung để phát hiện chu kỳ của danh sách. cdr các tiến bộ dọc theo danh sách theo một bậc và cddr - theo hai. eq là một vị từ con trỏ bình đẳng.

(defun is-cyclical (p) 
    (labels ((go (p q) 
      (if (not (null q)) 
       (if (eq p q) t 
       (go (cdr p) (cddr q)))))) 
    (go p (cdr p))))