Sản phẩm Descartes của 2 danh sách trong Haskell

Question

Tôi muốn sản xuất sản phẩm Descartes của 2 danh sách trong Haskell, nhưng tôi không thể tìm ra cách để thực hiện nó. Các sản phẩm Descartes cho tất cả các kết hợp của các yếu tố danh sách:

xs = [1,2,3] 
ys = [4,5,6] 

cartProd :: [a] -> [b] -> [(a,b)] 
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)] 

Đây không phải là một câu hỏi bài tập về nhà thực tế và không liên quan đến bất kỳ câu hỏi như vậy, nhưng cách thức mà vấn đề này được giải quyết có thể giúp với một Tôi bị mắc kẹt trên.

Answer 1

Điều này rất dễ dàng với việc hiểu danh sách. Để có được sản phẩm Descartes của các danh sách xs và ys, chúng tôi chỉ cần lấy bộ số (x,y) cho mỗi thành phần x trong xs và mỗi thành phần y trong ys.

này mang lại cho chúng tôi danh sách hiểu biết sau đây:

cartProd xs ys = [(x,y) | x <- xs, y <- ys] 

Answer 2

Vâng, một cách rất dễ dàng để làm được điều này sẽ có comprehensions danh sách:

cartProd :: [a] -> [b] -> [(a, b)] 
cartProd xs ys = [(x, y) | x <- xs, y <- ys] 

Mà tôi nghĩ là làm thế nào tôi sẽ làm điều này , mặc dù tôi không phải là chuyên gia Haskell (bằng bất kỳ phương tiện nào).

Answer 3

cái gì đó như:

cartProd x y = [(a,b) | a <- x, b <- y] 

Answer 4

Cách đúng là sử dụng comprehensions danh sách, như những người khác đã chỉ ra, nhưng nếu bạn muốn làm điều đó mà không sử dụng comprehensions danh sách vì lý do bất kỳ, sau đó bạn có thể làm điều này :

cartProd :: [a] -> [b] -> [(a,b)] 
cartProd xs [] = [] 
cartProd [] ys = [] 
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys 

Answer 5

Như các câu trả lời khác đã lưu ý, sử dụng danh sách hiểu là cách tự nhiên nhất để thực hiện việc này trong Haskell.

Nếu bạn đang học Haskell và muốn làm việc về phát triển trực giác về các lớp học kiểu như Monad, tuy nhiên, đó là một bài tập thú vị để tìm ra lý do tại sao định nghĩa hơi ngắn hơn đây là tương đương:

import Control.Monad (liftM2) 

cartProd :: [a] -> [b] -> [(a, b)] 
cartProd = liftM2 (,) 

Có thể bạn wouldn không bao giờ muốn viết điều này trong mã thực, nhưng ý tưởng cơ bản là thứ bạn sẽ thấy trong Haskell mọi lúc: chúng tôi đang sử dụng liftM2 để nâng chức năng không đơn điệu (,) thành một đơn vị — trong trường hợp này cụ thể là danh sách đơn nguyên.

Nếu điều này không có ý nghĩa hoặc không hữu ích, hãy quên nó — đó chỉ là một cách khác để xem xét vấn đề.

Answer 6

Nếu danh sách đầu vào của bạn cùng loại, bạn có thể nhận được sản phẩm Descartes của một số danh sách tùy ý bằng cách sử dụng sequence (sử dụng List đơn nguyên).Điều này sẽ giúp bạn có được một danh sách liệt kê thay vì một danh sách các hàng:

> sequence [[1,2,3],[4,5,6]] 
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]] 

Answer 7

Tuy nhiên, một cách khác, bằng cách sử dụng do ký hiệu:

cartProd :: [a] -> [b] -> [(a,b)] 
cartProd xs ys = do x <- xs 
        y <- ys 
        return (x,y) 

Answer 8

Tuy nhiên, một cách khác để thực hiện điều này là sử dụng applicatives:

import Control.Applicative 

cartProd :: [a] -> [b] -> [(a,b)] 
cartProd xs ys = (,) <$> xs <*> ys 

Answer 9

Có một cách rất thanh lịch để thực hiện việc này với Functors áp dụng:

import Control.Applicative 

(,) <$> [1,2,3] <*> [4,5,6] 
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)] 

Ý tưởng cơ bản là áp dụng hàm trên đối số "được bao bọc", ví dụ:

(+) <$> (Just 4) <*> (Just 10) 
-- Just 14 

Trong trường hợp danh mục, các chức năng sẽ được áp dụng cho tất cả các kết hợp, vì vậy tất cả bạn phải làm là để "tuple" chúng với (,).

Xem http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors hoặc (lý thuyết hơn) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf để biết chi tiết.

Answer 10

Đây là triển khai thực hiện của tôi về sản phẩm Descartes n-ary:

crossProduct :: [[a]] -> [[a]] 
crossProduct (axis:[]) = [ [v] | v <- axis ] 
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ] 

Answer 11

Đó là một công việc cho sequence ing. Một thực hiện monadic của nó có thể là:

cartesian :: [[a]] -> [[a]] 
cartesian [] = return [] 
cartesian (x:xs) = x >>= \x' -> cartesian xs >>= \xs' -> return (x':xs') 

*Main> cartesian [[1,2,3],[4,5,6]] 
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]] 

Như bạn có thể nhận thấy, các giống trên việc thực hiện map bởi các chức năng tinh khiết nhưng trong loại monadic. Theo đó bạn có thể đơn giản hóa nó xuống

cartesian :: [[a]] -> [[a]] 
cartesian = mapM id 

*Main> cartesian [[1,2,3],[4,5,6]] 
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]] 

Answer 12

