que quieren hacer una función que toma una lista por ejemploListas - pares combinando
[('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)]
y luego suma los números juntos cuando la letra es la misma. Por lo que la entrada por encima produciría
[('A',8), ('B',2), ('C',7)].
Podría alguien por favor me acaba de dar una idea de cómo abordar esto, me gustaría tratar de hacer lo más posible a mí mismo!
Puede usar Data.Map's fromListWith para construir un mapa que tenga los valores sumados. Es tipo es la siguiente:
fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Toma una lista de pares (como se describe) como el primer argumento, si ve un duplicado, se utiliza alguna función (el primer argumento), para combinar el valor original con uno nuevo. A partir de ahí, puede convertir este mapa nuevamente en una lista de pares (también una función en Data.Map).
Puede hacer esto con listas puras, pero probablemente no sea tan eficiente, ya que construirá una nueva lista (o partes de ella) con bastante frecuencia.
Bueno, comience por dividir el problema en pedazos más pequeños.
Primero, ignore la condición adicional. ¿Cuál es el objetivo final? Agregando algunos números juntos, y probablemente ya sepa cómo hacerlo.
Pero no desea agregar todos números, ¿cómo sabe cuáles agregar? Vea si las letras coinciden. Entonces necesitas compararlos de alguna manera.
Una vez que sepa cómo agregar números y decidir si debe agregar dos números, necesita una forma de abordar toda la lista. No llegarás a ninguna parte con todos ellos mezclados, por lo que debes separar las cosas según los números que agregues. Puede hacer todo esto de una vez al crear sublistas, o puede filtrar de a una por vez, u otros enfoques, algunos de los cuales pueden ser más o menos eficientes que otros.
Esa es la idea básica, de todos modos. Entonces, volviendo a los pasos, comienza con una lista, separa los grupos de artículos en función de las letras que comparan, luego agrega todos los números en cada grupo resultante.
Obviamente me he saltado algunos pasos, como comparar letras y agregar números cuando se combinan como tuplas, ya que dijiste que preferirías resolver las cosas por tu cuenta. :]
Hay varias maneras de resolver esto y Adam ya te ha dado una manera eficiente basada en mapas. Sin embargo, creo que una solución que use solo listas y recursiones también sería instructiva, especialmente al aprender Haskell. Como ya has recibido una respuesta, espero poder escribir una solución aquí sin estropear nada.
La forma en que me acerqué a esto es pensar en cómo podemos reducir la lista de entrada a la lista de salida. Comenzamos con
[('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)]
El objetivo es terminar con una lista de resultados, donde cada tupla comienza con un carácter único. La creación de dicha lista de resultados se puede realizar de forma incremental: comience con una lista vacía y luego inserte tuplas en la lista, asegurándose de no duplicar los caracteres.El tipo sería
insertInResult :: (Char, Integer) -> [(Char, Integer)] -> [(Char, Integer)]
Se necesita el par, como ('A',3) y lo inserta en una lista existente de pares únicos. El resultado es una nueva lista de pares únicos. Esto se puede hacer de esta manera:
insertInResult (c, n) [] = [(c, n)]
insertInResult (c, n) ((c', n'):results)
| c == c' = (c, n + n') : results
| otherwise = (c', n') : (insertInResult (c, n) results)
Explicación: insertar una tupla en una lista de resultados vacío es fácil, basta con insertar la misma. Si la lista de resultados no está vacía, obtenemos el primer resultado (c', n') con coincidencia de patrones. Verificamos si los personajes coinciden con el guardia, y agregamos los números si es así. De lo contrario, simplemente copiemos la tupla del resultado e inserte la tupla (c, n) en los resultados restantes.
Ahora podemos hacer
*Main> insertInResult ('A',3) []
[('A',3)]
*Main> insertInResult ('B',2) [('A',3)]
[('A',3),('B',2)]
El siguiente paso es utilizar insertInResult repetidamente en la lista de entrada de manera que construimos una lista de resultados. Llamé a esta función sumPairs' ya llamé a la función de nivel superior sumPairs:
sumPairs' :: [(Char, Integer)] -> [(Char, Integer)] -> [(Char, Integer)]
sumPairs' [] results = results
sumPairs' (p:pairs) results = sumPairs' pairs (insertInResult p results)
Es una función simple que sólo repite en el primer argumento e inserta cada par en la lista de resultados. El último paso es llamar a esta función auxiliar con una lista de resultados vacía:
sumPairs :: [(Char, Integer)] -> [(Char, Integer)]
sumPairs pairs = sumPairs' pairs []
¡Funciona! :-)
*Main> sumPairs [('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)]
[('A',8),('B',2),('C',7)]
La complejidad de esta solución no es tan bueno como el basado en Data.Map. Para una lista con n pares, llamamos insertInResultn veces desde sumPairs'. Cada llamada al insertInResult puede iterar hasta n veces hasta que encuentre una tupla de resultado coincidente, o llegue al final de los resultados. Esto da una complejidad de tiempo de O (n ²). La solución basada en Data.Map tendrá O (n registro n) complejidad del tiempo ya que utiliza log n tiempo para insertar y actualizar cada uno de los n elementos.
Tenga en cuenta que esta es la misma complejidad que habría obtenido si hubiera ordenado la lista de entrada y luego escaneada una vez para sumar tuplas adyacentes con el mismo carácter:
sumPairs pairs = sumSorted (sort pairs) []
sumSorted [] result = result
sumSorted (p:pairs) [] = sumSorted pairs [p]
sumSorted ((c,n) : pairs) ((c',n') : results)
| c == c' = sumSorted pairs ((c,n + n') : results)
| otherwise = sumSorted pairs ((c,n) : (c',n') : results)
Además de la excelente Map basado en la solución, creo que una solución puramente basada en listas puede ser bastante instructiva. Como con un Map, el bit interesante es agrupar esos elementos con el mismo primer elemento. Hay una función incorporada group (y su versión generalizada groupBy) que fusiona elementos adyacentes:
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
El primer argumento indica cuándo debe unirse dos elementos.Por ejemplo:
> groupBy (\x y -> odd x == odd y) [1,1,3,4,6,5,7]
[[1,1,3],[4,6],[5,7]]
Por desgracia, como podemos ver aquí, sólo se funde adyacentes elementos, por lo que tenemos que encontrar una manera que se recojan los elementos de la lista original primero, para que las personas con claves iguales son uno al lado del otro. Hay otra función incorporada para hacer algo como eso: sort. El truco final es resumir los segundos elementos de trozos que tienen todos los primeros elementos iguales. Vamos a escribir una función que simplemente asume que ha pasado una buena parte no vacía con todos los primeros elementos iguales:
sumSnds :: Num b => [(a,b)] -> (a,b)
sumSnds abs = (a, sum bs) where
(a:_, bs) = unzip abs
Ahora puede encadenar todas estas piezas juntas:
solution :: (Ord a, Ord b, Num b) => [(a,b)] -> [(a,b)]
solution = map sumSnds . groupBy (\x y -> fst x == fst y) . sort
mucho más fácil de lo que pensaba ¡ser! –
Bueno ... Espero no haber aprovechado ninguna oportunidad de aprendizaje en las versiones anteriores de mi respuesta. –