Danh sách vô hạn các quầy vô hạn

Question

Đối với những người có tâm trí đáng ngờ, đây không phải là bài tập về nhà, chỉ tò mò thôi.

Với một bảng chữ cái hữu hạn, có thể xây dựng một danh sách các từ dài vô hạn được làm từ bảng chữ cái theo thứ tự ngược lại không?

ví dụ cho bảng chữ cái "ab"

là nó có thể để xây dựng danh sách:

["aaaaaa...", "baaaaa...", "abaaaa...", "bbaaaa...", "aabaaa...", ...] 

nơi ... đại diện cho danh sách (và danh sách liệt kê) kéo dài đến chiều dài vô hạn.

Một nỗ lực ngây thơ là:

counters alphabet = [c:ounter | ounter <- counters alphabet, c <- alphabet] 

nhưng điều này không làm việc kể từ khi nó bị bỏ đệ quy. Tất nhiên, với một phiên bản làm việc, nếu bạn cố in kết quả, bạn sẽ chỉ thấy phần tử đầu tiên được in dưới dạng danh sách vô hạn của phần tử đầu tiên từ bảng chữ cái. Tuy nhiên, bạn sẽ có thể làm điều này:

mapM_ (print . take 2) . take 4 . counters $ "ab" 

và xem kết quả:

aa 
ba 
ab 
bb 

Answer 1

Tại sao không fix?

ghci> let bar = let foo ~(st:sts) = [c:st | c <- "ab"] ++ foo sts in fix foo 
ghci> take 5 . map (take 5) $ bar 
["aaaaa","baaaa","abaaa","bbaaa","aabaa"] 
take 10 . map (take 5) $ bar 
["aaaaa","baaaa","abaaa","bbaaa","aabaa","babaa","abbaa","bbbaa","aaaba","baaba"] 

Answer 2

Có lẽ không phải là giải pháp hiệu quả nhất, nhưng ít nhất nó hoạt động:

counters alphabet = map f [0..] 
    where f n = let (q, r) = quotRem n (length alphabet) in alphabet !! r : f q 

> take 10 $ map (take 5) $ counters "ab" 
["aaaaa","baaaa","abaaa","bbaaa","aabaa","babaa","abbaa","bbbaa","aaaba","baaba"] 

Answer 3

Tiến trình trông giống như mã hóa số cơ sở-N với số lần đào ít quan trọng nhất nó ở bên trái, vì vậy chúng ta có thể tiếp cận nó như

1. Thực hiện một "căn N" chức năng sử dụng fbảng chữ cái của bạn như các chữ cái.
2. mapf đến [0..]
3. Thêm repeat $ head alphabets vào từng phần tử trong danh sách.

Answer 4

Bạn có thể tìm ra phương pháp sau đây gây cười/khó hiểu:

duplicates s ss = cycle ss : duplicates s (ss >>= \c -> s >> [c]) 
counters = transpose . join duplicates 

này xuất phát từ quan sát rằng các chữ cái đầu tiên theo mô hình "ababab...", các chữ cái thứ hai theo mô hình "aabbaabbaabb...", các chữ cái thứ ba theo mẫu "aaaabbbbaaaabbbb...", v.v.

Answer 5

Điều này thì sao?

f@(a:as) = a:('b':a):concatMap (\x -> ['a':x,'b':x]) as where a = ['a','a'..] 

Cũng (\x -> ['a':x,'b':x]) thể được viết bằng Applicative như ([('a':),('b':)] <*>) . pure nếu bạn coi nó là tao nhã hơn.

Answer 6

Tuy nhiên, một phiên bản dựa trên ý tưởng của Daniel:

counters = transpose $ map cycle $ iterate (>>= \x -> [x,x]) "ab"