Разбиение списка в список возможных кортежей

Мне нужно разбить список на список всех возможных кортежей, но я не уверен, как это сделать.

Например

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

должно привести к

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

Я смог сформировать первые два, но я не уверен, как получить остальное.

Вот что я до сих пор:

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

Вы можете использовать понимание списка:

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

Этот ответ состоит из двух частей. Первая часть напрямую касается вопроса. Вторая часть идет по касательной (буквально), чтобы усвоить математику, стоящую за первой частью: она может оказаться сложным материалом с ограниченным интересом, но я подумал, что некоторым экстремистам это понравится.

Ответы, которые я видел до сих пор, делают аккуратное использование списков или их монадический эквивалент, но они используют равенство, чтобы исключить дубликаты, тем самым требуя дополнительного ограничения Eq . Вот решение, которое делает все пары элементов в двух разных положениях .

Во-первых, я пишу удобную функцию, которая украшает каждый элемент списка списком элементов в других позициях: все способы «выбрать один и оставить остальных». Это очень полезно, когда списки используются для сбора материалов для выбора без замены, и это то, что я нахожу, я использую много.

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

Заметим, что map fst . picks = id map fst . picks = id , так что выбранный элемент в каждой позиции результата является элементом из этой позиции в исходном списке: вот что я имел в виду под «украшением».

Теперь легко выбрать два, используя тот же метод понимания списка, что и в других ответах. Но вместо того, чтобы выбрать первый компонент из самого списка, мы можем выбрать его picks , в то же время получив список кандидатов для второго компонента.

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

Так же легко завладеть троек, взяв два раза.

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

Для однородности почти соблазнительно сделать код немного менее эффективным, записывая (z, _) <- picks ys а не z <- ys в обоих.

Если в списке ввода нет дубликатов, вы не получите дублирующих кортежей в выводе, потому что кортежи берут свои элементы из разных позиций. Однако вы получите

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

Чтобы этого избежать, не стесняйтесь использовать allPairs . nub allPairs . nub , который удаляет дубликаты перед выбором и снова требует экземпляр Eq для типа элемента.


Только для экстремистов: контейнеры, исчисление, comonads и комбинаторика ahoy!

picks - один из примеров более общей конструкции, возникающей из дифференциального исчисления. Весьма забавно, что для любого заданного типа хранителя функтора f его математическая производная ∂f представляет f с удаленным одним элементом. Например,

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

имеет производную

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

С этой конструкцией может быть связан ряд операций. Представьте, что мы действительно можем использовать ∂ (и мы можем его кодировать с использованием семейств типов). Тогда мы могли бы сказать

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

чтобы дать тип выбранных элементов, украшенных контекстом. Мы, конечно, должны ожидать, что операция

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

Эта операция plug перемещает нас к корню, если мы зацикливаемся на дереве, узлы которого рассматриваются как контейнеры поддеревьев.

Мы также должны ожидать, что InContext f станет comonad, с

 counit :: InContext fx -> x counit = selected 

проецирование выбранного элемента и

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

украшая каждый элемент своим контекстом, демонстрируя все возможные способы переориентации , выбирая другой элемент.

Неоценимый Питер Хэнкок однажды предложил мне, что мы также должны ожидать, чтобы мы могли двигаться «вниз» (что означает «подальше от корня»), собирая все возможные способы выбора элемента в контексте из целостной структуры.

 picks :: fx -> f (InContext fx) 

должен украсить каждый x элемент во входной f своим контекстом. Мы должны ожидать, что

 fmap selected . picks = id 

который есть закон, который мы имели раньше, но также

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

говоря, что каждый украшенный элемент представляет собой разложение исходных данных. У нас не было этого закона выше. Мы имеем

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

украшая каждый элемент не совсем чем-то вроде своего контекста: из всего списка других элементов вы не можете видеть, где находится «дыра». Действительно,

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

отделяя список элементов перед отверстием от элементов после отверстия. Возможно, я должен был написать

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

и это, безусловно, очень полезная операция.

Но то, что действительно происходит, вполне разумно и лишь незначительное злоупотребление. В коде, который я изначально написал, я локально беру [] для представления конечных пакетов или неупорядоченных списков . Сумки представляют собой списки без понятия конкретной позиции, поэтому, если вы выберете один элемент, его контекст - это всего лишь мешок оставшихся элементов. В самом деле

 ∂Bag = Bag -- really? why? 

поэтому правильное понятие picks

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

Представьте Bag [] и это то, что у нас было. Кроме того, для мешков plug просто (:) и, вплоть до суммирования равенства (т. Е. Перестановки), второй закон для picks .

Другой способ взглянуть на сумки - это серия власти. Сумка - это выбор кортежей любого размера, с указанием всех возможных перестановок ( n! Для размера n ). Поэтому мы можем записать его комбинаторно как большую сумму степеней, координируемых факториалами, потому что вы должны разделить на x ^ n на n! чтобы учесть тот факт, что каждый из n! заказы, в которых вы могли бы выбрать x, дают вам ту же сумку.

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

так

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

смещая серию вбок. В самом деле, вы вполне могли бы признать, что ряд Bag для Bag является тем, что для exp (или e ^ x), который славится своей собственной производной.

Итак, фу! Вот так. Операция, естественным образом вытекающая из интерпретации данных экспоненциальной функции, являющейся ее собственной производной, представляет собой удобную часть набора для решения проблем, основанных на выборе без замены.

Мой подход, который несколько похож на других ». Он не требует Eq

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

Другая возможность – использовать монадические обозначения:

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

(Самый общий тип для этого определения pairs был бы (MonadPlus m, Eq a) => ma -> m (a,a) но я считаю, что нет экземпляра MonadPlus кроме [] для которого это имеет смысл. )

 import Control.Applicative pairs xs = filter (uncurry (/=)) $ (,) <$> xs <*> xs 
 pairs = (filter.uncurry) (/=) . (join.liftA2) (,) 
Давайте будем гением компьютера.