Sản phẩm được lồng ghép của danh sách Haskell

Question

Tôi muốn tạo một phương pháp để tôi có thể cung cấp cho nó một danh sách độ dài và nó sẽ trả về tất cả các kết hợp của tọa độ Descartes cho đến độ dài đó. Giải thích dễ dàng hơn với ví dụ:

cart [2,5] 
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ] 

cart [2,2,2] 
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ] 

Việc hiểu danh sách đơn giản sẽ không hiệu quả vì tôi không biết danh sách sẽ dài bao lâu. Trong khi tôi yêu sự đơn giản của Haskell đối với nhiều vấn đề, đây là một trong những điều mà tôi có thể viết procedurally (trong C hoặc một cái gì đó) trong 5 phút trong khi Haskell cho tôi một chứng phình động mạch!

Một giải pháp cho vấn đề cụ thể này sẽ giúp tôi rất nhiều; Tôi cũng thích nghe về quá trình suy nghĩ của bạn khi giải quyết những thứ như thế này.

Answer 1

Điều này có thể được giải quyết đệ quy. Thứ nhất, Cartesian product of nothing là {∅}:

cart [] = [[]] 

(Hoặc xác định chỉ là hình thức 1 phần tử nếu sản phẩm có sản phẩm nào là không hợp lệ:

cart [x] = [[i] | i <- [0 .. x-1]] 

)

Sau đó, sản phẩm Descartes của x:xs có thể được viết là

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs] 

---

Nói chung, nếu bạn biết những gì để viết một hàm f đòi hỏi chiều dài của danh sách N, cố gắng nghĩ ra một cách để làm cho f (N) phụ thuộc vào danh sách nhỏ hơn ví dụ f (N - 1) chỉ, sau đó giải quyết trường hợp cơ bản f (0) hoặc f (1) vv Điều này biến vấn đề thành đệ quy có thể dễ dàng được giải quyết.

Answer 2

Tôi đặt cược giải pháp thủ tục của bạn sẽ liên quan đến đệ quy. Giải pháp Haskell của chúng tôi cũng sẽ liên quan đến đệ quy.

Vì vậy, đệ quy. Đầu tiên là trường hợp đệ quy.

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart] 
    where rcart = cart cs 

Ở đây chúng tôi chỉ nói rằng đối với mỗi ban đầu phối hợp có thể, và mỗi sự kết hợp có thể có của Descartes tọa độ từ độ dài còn lại, chúng tôi làm điều hiển nhiên của việc kết hợp các phối hợp với phần còn lại phối hợp.

Sau đó, vỏ cơ sở.

cart [] = [[]] 

Bạn có thể nghĩ cart [] = []. Tôi đã làm lúc đầu. Nhưng hãy nghĩ về trường hợp đệ quy yêu cầu từ trường hợp cơ bản.

Answer 3

Umm ..

cart = sequence . map (enumFromTo 0 . subtract 1) 

Đó là hợp lý để hy vọng rằng một hàm [[a]] -> [[a]] làm những gì chúng tôi mong đợi đã tồn tại trong thư viện. Vì vậy, nếu một người không quen thuộc với sequence, việc tìm kiếm nó là một vấn đề đơn giản của hoogling nó.

Edit: như newacct chỉ ra:

cart = mapM (enumFromTo 0 . subtract 1) 

này cũng có thể được tìm thấy bằng cách ăn các giải pháp trước để HLint.