Utilizando la función de mapa de Haskell para calcular la suma de una lista

Question

Haskell

addm::[Int]->Int 
addm (x:xs) = sum(x:xs) 

que fue capaz de lograr para obtener una suma de una lista usando sum función, pero es posible obtener la suma de una lista usando la función map? ¿También qué uso tiene la función de mapa?

Answer 1

No se puede usar realmente map para resumir una lista, porque map trata cada elemento de lista independientemente de los demás. Puede utilizar map por ejemplo, para incrementar cada valor en una lista como en

map (+1) [1,2,3,4] -- gives [2,3,4,5] 

Otra forma de poner en práctica su ADDM sería utilizar foldl:

addm' = foldl (+) 0 

Answer 2

Mapa "mapas" de cada elemento de la lista a un elemento en su salida:

let f(x) = x*x 
map f [1,2,3] 

Esto devolverá una lista de los cuadrados.

En resumen todos los elementos de una lista, utilice doble:

foldl (+) 0 [1,2,3] 

+ es la función que desea aplicar, y 0 es el valor inicial (0 para la suma, 1 para el producto, etc)

Answer 3

No es posible usar map para reducir una lista a su suma. Ese patrón recursivo es fold.

sum :: [Int] -> Int 
sum = foldr (+) 0 

Como acotación al margen, tenga en cuenta que se puede definir como un pliegue map así:

map :: (a -> b) -> ([a] -> [b]) 
map f = fold (\x xs -> f x : xs) [] 

Esto se debe a foldr es la función recursiva canónica en las listas.

---

Referencias: A tutorial on the universality and expressiveness of fold, Graham Hutton, J. programación funcional 9 (4): 355-372, julio de 1999.

Answer 4

Como las otras respuestas señalan, la forma "normal" es use una de las funciones fold. Sin embargo, es posible escribir algo bastante similar a un bucle while en lenguajes imperativos:

sum' [] = 0 
sum' xs = head $ until single loop xs where 
    single [_] = True 
    single _ = False 
    loop (x1 : x2 : xs) = (x1 + x2) : xs 

Añade los dos primeros elementos de la lista juntos hasta que termina con una lista de un solo elemento, y devuelve ese valor (usando head).

Answer 5

Después de algunas ideas tengo que agregar otra respuesta: No puede obtener la suma de una lista con map, pero puede obtener la suma con su versión monadic mapM. Todo lo que necesita hacer es utilizar una mónada Writer (consulte LYAHFGG) sobre el monoide Sum (consulte LYAHFGG).

me escribió una versión especializada, que es probablemente más fácil de entender:

data Adder a = Adder a Int 

instance Monad Adder where 
    return x = Adder x 0 
    (Adder x s) >>= f = let Adder x' s' = f x 
         in Adder x' (s + s') 

toAdder x = Adder x x 

sum' xs = let Adder _ s = mapM toAdder xs in s 

main = print $ sum' [1..100] 
--5050 

Adder es sólo una envoltura alrededor de algún tipo que también mantiene un "suma en curso." Podemos hacer Adder una mónada, y aquí hace algo de trabajo: Cuando se ejecuta la operación >>= (a.k.a. "bind"), devuelve el nuevo resultado y el valor de la suma en ejecución de ese resultado más el total acumulado original. La función toAdder toma un Int y crea un Adder que contiene ese argumento como valor empaquetado y como suma acumulada (en realidad, no estamos interesados ​​en el valor, sino solo en la parte de suma). Luego, en sum'mapM puede hacer su magia: A pesar de que funciona de forma similar a map para los valores incorporados en la mónada, ejecuta funciones "monádicos" como toAdder y cadenas estas llamadas (que utiliza sequence para hacer esto). En este punto, obtenemos a través de la "puerta trasera" de nuestra mónada la interacción entre los elementos de la lista que falta en el estándar map.

Answer 6

Aquí está, la definición supuestamente imposible de sum en términos de map:

summ xs = let ys = 0 : map (\(a,b)->a+b) (zip xs ys) in last ys 

esto realmente muestra cómo scanl se pueden implementar en términos de map, al estar por encima equivalente a foldl (+) 0 xs === last $ scanl (+) 0 xs:

scannl f z xs = let ys = z : map (uncurry f) (zip ys xs) in ys 

Espero que se puedan calcular muchas cosas con map, arreglando todo tipo de flujo de información.

edición: Lo anterior es sólo una zipWith disfrazada por supuesto (y zipWith es una especie de map2):

summ xs = let ys = 0 : zipWith (+) ys xs in last ys 

Esto parece sugerir que scanl es más fundamental que foldl, visto desde esta ángulo al menos.

Answer 7

realizo esta pregunta ha sido contestada, pero quería añadir este pensamiento ...

listLen2 :: [a] -> Int 
listLen2 = sum . map (const 1) 

Creo que devuelve la constante 1 para cada elemento de la lista, y devuelve la suma! Puede que no sea la mejor práctica de codificación, pero fue un ejemplo que mi profesor nos dio a los estudiantes que parece relacionarse bien con esta pregunta.

Answer 8

map nunca puede ser la herramienta principal para sumar los elementos de un contenedor, de la misma manera que un destornillador nunca puede ser la herramienta principal para ver una película. Pero puedes usar un destornillador para arreglar un proyector de películas. Si realmente lo desea, puede escribir

import Data.Monoid 
import Data.Foldable 

mySum :: (Foldable f, Functor f, Num a) 
     => f a -> a 
mySum = getSum . fold . fmap Sum 

Por supuesto, esto es una tontería. Usted puede obtener una más general, y posiblemente más eficiente, versión:

mySum' :: (Foldable f, Num a) => f a -> a 
mySum' = getSum . foldMap Sum 

O mejor, sólo tiene que utilizar sum, porque su realidad hizo para el trabajo.