Мне нужно разбить список на список всех возможных кортежей, но я не уверен, как это сделать.
Например
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, так что выбранный элемент в каждой позиции результата является элементом из этой позиции в исходном списке: это то, что я имел в виду под "украшением".
Теперь легко выбрать два, используя тот же метод понимания списка, что и в других ответах. Но вместо того, чтобы выбрать первый компонент из самого списка, мы можем выбрать его picks, в то же время получив список кандидатов для второго компонента.
allPairs :: [x] -> [(x, x)]
allPairs xs = [(y, z) | (y, ys) <- picks xs, z <- ys]
Так же легко получить тройки, взяв picks дважды.
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, который удаляет дубликаты перед выбором и снова требует экземпляр 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 f x = (:-) {selected :: x, context :: ∂f x}
чтобы указать тип выбранных элементов, украшенных контекстом. Мы, конечно же, должны ожидать, что операция
plug :: InContext f x -> f x -- putting the element back in its place
Эта операция plug перемещает нас к корню, если мы зацикливаемся на дереве, узлы которого рассматриваются как контейнеры поддеревьев.
Мы также должны ожидать, что InContext f будет comonad, с
counit :: InContext f x -> x
counit = selected
проецирование выбранного элемента и
cojoin :: InContext f x -> InContext f (InContext f x)
украшая каждый элемент своим контекстом, демонстрируя все возможные способы переориентации, выбирая другой элемент.
Неоценимый Питер Хэнкок однажды предложил мне, что мы также должны ожидать перехода "вниз" (что означает "подальше от корня" ), собирая все возможные способы выбора элемента в контексте из целого структура.
picks :: f x -> f (InContext f x)
должен украшать каждый 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 как таковой для 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) => m a -> m (a,a), но я считаю, что нет экземпляра MonadPlus, кроме [], для которого это имеет смысл.)
import Control.Applicative
pairs xs = filter (uncurry (/=)) $ (,) <$> xs <*> xs
pairs = (filter.uncurry) (/=) . (join.liftA2) (,)