Dividere la lista in una lista di possibili tuple

Devo dividere una lista in una lista di tutte le possibili tuple, ma non sono sicuro di come farlo.

Per esempio

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

dovrebbe comportare

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

Sono stato in grado di formare i primi due, ma non sono sicuro di come ottenere il resto.

Ecco cosa ho finora:

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

Puoi usare una comprensione di lista:

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

Questa risposta è divisa in due parti. La prima parte affronta direttamente la domanda. La seconda parte si muove su una tangente (letteralmente) per scavare nella matematica dietro la prima parte: può quindi rivelarsi un materiale difficile di scarso interesse, ma ho pensato che alcuni estremisti potrebbero goderne.

Le risposte che ho visto finora fanno un uso accurato delle list comprehensions o del loro equivalente monadico, ma usano l’ uguaglianza per escludere duplicati, richiedendo quindi un vincolo Eq extra. Ecco una soluzione che rende tutte le coppie di elementi in due diverse posizioni .

In primo luogo, scrivo una funzione utile che decora ogni elemento di una lista con l’elenco degli elementi in altre posizioni: tutti i modi per “sceglierne uno e lasciare gli altri”. È molto utile ogni volta che vengono utilizzate liste per raccogliere materiale per la selezione, senza sostituzione, ed è qualcosa che trovo che uso molto.

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

Si noti che map fst . picks = id map fst . picks = id , in modo che l'elemento selezionato in ogni posizione del risultato sia l'elemento di quella posizione nell'elenco originale: questo è ciò che intendevo per "decora".

Ora è facile sceglierne due, usando lo stesso metodo di comprensione delle liste come nelle altre risposte. Ma invece di selezionare il primo componente dalla lista stessa, possiamo selezionare dalle sue picks , allo stesso tempo acquisire l'elenco dei candidati per il secondo componente.

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

È altrettanto facile ottenere le triple, prendendo picks due volte.

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

Per uniformità, è quasi allettante rendere il codice leggermente meno efficiente, scrivendo (z, _) <- picks ys piuttosto che z <- ys in entrambi.

Se l'elenco di input non ha duplicati, non si otterranno tuple duplicate nell'output, perché le tuple prendono i loro elementi da posizioni diverse. Tuttavia, otterrai

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

Per evitare ciò, sentitevi liberi di usare allPairs . nub allPairs . nub , che rimuove i duplicati prima della selezione e richiede ancora una volta un'istanza Eq per il tipo di elemento.


Solo per gli estremisti: contenitori, calcolo, consonanti e combinatori ahoy!

picks sono un'istanza di un costrutto più generale, derivante dal calcolo differenziale. È un fatto divertente che per ogni dato tipo di contenimento di un functor f , la sua derivata matematica, ∂f, rappresenti f -strutture con un elemento rimosso. Per esempio,

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

ha derivato

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

Un certo numero di operazioni possono essere associate a questa costruzione. Immagina di poter usare davvero ∂ (e possiamo codificarlo in base alle famiglie di tipi). Potremmo quindi dire

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

per dare un tipo di elementi selezionati decorati dal contesto. Dovremmo certamente aspettarci di avere l'operazione

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

Questa operazione di plug ci sposta verso la radice se stiamo facendo un giro su un albero i cui nodes sono visti come contenitori di sottoalberi.

Dovremmo anche aspettarci che InContext f sia una comonade, con

 counit :: InContext fx -> x counit = selected 

proiettando l'elemento selezionato e

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

decorare ogni elemento con il suo contesto, mostrando tutti i modi possibili di rifocalizzazione , selezionando un elemento diverso.

L'inestimabile Peter Hancock una volta mi suggerì che dovremmo anche aspettarci di essere in grado di muoversi "in basso" (che significa "lontano dalla radice"), raccogliendo tutti i modi possibili per scegliere un elemento in contesto da un'intera struttura.

 picks :: fx -> f (InContext fx) 

dovrebbe decorare ogni x -elemento nella input f -structure con il suo contesto. Dovremmo aspettarcelo

 fmap selected . picks = id 

che è la legge che avevamo prima, ma anche

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

dicendoci che ogni elemento decorato è una scomposizione dei dati originali. Non avevamo questa legge sopra. Abbiamo avuto

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

decorare ogni elemento non proprio con qualcosa di simile al suo contesto: dalla semplice lista di altri elementi, non puoi vedere dove si trova il "buco". In verità,

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

separare la lista di elementi prima del buco dagli elementi dopo il buco. Probabilmente, avrei dovuto scrivere

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

e questa è certamente un'operazione molto utile anche.

Ma quello che sta realmente accadendo è abbastanza ragionevole, e solo un leggero abuso. Nel codice che ho originariamente scritto, sto assumendo localmente [] per rappresentare borse finite o liste non ordinate . Le borse sono liste senza una nozione di posizione specifica, quindi se selezioni un elemento, il suo contesto è solo il sacchetto degli elementi rimanenti. Infatti

 ∂Bag = Bag -- really? why? 

quindi la nozione giusta di picks è davvero

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

Rappresenta la Bag di [] e questo è quello che avevamo. Inoltre, per i sacchi, la plug è solo (:) e, fino all'uguaglianza dei sacchi (cioè la permutazione), la seconda legge per i picks valida.

Un altro modo di guardare le borse è come una serie di potenze. Una borsa è una scelta di tuple di qualsiasi dimensione, con tutte le possibili permutazioni ( n! Per taglia n ) identificate. Quindi possiamo scrivere in modo combinatorio come una grande sum di poteri citata dai fattoriali, perché devi dividere per x ^ n per n! per rendere conto del fatto che ognuno dei n! gli ordini in cui potresti aver scelto le x ti danno la stessa borsa.

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

così

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

spostando la serie lateralmente. In effetti, potresti aver riconosciuto la serie di potenze per Bag come quella per exp (o e ^ x), che è famosa per essere la sua derivata.

Quindi, uh! Ecco qua. Un'operazione naturalmente derivante dall'interpretazione del tipo di funzione esponenziale, essendo la sua derivata, è il pratico pezzo di kit per risolvere problemi basati sulla selezione-senza-sostituzione.

Il mio approccio, che è in qualche modo simile ad altri ‘. Non richiede Eq .

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

Un’altra possibilità è usare la notazione monadica:

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

(Il tipo più generale per questa definizione di pairs sarebbe (MonadPlus m, Eq a) => ma -> m (a,a) ma credo che non ci siano istanze di MonadPlus diverse da [] per le quali avrebbe senso. )

 import Control.Applicative pairs xs = filter (uncurry (/=)) $ (,) <$> xs <*> xs 
 pairs = (filter.uncurry) (/=) . (join.liftA2) (,)