Join elements with list with some same attributes-CodePudding

I have a list with the type `[(Int, Char, Int)]'. E.g:

[(1, 'x', 1), (1, 'y', 2), (2, 'x', 1)]

The first Int is the number of times the Char appears and the second Int is to differentiate the same char from each other. For example, there could be x1 and x2.

I want to join elements of that list that have the same 2nd and 3rd element. In the case of the list above, it would become [(3, 'x', 1), (1, 'y', 2)] (the first and third tuples from the initial list were added together).

I've looked into zipWith and list comprehensions, but none of them seem to work. Is there any other way that I'm not thinking about that might work here?

CodePudding user response：

First of all, I would suggest working with more meaningful domain types. A 3-tuple of built-in types could mean a lot of different things. By defining a new type and naming the components, you make everything clearer and prevent mistakes like getting the two Ints mixed up:

type Power = Int
type Coefficient = Int
data Exp var = Exp var Power deriving (Show, Eq, Ord)
data Term var = Term Coefficient (Exp var) deriving Show

What you're doing looks a lot to me like combining terms in polynomials, so I've defined types that make sense in that context. You may prefer different names, or a different structure, if you're actually doing something else.

Now you're looking for a function of type [Term Char] -> [Term Char], which groups together like Exps. Generally Data.Map.fromListWith is a great tool for grouping list items together by a key:

import qualified Data.Map as M

combine :: Ord a => [Term a] -> M.Map (Exp a) Coefficient
combine = M.fromListWith ( ) . map toTuple
  where toTuple (Term coef exp) = (exp, coef)

Then all that's left is to re-inflate the Map we've extracted to a list again:

simplify :: Ord a => [Term a] -> [Term a]
simplify = map fromTuple . M.assocs . combine
  where fromTuple (exp, coef) = Term coef exp

And indeed, we get the grouping you hoped for:

*Main> simplify [Term 1 (Exp 'x' 1), Term 1 (Exp 'y' 2), Term 2 (Exp 'x' 1)]
[Term 3 (Exp 'x' 1),Term 1 (Exp 'y' 2)]

CodePudding user response：

The two functions you want to use are Data.List.sortBy and Data.List.groupBy.

If we sort by comparing the second and third elements of each tuple, we get the entries in the list sorted by variable and exponent.

import Data.List

lst = [(1, 'x', 1), (1, 'y', 2), (2, 'x', 1)]
lst' = sortBy (\(_, a, b) (_, a', b') -> (a,b) `compare` (a',b')) lst
-- [(1,'x',1), (2,'x',1), (1,'y',2)]

Now we need to group based on the second and third values. groupBy will not work the way you need on an unsorted list, so don't skip that step.

lst'' = groupBy (\(_, a, b) (_, a', b') -> a == a' && b == b') lst'
-- [[(1,'x',1), (2,'x',1)], [(1,'y',2)]]

Now summing the first elements of the tuples and incorporating the other information is trivial with list comprehensions.

[let (_,x,y) = lst!!0 in (sum [c | (c,_,_) <- lst], x, y) | lst <- lst'', not (null lst)]
-- [(3,'x',1), (1,'y',2)]