haskell - promedio - División de la lista en una lista de posibles tuplas

ordenar lista haskell

Question

Necesito dividir una lista en una lista de todas las tuplas posibles, pero no estoy seguro de cómo hacerlo.

Por ejemplo

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

debería resultar en

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

Pude formar los dos primeros, pero no estoy seguro de cómo obtener el resto.

Esto es lo que tengo hasta ahora:

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

Answer 1

Mi enfoque, que es algo similar a los demás. No requiere Eq .

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

Answer 2

Otra posibilidad es usar la notación monádica:

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

(El tipo más general para esta definición de pairs sería (MonadPlus m, Eq a) => ma -> m (a,a) pero creo que no hay ningún ejemplo de MonadPlus no sea [] para lo cual tendría sentido. )

Answer 3

Puedes usar una lista de comprensión:

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

Answer 4

Esta respuesta tiene dos partes. La primera parte aborda la pregunta directamente. La segunda parte se inicia en una tangente (literalmente) para profundizar en las matemáticas detrás de la primera parte: puede ser un material difícil de interés limitado, pero pensé que algunos extremistas podrían disfrutarlo.

Las respuestas que he visto hasta ahora hacen un buen uso de las listas de comprensión o su equivalente monádico, pero usan la igualdad para descartar duplicados, por lo que requieren una restricción Eq adicional. Aquí hay una solución que hace que todos los pares de elementos estén en dos posiciones diferentes.

En primer lugar, escribo una función útil que decora cada elemento de una lista con la lista de elementos en otras posiciones: todas las formas de "elegir una y dejar las otras". Es muy útil cuando las listas se utilizan para recopilar material para la selección sin reemplazo, y es algo que encuentro que uso mucho.

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

Tenga en cuenta que map fst . picks = id map fst . picks = id , de modo que el elemento seleccionado en cada posición del resultado es el elemento de esa posición en la lista original: eso es lo que quise decir con "decora".

Ahora es fácil elegir dos, utilizando el mismo método de comprensión de la lista que en las otras respuestas. Pero en lugar de seleccionar el primer componente de la lista, podemos seleccionar sus picks , al mismo tiempo adquirir la lista de candidatos para el segundo componente.

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

Es tan fácil hacerse con los triples, tomando picks dos veces.

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

Para uniformidad, es casi tentador hacer que el código sea menos eficiente, escribiendo (z, _) <- picks ys lugar de z <- ys en ambos.

Si la lista de entrada no tiene duplicados, no obtendrá ninguna tupla duplicada en la salida, porque las tuplas toman sus elementos de diferentes posiciones. Sin embargo, obtendrás

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

Para evitar eso, siéntete libre de usar todos los allPairs . nub allPairs . nub , que elimina los duplicados antes de la selección y exige una vez más una instancia Eq para el tipo de elemento.

Solo para extremistas: contenedores, cálculo, comonads y combinatorics ¡ahoy!

picks es una instancia de una construcción más general, que surge del cálculo diferencial. Es un hecho divertido que para cualquier tipo de contenedor dado un functor f , su derivada matemática, ∂f, representa f -estructuras con un elemento eliminado. Por ejemplo,

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

tiene derivado

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

Se pueden asociar varias operaciones con esta construcción. Imagina que realmente podemos usar ∂ (y podemos codificarlo usando familias de tipos). Entonces podríamos decir

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

para dar un tipo de elementos seleccionados decorados por contexto. Sin duda, deberíamos esperar tener la operación

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

Esta operación de plug nos mueve hacia la raíz si estamos cerrando de un árbol cuyos nodos se ven como contenedores de subárboles.

También deberíamos esperar que InContext f sea ​​comonad, con

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

proyectando el elemento seleccionado y

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

decorando cada elemento con su contexto, mostrando todas las formas posibles en que podría enfocarse , seleccionando un elemento diferente.

El inestimable Peter Hancock me sugirió una vez que también deberíamos poder movernos "hacia abajo" (es decir, "lejos de la raíz"), recopilando todas las formas posibles de elegir un elemento en contexto de una estructura completa.

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

debería decorar cada x -elemento en la estructura f entrada con su contexto. Deberíamos esperar que

fmap selected . picks = id

cual es la ley que tuvimos antes, pero también

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

diciéndonos que cada elemento decorado es una descomposición de los datos originales. No teníamos esa ley arriba. Tuvimos

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

decorar cada elemento no del todo con algo como su contexto: a partir de la lista de otros elementos, no se puede ver dónde está el "agujero". En verdad,

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

separando la lista de elementos antes del hoyo de los elementos después del hoyo. Podría decirse que debería haber escrito

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

y eso es ciertamente una operación muy útil también.

Pero lo que realmente está sucediendo es bastante sensato, y solo un leve abuso. En el código que originalmente escribí, estoy tomando localmente [] para representar bolsas finitas o listas desordenadas . Las bolsas son listas sin una noción de posición específica, por lo que si selecciona un elemento, su contexto es solo la bolsa de los elementos restantes. En efecto

∂Bag = Bag   -- really? why?

por lo que la noción correcta de picks es de hecho

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

Representa a Bag por [] y eso es lo que teníamos. Además, para las bolsas, el plug es justo (:) y, hasta la igualdad de la bolsa (es decir, la permutación), la segunda ley para las picks se mantiene.

Otra forma de mirar las bolsas es como una serie de poder. Una bolsa es una elección de tuplas de cualquier tamaño, con todas las permutaciones posibles ( n! Para tamaño n ) identificadas. Entonces, podemos escribirlo combinatoriamente como una gran suma de poderes que los factoriales asignan, ¡porque tienes que dividir por x ^ n por n! para dar cuenta del hecho de que cada uno de los n! las órdenes en las que podría haber elegido las x le da la misma bolsa.

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

asi que

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

desplazando la serie hacia los lados. De hecho, es posible que haya reconocido que la serie de potencias para Bag es aquella para exp (o e ^ x), que es famosa por ser su propia derivada.

Entonces, ¡uf! Ahí tienes. Una operación que surge naturalmente de la interpretación de tipo de datos de la función exponencial, siendo su propia derivada, es la pieza útil del kit para resolver problemas basado en la selección sin reemplazo.

Answer 5

import Control.Applicative

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

Answer 6

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