Функция вычисления кумулятивных сумм всех префиксов списка

@ASPIRIN93 · Регистрация: 08.05.2014

Студворк — интернет-сервис помощи студентам

Доброго времени суток! Помогите пожалуйста еще раз с задачей:

Написать функцию cumSum PrefixMy :: Num a => [a] -> [a] , которая вычисляет кумулятивные суммы всех префиксов списка.
Например CumSum PrefixMy [1,2,2,4] == [1,3,5,9]

@Catstail · 26.05.2014, 16:16

Haskell
1
2
cumSum :: (Num a) => [a] -> [a]
cumSum x = map (\ k -> sum $ take k x) [1..(length x)]

@Araneo · 26.05.2014, 16:21

Haskell
1
2
cumSum ::Num a => [a] -> [a]
cumSum = reverse.foldl (\xs y -> case xs of {x:sx -> (y+x):xs; _ -> y:[]}) []

@Catstail · 26.05.2014, 16:24

Или так:

Haskell
1
2
cumSum' :: (Num a) => [a] -> [a]
cumSum' x = drop 1 $ foldl (\ a x -> a++[x+last a]) [0] x

@Araneo · 26.05.2014, 16:29

Catstail, И не жалко вам каждый раз, чтоб добавить элемент, пробегать до конца списка?

@Catstail · 26.05.2014, 16:34

Жалко. Но реверс тоже требует ресурсов...

Добавлено через 1 минуту
А в первом решении этого нет.

@ASPIRIN93 · 26.05.2014, 16:34 **[ТС]**

Спасибо огромное за помощь!

@Araneo · 26.05.2014, 16:36

Catstail, Мне всегда казалось, что reverse работает за линейное, а не квадратичное время...

Haskell
1
reverseMy = foldl (flip (:)) []

один проход и готово... Или в библиотечном коде он реализован иначе?

@Catstail · 26.05.2014, 16:39

Реверс работает за линейное время.

@Araneo · 26.05.2014, 16:48

Ну и чтоб закрыть тему...

Haskell
1
2
import Data.List(inits)
cumSum = map sum.drop 1.inits

@Catstail · 26.05.2014, 16:54

А здесь и реверс не нужен:

Haskell
1
2
cumSum2 :: (Num a) => [a] -> [a]
cumSum2 x = drop 1 $ foldr (\ x acc -> (head acc-x):acc) [sum x] x

Добавлено через 2 минуты

Сообщение от Araneo

Data.List(inits)

- а может, в Data.List есть готовая функция для сумм префиксов? Тогда было бы еще короче...

@Araneo · 26.05.2014, 17:11

Сообщение от Catstail

- а может, в Data.List есть готовая функция для сумм префиксов? Тогда было бы еще короче...

нет такой там скорее всего нет... А вообще в чём беда? Тем более как реализовать inits в соседней теме уже написано( причём спрашивал, кажется, тот же человек что и эту тему начал). Так почему я не могу использовать уже написанную функцию?

@Catstail · 26.05.2014, 17:12

Сообщение от Araneo

Так почему я не могу использовать уже написанную функцию?

- можешь... Но будет длиннее.

@Mysterious Light · 26.05.2014, 17:32

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

Сообщение от Catstail

- а может, в Data.List есть готовая функция для сумм префиксов? Тогда было бы еще короче...
- можешь... Но будет длиннее.

1) почему бы и нет, не велосипеды же изобретать на всякую потребу? 2) Prelude Вы используете же, 3) Вы сравнивали длины?

Haskell
1
map sum . foldr (\x r -> [x] : map (x:) r) []

P.S. drop 1 эквивалентно tail.

@Catstail · 26.05.2014, 20:23

Mysterious Light, да... Никак не "подружусь" с бесконечными списками. Вот решение (ненамного длиннее Вашего):

Haskell
1
2
3
4
5
6
7
cumSum4 :: (Num a) => [a] -> [a]
cumSum4 x = map (\ k -> sum $ take (snd k) x) (zip x [1,2..])
 
