24 votes

Le fractionnement de la liste dans une liste de tuples

J'ai besoin de partager une liste dans une liste de toutes les tuples, mais je ne suis pas sûr de la façon de le faire.

Par exemple

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

devrait en résulter

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

J'ai été en mesure de former les deux premiers, mais je suis pas sûr de savoir comment obtenir le reste.

Voici ce que j'ai à ce jour:

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

100voto

pigworker Points 20324

Cette réponse est en deux parties. La première partie aborde la question directement. La deuxième partie passe sur une tangente (littéralement) dans le but de creuser sur dans les mathématiques derrière la première partie: il peut donc s'avérer difficile d'intérêt limité, mais j'ai pensé à quelques extrémistes pourraient en profiter.

Les réponses que j'ai vu jusqu'à présent faire neat utilisation des interprétations de la liste ou de leur monadique équivalent, mais ils utilisent l'égalité pour exclure les doublons, ce qui nécessite l'extra - Eq contrainte. Voici une solution qui rend toutes les paires d'éléments dans deux différentes positions.

Tout d'abord, j'écris une fonction très pratique qui décore chaque élément d'une liste avec la liste des éléments dans d'autres positions: de toutes les façons "d'en choisir un et de laisser les autres". C'est très utile lorsque les listes sont utilisées pour collecter des trucs pour la sélection-sans-remplacement, et c'est quelque chose que je trouve que j'utilise beaucoup.

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

Notez que map fst . picks = id, de sorte que l'élément sélectionné dans chaque position de la résultat est l'élément à partir de cette position dans la liste d'origine: c'est ce que je voulais dire par "décore".

Maintenant, il est facile à prendre en deux, en utilisant la même liste de compréhension de la méthode comme dans les autres réponses. Mais au lieu de sélectionner le premier élément de la liste elle-même, on peut sélectionner à partir de son picks, dans le même temps, l'acquisition de la liste des candidats pour le second volet.

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

Il est tout aussi facile de se procurer des triples, en prenant picks deux fois.

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

Pour l'uniformité, c'est presque tentant de rendre le code un peu moins efficace, la rédaction (z, _) <- picks ys plutôt que d' z <- ys dans les deux.

Si la liste de saisie a pas de doublons, vous n'aurez pas de duplication des tuples dans la sortie, parce que les tuples de prendre leurs éléments à partir de positions différentes. Cependant, vous obtiendrez

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

Pour éviter cela, n'hésitez pas à utiliser allPairs . nub, ce qui supprime les doublons avant de la sélection et de la demande une fois de plus un Eq exemple pour le type d'élément.


Pour les extrémistes seulement: conteneurs, de calcul, de comonads et de la combinatoire ahoy!

picks est une instance d'un programme plus général de la construction, résultant de la différence de calcul. Il est aussi amusant fait que pour tout containery sorte de un foncteur f, mathématique dérivés, ∂f, représente f-structures avec un élément supprimé. Par exemple,

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

a dérivé

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

Un certain nombre d'opérations peuvent être associés à cette construction. Imaginer que l'on peut vraiment utiliser ∂ (et on a un peu de code en utilisant le type de familles). Nous pourrions dire alors

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

pour donner un type d'éléments sélectionnés décoré par le contexte. Nous devons certainement nous attendre à avoir de l'opération

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

Cette plug fonctionnement se déplace vers la racine si nous sommes zippering dans un arbre dont les nœuds sont considérés comme des conteneurs de sous-arbres.

On doit également s'attendre InContext f être un comonad, avec

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

la projection sur l'élément sélectionné et

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

la décoration de chaque élément dans son contexte, en montrant tous les possibles, vous pourriez vous recentrer, de la sélection d'un élément différent.

L'inestimable Peter Hancock, une fois m'a suggéré que l'on doit également s'attendre à être en mesure de se déplacer "vers le bas" (qui signifie "loin de la racine"), la collecte de toutes les façons possibles de choisir un élément dans le contexte de l'ensemble de la structure.

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

devrait décorer chaque x-élément dans l'entrée f-structure avec son environnement. On devrait s'attendre à ce que

fmap selected . picks = id

qui est la loi que nous avions précédemment, mais aussi

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

de nous dire que toutes décorées élément est une décomposition des données d'origine. Nous n'avons pas que la loi ci-dessus. Nous avons eu

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

la décoration de chaque élément, pas tout à fait avec quelque chose d'un peu comme son contexte: à partir de seulement la liste des autres éléments, vous ne pouvez pas voir où le "trou" est. En vérité,

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

la séparation de la liste des éléments devant le trou à partir des éléments après le trou. Sans doute, je l'aurais écrit

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

et c'est certainement un très utile fonctionnement trop.

Mais ce qui se passe réellement est tout à fait raisonnable, et qu'un léger abus. Dans le code que j'ai initialement écrit, je suis en local prenant [] pour représenter finis les sacs ou les listes non ordonnées. Les sacs sont des listes sans une notion de position spécifique, donc si vous sélectionnez un élément, son contexte est juste le sac, les éléments restants. En effet

∂Bag = Bag   -- really? why?

ainsi la notion d' picks est en effet

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

Représenter Bag par [] et c'est ce que nous avons eu. En outre, pour les sacs, plug est juste (:) et, jusqu'à sac de l'égalité (c'est à dire, de permutation), la deuxième loi de picks ne détiennent.

Une autre façon de regarder les sacs est comme une puissance de la série. Un sac est un choix de n-uplets de toute taille, avec toutes les permutations possibles (n! pour la taille n) est identifié. Donc on peut l'écrire de façon combinatoire comme une grande somme des puissances quotiented par factorielles, parce que vous avez à diviser par x^n par n! pour tenir compte du fait que chacune des n! les commandes dont vous pourriez avoir choisi le x vous donne le même sac.

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

donc

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

déplacement de la série de côté. En effet, vous avez peut-être reconnu la puissance de la série pour Bag comme étant celle de exp (ou e^x), qui est célèbre pour être sa propre dérivée.

Donc, ouf! Là vous allez. Une opération découlant naturellement du type de données de l'interprétation de la fonction exponentielle, étant sa propre dérivé, c'est le morceau de handy kit pour résoudre des problèmes basés sur la sélection-sans remplacement.

25voto

user5402 Points 8479

Vous pouvez utiliser une liste de compréhension:

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

5voto

Mon approche, ce qui est quelque peu similaire à celle des autres. Il ne nécessite pas d' Eq.

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

2voto

Petr Pudlák Points 25113

Une autre possibilité est d'utiliser monadique notation:

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

(Le type de cette définition de l' pairs serait (MonadPlus m, Eq a) => m a -> m (a,a) mais je crois qu'il n'existe aucune instance de l' MonadPlus autres qu' [] pour qui cela aurait du sens.)

2voto

Landei Points 30509
import Control.Applicative

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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X