Câu trả lời khác giả định rằng hai danh sách đầu vào là hữu hạn. Thông thường, mã Haskell thành ngữ bao gồm danh sách vô hạn, và do đó, nó là đáng giá bình luận một thời gian ngắn về cách sản xuất một sản phẩm Cartesian vô hạn trong trường hợp đó là cần thiết.

Cách tiếp cận tiêu chuẩn là sử dụng chéo; bằng văn bản cho một đầu vào dọc theo phía trên và các đầu vào khác dọc bên trái, chúng ta có thể viết một bảng hai chiều có chứa sản phẩm Descartes đầy đủ như thế này:

1 2 3 4 ... 
a a1 a2 a3 a4 ... 
b b1 b2 b3 b4 ... 
c c1 c2 c3 c4 ... 
d d1 d2 d3 d4 ... 

. . . . . . 
. . . . . . 
. . . . . . 

Tất nhiên, làm việc trên bất kỳ hàng duy nhất sẽ cho chúng ta các yếu tố vô hạn trước khi nó đạt đến hàng tiếp theo; tương tự như đi cột-khôn ngoan sẽ là thảm họa. Nhưng chúng ta có thể đi dọc theo đường chéo đi xuống và sang trái, bắt đầu một lần nữa ở xa hơn một chút về phía bên phải mỗi khi chúng ta tới được cạnh của lưới điện.

a1 

    a2 
b1 

     a3 
    b2 
c1 

     a4 
     b3 
    c2 
d1 

... v.v. Theo thứ tự, điều này sẽ cung cấp cho chúng tôi:

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ... 

Để mã này trong Haskell, đầu tiên chúng ta có thể viết các phiên bản sản xuất bảng hai chiều:

cartesian2d :: [a] -> [b] -> [[(a, b)]] 
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs] 

Một phương pháp hiệu quả của diagonalizing là để sau đó lặp lại đầu tiên dọc theo đường chéo và sau đó dọc theo chiều sâu của mỗi đường chéo, kéo ra từng phần tử thích hợp mỗi lần. Để đơn giản giải thích, tôi sẽ giả định rằng cả hai danh sách đầu vào là vô hạn, vì vậy chúng tôi không phải lộn xộn xung quanh với kiểm tra giới hạn.

diagonalBad :: [[a]] -> [a] 
diagonalBad xs = 
    [ xs !! row !! col 
    | diagonal <- [0..] 
    , depth <- [0..diagonal] 
    , let row = depth 
      col = diagonal - depth 
    ] 

thực hiện này là một chút may mắn: lặp đi lặp lại danh sách chỉ mục hoạt động !! ngày càng trở nên đắt đỏ hơn khi chúng ta đi, đưa ra một hiệu suất khá xấu tiệm cận. Việc triển khai hiệu quả hơn sẽ thực hiện ý tưởng trên nhưng thực hiện nó bằng cách sử dụng khóa kéo. Vì vậy, chúng tôi sẽ chia lưới vô hạn của chúng tôi thành ba hình dạng như sau:

a1 a2/a3 a4 ... 
    /
    /
b1/b2 b3 b4 ... 
/
/
/
c1 c2 c3 c4 ... 
--------------------------------- 
d1 d2 d3 d4 ... 

. . . . . 
. . . . . 
. . . . . 

Hình tam giác trên cùng bên trái sẽ là các bit chúng tôi đã phát ra; tứ giác trên cùng bên phải sẽ là những hàng đã được phát ra một phần nhưng vẫn sẽ đóng góp vào kết quả; và hình chữ nhật phía dưới sẽ là các hàng mà chúng tôi chưa bắt đầu phát ra. Để bắt đầu, tam giác trên và tứ giác trên sẽ trống, và hình chữ nhật phía dưới sẽ là toàn bộ lưới. Trên mỗi bước, chúng ta có thể phát ra phần tử đầu tiên của mỗi hàng trong tứ giác trên (về cơ bản di chuyển đường nghiêng qua một), sau đó thêm một hàng mới từ hình chữ nhật dưới lên tứ giác trên (về cơ bản di chuyển đường ngang xuống một).

diagonal :: [[a]] -> [a] 
diagonal = go [] where 
    go upper lower = [h | h:_ <- upper] ++ case lower of 
     []   -> concat (transpose upper') 
     row:lower' -> go (row:upper') lower' 
     where upper' = [t | _:t <- upper] 

Mặc dù điều này có vẻ phức tạp hơn một chút nhưng hiệu quả hơn đáng kể. Nó cũng xử lý các giới hạn kiểm tra mà chúng tôi punted trên trong phiên bản đơn giản.

Nhưng bạn không nên tự viết tất cả mã này! Thay vào đó, bạn nên sử dụng gói universe. Trong Data.Universe.Helpers, có (+*+), những gói cùng nhau trên cartesian2d và diagonal chức năng để cung cấp cho chỉ hoạt động sản phẩm Descartes:

Data.Universe.Helpers> "abcd" +*+ [1..4] 
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)] 

Bạn cũng có thể nhìn thấy các đường chéo mình nếu cấu trúc đó trở nên hữu ích:

Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4] 
[('a',1)] 
[('a',2),('b',1)] 
[('a',3),('b',2),('c',1)] 
[('a',4),('b',3),('c',2),('d',1)] 
[('b',4),('c',3),('d',2)] 
[('c',4),('d',3)] 
[('d',4)] 

Nếu bạn có nhiều danh sách để cùng nhau sản xuất, việc lặp lại (+*+) có thể sai lệch danh sách nhất định; bạn có thể sử dụng choices :: [[a]] -> [[a]] cho nhu cầu sản phẩm nes chiều của bạn.