Tách danh sách thành một danh sách các bộ dữ liệu có thể

Question

Tôi cần chia danh sách thành danh sách tất cả các bộ dữ liệu có thể, nhưng tôi không chắc chắn về cách thực hiện.

Ví dụ

pairs ["cat","dog","mouse"] 

nên kết quả trong

[("cat","dog"), ("cat","mouse"), ("dog","cat"), ("dog","mouse"), ("mouse","cat"), ("mouse","dog")]

tôi đã có thể hình thành nên hai đầu tiên, nhưng không chắc chắn làm thế nào để có được phần còn lại.

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

pairs :: [a] -> [(a,a)] 
pairs (x:xs) = [(m,n) | m <- [x], n <- xs] 

Answer 1

Bạn có thể sử dụng danh sách hiểu:

allpairs :: Eq a => [a] -> [(a,a)] 
allpairs xs = [ (x1,x2) | x1 <- xs, x2 <- xs, x1 /= x2 ] 

Answer 2

Một khả năng khác là sử dụng ký hiệu monadic:

pairs :: (Eq a) => [a] -> [(a,a)] 
pairs l = do 
    x <- l 
    y <- l 
    guard (x /= y) 
    return (x, y) 

(Nhất loại chung cho định nghĩa này là pairs sẽ là (MonadPlus m, Eq a) => m a -> m (a,a) nhưng tôi tin rằng có không có cá thể nào của MonadPlus khác với [] mà nó có ý nghĩa.)

Answer 3

Câu trả lời này là hai phần. Phần đầu tiên giải quyết trực tiếp câu hỏi. Phần thứ hai diễn ra trên một tiếp tuyến (theo nghĩa đen) để đào sâu về toán học đằng sau phần đầu tiên: nó có thể chứng minh là vật liệu khó có lợi ích hạn chế, nhưng tôi nghĩ một số cực đoan có thể thích nó.

Những câu trả lời tôi đã nhìn thấy cho đến nay sử dụng gọn gàng của comprehensions danh sách hoặc tương đương monadic của họ, nhưng họ sử dụng bình đẳng để loại trừ các bản sao, do đó đòi hỏi thêm Eq hạn chế. Đây là một giải pháp mà làm cho tất cả các cặp của các yếu tố ở hai vị trí khác nhau .

Thứ nhất, tôi viết một hàm tiện dụng để trang trí từng phần tử của danh sách với danh sách các phần tử ở các vị trí khác: tất cả các cách để "chọn một và bỏ những người khác". Nó rất hữu ích bất cứ khi nào danh sách đang được sử dụng để thu thập các công cụ để lựa chọn mà không cần thay thế, và đó là điều tôi thấy tôi sử dụng rất nhiều.

picks :: [x] -> [(x, [x])] 
picks [] = [] 
picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs] 

Lưu ý rằng map fst . picks = id, do đó thành phần được chọn trong mỗi vị trí của kết quả là các phần tử từ vị trí đó trong danh sách ban đầu: đó là những gì tôi có nghĩa là bằng cách "trang trí".

Bây giờ thật dễ dàng để chọn hai, sử dụng cùng một phương pháp đọc danh sách như trong các câu trả lời khác. Nhưng thay vì chọn thành phần đầu tiên từ danh sách, chúng ta có thể chọn từ picks, đồng thời có được danh sách các ứng cử viên cho thành phần thứ hai.

allPairs :: [x] -> [(x, x)] 
allPairs xs = [(y, z) | (y, ys) <- picks xs, z <- ys] 

Thật dễ dàng để giữ các bộ ba, lấy picks hai lần.

allTriples :: [x] -> [(x, x, x)] 
allTriples ws = [(x, y, z) | (x, xs) <- picks ws, (y, ys) <- picks xs, z <- ys] 

Đối với tính thống nhất, nó gần như hấp dẫn để làm cho đoạn code hơi kém hiệu quả, viết (z, _) <- picks ys hơn z <- ys trong cả hai.

Nếu danh sách đầu vào không có bản sao, bạn sẽ không nhận được bất kỳ bộ dữ liệu trùng lặp nào ở đầu ra vì các bộ dữ liệu lấy các phần tử của chúng từ các vị trí khác nhau. Tuy nhiên, bạn sẽ nhận được

Picks> allPairs ["cat", "cat"] 
[("cat","cat"),("cat","cat")] 

Để tránh điều đó, cảm thấy tự do để sử dụng allPairs . nub, mà loại bỏ trùng lặp trước khi lựa chọn và yêu cầu một lần nữa một thể hiện Eq cho các loại nguyên tố.

---

Đối với phần tử cực đoan chỉ: container, calculus, comonads và tổ hợp ahoy!

picks là một ví dụ về cấu trúc tổng quát hơn, phát sinh từ phép tính vi phân. Đó là một thực tế thú vị rằng đối với bất kỳ loại ngăn chặn nào của một functor f, dẫn xuất toán học của nó, ∂f, đại diện cho f-cấu trúc với một phần tử bị loại bỏ. Ví dụ,

newtype Trio x = Trio (x, x, x) -- x^3 

có phái sinh

data DTrio x = Left3 ((), x, x) | Mid3 (x,(), x) | Right3 (x, x,()) -- 3*x^2 

