Liệt kê tất cả các chuỗi số nguyên hữu hạn?

Question

Tôi muốn viết một danh sách Haskell để liệt kê tất cả các chuỗi hữu hạn của các số nguyên.

Tôi khá chắc chắn rằng bộ này có thể đếm được.

Đây là những gì tôi có cho đến nay:

enumIntSeqs = [ (x, [ (x, [0..x]) | x <- [ x | x <- [0..x] ] ]) | x <- [0..] ] 

Một ý tưởng tôi có là bằng cách nào đó liệt kê mọi con đường hữu hạn trong mảng vô hạn

Z * XZ * nơi Z * = {0, 1 , -1, 2, -2, ...}

Answer 1

Điều này thực sự là có thể. Nhưng điều đó không dễ chút nào. Hãy tưởng tượng bạn có một liệt kê tất cả các số nguyên, một liệt kê tất cả các cặp số nguyên, một liệt kê của tất cả ba bộ nguyên, vv. Sau đó, bạn cần phải chọn "khá" từ những liệt kê để chắc chắn để đạt từng yếu tố của mỗi. Một vấn đề tương tự sẽ xảy ra khi bạn cố gắng liệt kê tất cả các cặp số nguyên. Tôi đề nghị bạn bắt đầu với vấn đề đó, và sau đó nhìn vào một cái gì đó như Control.Monad.Omega, hoặc thậm chí có thể Control.Monad.Logic.

Answer 2

Tôi sẽ không làm hỏng niềm vui của bạn bằng cách thử câu trả lời đầy đủ, vì vậy hãy để tôi chỉ trình bày một số điều thông qua vấn đề đơn giản liệt kê tất cả các chuỗi tự nhiên hữu hạn, không trống rỗng, bắt đầu từ số không - một cái gì đó mà bạn dường như đã đạt được thành công của riêng mình rồi. Các bước quan trọng đã có trong số enumIntSeqs của bạn, nhưng bạn không phải lồng ghép danh sách như thế. Nếu bạn bắt đầu với ...

[ {- etc. -} | x <- [0..] ] 

... bạn có thể tạo một danh sách mới cho mỗi x chỉ đơn giản bằng cách làm ...

[ {- etc. -} | x <- [0..], let ys = [0..x] ] 

... và sau đó quay trở lại những danh sách:

[ ys | x <- [0..], let ys = [0..x] ] 

(Lưu ý rằng tôi đã không viết ys <- [0..x]. Cố gắng dự đoán những gì sẽ xảy ra trong trường hợp đó, và sau đó kiểm tra xem nó trong GHCi.)

Các định nghĩa riêng biệt let là không cần thiết, cũng không thêm bất cứ điều gì về sự rõ ràng trong sự hiểu biết đơn giản này, vì vậy chúng tôi chỉ có thể viết:

[ [0..x] | x <- [0..] ] 

Và đó là nó.

Prelude> take 4 $ [ [0..x] | x <- [0..] ] 
[[0],[0,1],[0,1,2],[0,1,2,3]] 

P.S .: Hai cách viết khác của liệt kê. Sử dụng làm-ký hiệu ...

someIntSeqs = do 
    x <- [0..] 
    return [0..x] 

... và với một khiêm tốn fmap (mà trong trường hợp này cũng giống như map):

Prelude> take 4 $ fmap (\x -> [0..x]) [0..] 
[[0],[0,1],[0,1,2],[0,1,2,3]] 
Prelude> -- Or, equivalently... 
Prelude> take 4 $ (\x -> [0..x]) <$> [0..] 
[[0],[0,1],[0,1,2],[0,1,2,3]]