Main> cumSum4 [1,2,3,4]
[1,3,6,10]
Main> take 20 $  cumSum4 [1,2..]
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210]

Добавлено через 5 минут

Не по теме:

Сообщение от Mysterious Light

почему бы и нет, не велосипеды же изобретать на всякую потребу? Prelude Вы используете же

- постараюсь объяснить, что я имел в виду. Представьте себе шкалу: на одном конце шкалы - все сделанное только "своими руками", на другом - вызов только стандартных функций, полностью решающих поставленную задачу. Оба конца шкалы - "не есть хорошо". Но "велосипедный конец" все-же лучше. И вот, почему: тот, кто изобрел несколько велосипедов, готовое решение усвоит без особых проблем. Обратное - не факт.

@Araneo · 26.05.2014, 22:24

Сообщение от Mysterious Light

P.S. drop 1 эквивалентно tail.

здесь да, а вообще нет.

Haskell
1
2
3
4
Н> drop 1 []
[]
H> tail []
*** Exception: Prelude.tail: empty list

Сообщение от Catstail

- постараюсь объяснить, что я имел в виду. Представьте себе шкалу: на одном конце шкалы - все сделанное только "своими руками", на другом - вызов только стандартных функций, полностью решающих поставленную задачу. Оба конца шкалы - "не есть хорошо". Но "велосипедный конец" все-же лучше. И вот, почему: тот, кто изобрел несколько велосипедов, готовое решение усвоит без особых проблем. Обратное - не факт.

Любая программа на Хаскель, это композиция стандартных функций, чем больше их знаешь, тем лучше. Каждой функции своё место. Нет можно всё сделать и с минимумом... Но зачем. так можно например свёртки запретить, и мап, ведь и правда зачем они если есть рекурсия... и фильтер каждый раз писать самому... Давайте без фанатизма.

@Catstail · 27.05.2014, 11:08

Сообщение от Araneo

чем больше их знаешь, тем лучше

- нет. Лишняя нагрузка на память. Это быстро перестает окупаться. Программирование - это создание кода, а не просто вызов библиотечных функций.

Сообщение от Araneo

можно например свёртки запретить, и мап

- а я этого и не предлагал.

@korvin_ · 27.05.2014, 11:56

Не по теме:

Я бы не рекомендовал называть функцию как cumSum, т.к. в американском английском слово cum имеет несвязанный с темой смысл

Новые блоги и статьи Все статьи Все блоги /
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Данные берутся из. . .

@ASPIRIN93 0 / 0 / 0 Регистрация: 08.05.2014 Сообщений: 6

	Функция вычисления кумулятивных сумм всех префиксов списка 26.05.2014, 14:50. Показов 1500. Ответов 17 Метки нет (Все метки) Доброго времени суток! Помогите пожалуйста еще раз с задачей: Написать функцию cumSum PrefixMy :: Num a => [a] -> [a] , которая вычисляет кумулятивные суммы всех префиксов списка. Например CumSum PrefixMy [1,2,2,4] == [1,3,5,9] 0

@Araneo 650 / 260 / 16 Регистрация: 02.03.2014 Сообщений: 587
	26.05.2014, 16:29
	Catstail, И не жалко вам каждый раз, чтоб добавить элемент, пробегать до конца списка? 0

@Catstail Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	26.05.2014, 16:34
	Жалко. Но реверс тоже требует ресурсов... Добавлено через 1 минуту А в первом решении этого нет. 0

@ASPIRIN93 0 / 0 / 0 Регистрация: 08.05.2014 Сообщений: 6
	26.05.2014, 16:34 [ТС]
	Спасибо огромное за помощь! 0

@Catstail Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	26.05.2014, 16:39
	Реверс работает за линейное время. 0

@korvin_
	27.05.2014, 11:56
	Не по теме: Я бы не рекомендовал называть функцию как cumSum, т.к. в американском английском слово cum имеет несвязанный с темой смысл 0