Một số hoạt động có thể được kết hợp với xây dựng này. Hãy tưởng tượng chúng ta thực sự có thể sử dụng ∂ (và chúng ta có thể mã hóa nó bằng cách sử dụng các họ kiểu). Khi đó, chúng tôi có thể nói

data InContext f x = (:-) {selected :: x, context :: ∂f x} 

để cung cấp cho một loại yếu tố được chọn được trang trí theo ngữ cảnh. Chúng tôi chắc chắn sẽ mong đợi để có hoạt động

plug :: InContext f x -> f x -- putting the element back in its place 

hoạt động plug này đưa chúng ta về phía gốc nếu chúng ta đang zippering về trong một cây có các nút được coi là thùng chứa của subtrees.

Chúng ta cũng nên hy vọng InContext f là một comonad, với

counit :: InContext f x -> x 
counit = selected 

nhô ra thành phần được chọn và

cojoin :: InContext f x -> InContext f (InContext f x) 

trang trí mọi phần tử với bối cảnh của nó, hiển thị tất cả những cách có thể bạn có thể tái tập trung, chọn yếu tố khác. Peter Hancock đã từng đề nghị với tôi rằng chúng ta cũng nên mong đợi để có thể di chuyển "xuống" (có nghĩa là "đi từ gốc"), thu thập tất cả các cách có thể để chọn một yếu tố trong bối cảnh từ một toàn bộ cấu trúc.

picks :: f x -> f (InContext f x) 

nên trang trí mỗi x -element trong -structure đầu vào f với ngữ cảnh của nó. Chúng ta nên hy vọng rằng

fmap selected . picks = id 

đó là luật chúng tôi đã có trước đó, nhưng cũng

fmap plug (picks fx) = fmap (const fx) fx 

nói với chúng ta rằng tất cả các yếu tố trang trí là một phân hủy của dữ liệu gốc. Chúng tôi không có luật đó ở trên.Chúng tôi đã có

picks :: [x] -> [(x, [x])] 

Trang trí mọi phần tử không hoàn toàn giống với ngữ cảnh của nó: từ danh sách các yếu tố khác, bạn không thể thấy "lỗ" ở đâu. Trong sự thật,

∂[] x = ([x], [x]) 

tách danh sách các phần tử trước lỗ từ các phần tử sau lỗ. Có thể cho rằng, tôi cần phải viết

picks :: [x] -> [(x, ([x], [x]))] 
picks [] = [] 
picks (x : xs) = (x, ([], xs)) : [(y, (x : ys, ys')) | (y, (ys, ys')) <- picks xs] 

và đó chắc chắn là một hoạt động rất hữu ích.

Nhưng những gì thực sự diễn ra khá hợp lý và chỉ có một sự lạm dụng nhỏ. Trong mã tôi đã viết ban đầu, tôi đang sử dụng địa phương [] để đại diện cho túi hữu hạn hoặc danh sách không theo thứ tự. Túi là danh sách không có khái niệm vị trí cụ thể, vì vậy nếu bạn chọn một phần tử, ngữ cảnh của nó chỉ là túi của các phần tử còn lại. Thật vậy

∂Bag = Bag -- really? why? 

nên khái niệm quyền picks thực sự là

picks :: Bag x -> Bag (x, Bag x) 

Đại diện Bag bởi [] và đó là những gì chúng tôi đã có. Hơn nữa, đối với túi xách, plug chỉ là (:) và, lên đến bình đẳng túi (nghĩa là, hoán vị), luật thứ hai cho số pickskhông giữ.

Một cách khác để xem túi là một chuỗi công suất. Túi là một lựa chọn các bộ dữ liệu có kích thước bất kỳ, với tất cả các hoán vị có thể (n! đối với kích thước n) đã xác định. Vì vậy, chúng ta có thể viết nó một cách tổng hợp như một số tiền lớn của các quyền hạn được định nghĩa bởi giai thừa, bởi vì bạn phải chia cho x^n bởi n! tính đến thực tế là mỗi n! đơn đặt hàng mà bạn có thể đã chọn của x cung cấp cho bạn cùng một túi.

Bag x = 1 + x + x^2/2! + x^3/3! + ... 

nên

∂Bag x = 0 + 1 + x  + x^2/2! + ... 

chuyển series ngang. Thật vậy, bạn cũng có thể đã nhận ra chuỗi quyền lực cho Bag giống như đối với exp (hoặc e^x), nổi tiếng là dẫn xuất riêng của nó.

Vì vậy, hãy nhai! Có bạn đi. Một hoạt động tự nhiên phát sinh từ việc giải thích kiểu dữ liệu của hàm mũ, là đạo hàm riêng của nó, là phần tiện dụng của bộ để giải quyết các vấn đề dựa trên lựa chọn mà không cần thay thế.

Answer 4

import Control.Applicative 

pairs xs = filter (uncurry (/=)) $ (,) <$> xs <*> xs 

Answer 5

Cách tiếp cận của tôi, tương tự như cách khác '. Nó không yêu cầu Eq.

allpairs :: [t] -> [(t,t)] 
allpairs [] = [] 
allpairs [_] = [] 
allpairs (x:xs) = concatMap (\y -> [(x,y),(y,x)]) xs ++ allpairs xs 

Answer 6

pairs = (filter.uncurry) (/=) . (join.liftA2) (,)