Разбить список и сделать сумму из подсписка?

Question

я ищу решение для своего класса на Haskell.

У меня есть список чисел, и мне нужно вернуть SUM для каждой части списка.Части делятся на 0. Мне нужно использовать функцию FOLDL.

Пример:
начальный список: [1,2,3,0,3,4,0,5,2,1]
sublist [[1,2,3], [3,4], [5,2,1]]
результат [6,7,7]

У меня есть функция для нахождения 0 вначальный список:

findPos list = [index+1 | (index, e) <- zip [0..] list, e == 0] 

(возвращает [4,6] для начального списка из примера)

и функция для создания СУММЫ с FOLDL:

sumList list = foldl (+) 0 list

Но ясовершенно не удалось собрать это воедино: /

---- МОЕ РЕШЕНИЕ
В конце концов я нашел нечто совершенно иное, что вы, ребята, предложили.
Мне потребовался целый день, чтобы сделать это: /

groups :: [Int] -> [Int]
groups list = [sum x | x <- makelist list]

makelist :: [Int] -> [[Int]]
makelist xs = reverse (foldl (\acc x -> zero x acc) [[]] xs)  

zero :: Int -> [[Int]] -> [[Int]]
zero x acc | x == 0 = addnewtolist acc
           | otherwise = addtolist x acc

addtolist :: Int -> [[Int]] -> [[Int]]
addtolist i listlist = (i : (head listlist)) : (drop 1 listlist)

addnewtolist :: [[Int]] -> [[Int]]
addnewtolist listlist = [] : listlist

Answer 1

Я собираюсь дать вам несколько советов, а не полное решение, поскольку это может звучать как домашнее задание.

Мне нравится разбивка шагов, которые вы предложили. Для первого шага (переход от списка чисел с нулевыми маркерами к списку списков) я предлагаю сделать явную рекурсию; попробуйте это для шаблона:

splits []     = {- ... -}
splits (0:xs) = {- ... -}
splits (x:xs) = {- ... -}

Вы также можете злоупотреблять groupBy, если вы осторожны.

Для второго шага похоже, что вы почти на месте; последний шаг, который вам нужен, это взглянуть на функцию map :: (a -> b) -> ([a] -> [b]), которая берет нормальную функцию и запускает ее для каждого элемента списка.

В качестве бонусного упражнения вы можете подумать о том, как вы можете сделать все это за один выстрел одним фолдом. Это возможно - и даже не слишком сложно, если вы проследите, какими должны быть типы различных аргументов для foldr / foldl!

Дополнения после изменения вопроса:

Так как похоже, что вы разработали решение, теперь я чувствую себя комфортно, давая несколько спойлеров. =)

Я предложил две возможные реализации; один, который идет шаг за шагом, как вы предложили, и другой, который идет все сразу. Шаг за шагом это может выглядеть так:

splits []     = []
splits (0:xs) = [] : splits xs
splits (x:xs) = case splits xs of
    []       -> [[x]]
    (ys:yss) -> ((x:ys):yss)

groups' = map sum . splits

Или вот так:

splits' = groupBy (\x y -> y /= 0)
groups'' = map sum . splits'

Полная версия может выглядеть так:

accumulate 0 xs     = 0:xs
accumulate n (x:xs) = (n+x):xs

groups''' = foldr accumulate [0]

Чтобы убедиться, что вы понимаете это, вот несколько упражнений, которые вы можете попробовать:

• Что splits и splits' делают с [1,2,3,0,4,5]? [1,2,0,3,4,0]? [0]? []? Проверьте свои прогнозы в ghci.
• Прогнозируйте, что выводит каждая из четырех версий groups (включая вашу) для таких входных данных, как [] или [1,2,0,3,4,0], а затем проверяйте свой прогноз в ghci.
• Измените groups''', чтобы продемонстрировать поведение одной из других реализаций.
• Измените groups''', чтобы использовать foldl вместо foldr.

Answer 2

Теперь, когда вы решили проблему самостоятельно, я покажу вам немного менее подробную версию. Foldr кажется, на мой взгляд, лучше для этой проблемы *, но, поскольку вы попросили foldl, я покажу вам свое решение с использованием обеих функций.

Кроме того, ваш пример выглядит неверно, сумма [5,2,1] равна 8, а не 7.

Версия foldr.

makelist' l = foldr (\x (n:ns) -> if x == 0 then 0:(n:ns) else (x + n):ns) [0] l

В этой версии мы просматриваем список, если текущий элемент (x) равен 0, мы добавляем новый элемент в список аккумуляторов (n: ns). В противном случае мы добавляем значение текущего элемента к значению переднего элемента аккумулятора и заменяем переднее значение аккумулятора этим значением.

Шаг за шагом:

1. acc = [0], x = 1. Result is [0+1]
2. acc = [1], x = 2. Result is [1+2]
3. acc = [3], x = 5. Result is [3+5]
4. acc = [8], x = 0. Result is 0:[8]
5. acc = [0,8], x = 4. Result is [0+4,8]
6. acc = [4,8], x = 3. Result is [4+3,8]
7. acc = [7,8], x = 0. Result is 0:[7,8]
8. acc = [0,7,8], x = 3. Result is [0+3,7,8]
9. acc = [3,7,8], x = 2. Result is [3+2,7,8]
10. acc = [5,7,8], x = 1. Result is [5+1,7,8] = [6,7,8]

Вот оно!

И версия foldl. Работает так же, как и выше, но создает перевернутый список, поэтому в начале этой функции используется обратный к списку.

makelist l = reverse $ foldl (\(n:ns) x -> if x == 0 then 0:(n:ns) else (x + n):ns) [0] l

* Сворачивание списка справа позволяет использовать функцию cons (:) естественным образом, при использовании моего метода с левой складкой получается перевернутый список. (Вероятно, существует более простой способ сделать версию левого сгиба, о которой я не думал, которая устраняет эту мелочь.)

Answer 3

Как вы уже решили, другая версия:

subListSums list = reverse $ foldl subSum [0] list where
   subSum xs 0 = 0 : xs
   subSum (x:xs) n = (x+n) : xs

(при условии, что в списке есть только неотрицательные числа)