CODEWITHSUNDEEP
listhaskellrecursion
Jose_Sunstrider
Jose_Sunstrider

Reputation: 323

Sum all elements with same snd of a list Haskell

I'm trying to do a polynomial calculator in Haskell and I'm having some problems with the multiplication. The polynomials are introduced as a list of coefficients where the first term corresponds to x^0, the second one corresponds to x^1 and so on.

For the multiplication I have a list of tuples which indicate, on the first element, the coefficient they belong to and, on the second element, they show the corresponding coefficient:

[(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)

(This is done to keep reference to each item multiplied and the coefficient it belongs to)

Since it's one of my first steps into functional programming I'm having some trouble on making a list where the first element is the sum of all the second elements from the tuples on the list shown above with 0 as its first element, the second term should be the sum of all second elemts from the tuples in the list shown above with 1 as its first element, and so on.

I tried with Data.Sequence update as pointed in the first answer here but it doesn't seems to 'update' an already created Data.Sequence, It returns a new one each time.

Is there any way to create a list and update its contents based on index? I'm trying to figure how to solve this problem recursively but I have no idea how to do it so any help would be appreciated.

Upvotes: 0

Views: 1451

Answers (1)

Satvik
Satvik

Reputation: 11218

Here is the solution, 

import Data.List
import Data.Function

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

Read the function from right to left to understand what it is doing.

Here is the breakage into smaller parts to understand it

*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)]

This sorts the list, so all pairs with same first element are together. After this you can also use a 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)]]

This combines all the pairs with same first element. 

*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]

Now we just need to calculate the sum of the second element in the list of lists.

Upvotes: 6

Related Questions