Haskell, xác định danh sách vô hạn, thêm dữ liệu khi đang di chuyển và sắp xếp cùng một lúc. Làm sao?

Question

tôi phải xác định một danh sách trong đó:

• 1 là thành viên
• nếu n là thành viên, vì vậy là 2n + 1 và 3n + 1

Vì vậy, danh sách là vô hạn và phải được sắp xếp. Khi nạp vào GHCi, lệnh:

"take 10 theList" 

sẽ sản xuất:

[1,3,4,7,9,10,13,15,19,21] 

Dưới đây là mã của tôi:

theList = ([1] ++ concat [[(x*2+1),(x*3+1)]|x<-theList]) 

Có vẻ như để làm việc trừ rằng nó không phải được sắp xếp, các cùng một lệnh như trên tạo ra:

[1,3,4,7,10,9,13,15,22,21] 

Có ai có ý tưởng nào để phân loại nó không? Cảm ơn

Answer 1

Vấn đề có thể mặc dù như một cây nhị phân vô hạn (A và B là nhãn cho các chi nhánh):

1__ B 
    | 4___ 
    | \ 13 ... 
A 3_ \ 
    | \ 9 ... 
    7 10 
    ... 

Suy nghĩ về nó theo cách này, chúng ta có thể thấy rằng chúng tôi muốn viết một chức năng ("listify") chuyển đổi "cây" thành danh sách được sắp xếp. Đây là nơi Haskell thực sự tốt đẹp: nếu chúng ta có một hàm (merge) cần hai danh sách được sắp xếp (vô hạn) và gộp chúng thành một danh sách được sắp xếp (bạn nên viết hàm này), sau đó listify -ing cây đơn giản là listify -ing hai chi nhánh, sáp nhập chúng và đặt gốc vào lúc bắt đầu, tức là trong cây trên

1:merge (listify A) (listify B) 

Vì đây là bài tập về nhà tôi sẽ không nói nhiều hơn, nhưng bất kỳ nhánh cây nào đều được xác định hoàn toàn bởi gốc nút, do đó, chữ ký loại listify có thể là Integer -> [Integer]. Và khi bạn có listify, thì theList = listify 1.

Answer 2

Một cách khác để xem đây là danh sách các số nguyên được lọc. Số n là một phần của chuỗi nếu n = 1 (mod 2) và (n-1)/2 là một phần của chuỗi, hoặc nếu n = 1 (mod 3) và (n-1)/3 là một một phần của chuỗi.