Суммировать все элементы с тем же snd списка Haskell

Question

Я пытаюсь сделать полиномиальный калькулятор в Haskell, и у меня возникают некоторые проблемы с умножением. Полиномы вводятся как список коэффициентов, где первый член соответствует x^0, второй соответствует x^1 и т. Д.

Для умножения у меня есть список кортежей, которые указывают на первый элемент, коэффициент к которому они принадлежат, а на втором элементе, они показывают соответствующий коэффициент:

[(0,0),(0,-1),(0,-2),(0,-3),(0,-4),(0,1),(1,0),(2,-1),(3,-2),(4,-3),(0,2),(2,1),(4,0) 

(Это делается чтобы сохранить ссылку на каждый умноженный множитель и коэффициент, которому он принадлежит)

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

Я пробовал с обновлением Data.Sequence, как указано в первом ответе here, но, похоже, не «обновляет» уже созданную Data.Sequence, она возвращает новый каждый раз.

Есть ли способ создать список и обновить его содержимое на основе индекса? Я пытаюсь понять, как решить эту проблему рекурсивно, но я понятия не имею, как это сделать, чтобы любая помощь была оценена.

Answer 1

Вот решение,

import Data.List 
import Data.Function 

combine :: [(Int,Int)] -> [Int] 
combine = map (sum . map snd) . groupBy ((==) `on` fst) . sort 

Прочитайте функцию справа налево, чтобы понять, что он делает.

Вот поломка на более мелкие части, чтобы понять, что

*Main> sort [(0,0),(0,-1),(0,-2),(0,-3),(0,-4),(0,1),(1,0),(2,-1),(3,-2),(4,-3),(0,2),(2,1),(4,0)] 
[(0,-4),(0,-3),(0,-2),(0,-1),(0,0),(0,1),(0,2),(1,0),(2,-1),(2,1),(3,-2),(4,-3),(4,0)] 

Это сортирует список, так что все пары с одинаковым первым элементом вместе. После этого вы также можете использовать fold.

*Main> groupBy ((==) `on` fst) . sort $ [(0,0),(0,-1),(0,-2),(0,-3),(0,-4),(0,1),(1,0),(2,-1),(3,-2),(4,-3),(0,2),(2,1),(4,0)] 
[[(0,-4),(0,-3),(0,-2),(0,-1),(0,0),(0,1),(0,2)],[(1,0)],[(2,-1),(2,1)],[(3,-2)],[(4,-3),(4,0)]] 

Это сочетает в себе все пары с одним и тем же первым элементом.

*Main> combine [(0,0),(0,-1),(0,-2),(0,-3),(0,-4),(0,1),(1,0),(2,-1),(3,-2),(4,-3),(0,2),(2,1),(4,0)] 
[-7,0,0,-2,-3] 

Теперь нам просто нужно вычислить сумму второго элемента в списке списков.