Использование функции карты Haskell для вычисления суммы списка

Question

Haskell

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

Мне удалось получить сумму списка с помощью функции sum, но возможно ли получить сумму списка с помощью функции map? И что за использование функции карты?

Answer 1

Вы не можете использовать map для суммирования списка, потому что карта обрабатывает каждый элемент списка независимо от других.Вы можете использовать map, например, чтобы увеличивать каждое значение в списке, как в

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

. Другим способом реализации вашего addm будет использование foldl :

addm' = foldl (+) 0

Answer 2

Вот оно, якобы невозможное определение sum в терминах map:

sum' xs  =  let { ys = 0 : map (\(a,b) -> a + b) (zip xs ys) } in last ys

это фактически показывает, как scanl может быть реализовано в терминах map ( и zip и last), причем приведенное выше эквивалентно foldl (+) 0 xs === last $ scanl (+) 0 xs :

scanl' f z xs  =  let { ys = z : map (uncurry f) (zip ys xs) } in ys

Я ожидаю, что можно вычислить многие вещи с помощью map, организуя для всех видов информационный поток через zip.

edit: вышеприведенное это просто zipWith замаскированный, конечно (а zipWith является своего рода map2):

sum' xs  =  let { ys = 0 : zipWith (+) ys xs } in last ys

Похоже, что scanl более универсален, чем foldl.

Answer 3

Невозможно использовать map, чтобы уменьшить список до его суммы. Этот рекурсивный шаблон является fold.

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

Обратите внимание, что вы также можете определить map как фолд:

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

Это потому, что foldr является канонической рекурсивной функцией в списках.

---

Ссылки : Учебное пособие по универсальности и выразительности сгиба , Грэм Хаттон, Дж. Функциональное программирование 9 (4): 355–372, июль 1999 г.

Answer 4

После некоторого понимания я должен добавить еще один ответ: Вы не можете получить сумму списка с помощью map, но вы можете получить сумму с помощью монадической версии mapM. Все, что вам нужно сделать, это использовать Writer монаду (см. LYAHFGG ) над моноидом Sum (см. LYAHFGG ).

Я написал специализированную версию, которая, вероятно, легче понять:

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 - это просто обертка вокруг некоторого типа, которая также сохраняет «промежуточную сумму». Мы можем сделать Adder монадой, и здесь она выполняет определенную работу: когда выполняется операция >>= (она же «связывание»), она возвращает новый результат и значение промежуточной суммы этого результата plus первоначальная сумма бега . Функция toAdder принимает Int и создает Adder, который содержит этот аргумент как в виде обернутого значения, так и в качестве текущей суммы (на самом деле нас интересует не значение, а только часть суммы). Затем в sum' mapM можно творить чудеса: хотя он работает аналогично map для значений, встроенных в монаду, он выполняет «монадические» функции, такие как toAdder и цепочки этих вызовов (для этого используется sequence). На этом этапе через «черный ход» нашей монады мы получаем взаимодействие между элементами списка, которое отсутствует в стандарте map.

Answer 5

Сопоставить "сопоставляет" каждый элемент вашего списка с элементом в вашем выводе:

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

Это вернет список квадратов.

Чтобы сложить все элементы в списке, используйте fold:

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

+ - это функция, которую вы хотите применить, а 0 - начальное значение (0 для суммы, 1 для продукта и т. Д.)

Answer 6

Я понимаю, что на этот вопрос ответили, но я хотел добавить эту мысль ...

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

Я считаю, что он возвращает константу 1 для каждого элемента в списке и возвращает сумму! Возможно, это не лучшая практика кодирования, но это был пример, который мой профессор дал нам студентам, который, похоже, хорошо относится к этому вопросу.

Answer 7

Как указывают другие ответы, «нормальным» способом является использование одной из fold функций.Однако возможно написать что-то похожее на цикл while в императивных языках:

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

Он добавляет первые два элемента списка вместе, пока не заканчивается одноэлементным списком, ивозвращает это значение (используя head).

Answer 8

map никогда не может быть основным инструментом для суммирования элементов контейнера, во многом так же, как отвертка никогда не может быть основным инструментом для просмотра фильма.Но вы можете использовать отвертку, чтобы починить кинопроектор.Если вы действительно хотите, вы можете написать

import Data.Monoid
import Data.Foldable

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

Конечно, это глупо.Вы можете получить более общую и, возможно, более эффективную версию:

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

Или, что лучше, просто используйте sum, потому что он действительно предназначен для работы.