CODEWITHSUNDEEP
haskell
user1885332
user1885332

Reputation: 107

Adding the first element lists of tuples

I have a structure defined as follows:

type P = [(Int, Int)]

I need to make a function from lists of that structure, add the items that are in first position in the tuple if the following condition is met: that the second element of the tuple is the same.

add :: [P] -> P
add lists = ......

E.g.

add [[(1,2), (3,0)], [(3,1), (7,0)]]

The result would be [(1,2), (3,1), (10.0)].

Since only would add tuples (3.0) with (7.0) because it matches the 0.

Upvotes: 3

Views: 1916

Answers (4)

raymonad
raymonad

Reputation: 949

After merging and sorting (on second element), you can use a variant of group(By) to combine the tuples that have the same second element.

import Data.List
import Data.Ord

add :: [P] -> P
add = combine . sortBy (comparing snd) . concat
  where
    combine []     = []
    combine (x:xs) = (fst x + foldr ((+) . fst) 0 ys, snd x) : combine zs
      where
        (ys, zs) = span ((snd x ==) . snd) xs

Or you can use groupBy to get one list for each distinct snd value and fold each of those lists:

import Data.Function

add' :: [P] -> P
add' = map sumFst . groupBy ((==) `on` snd) . sortBy (comparing snd) . concat
  where
    sumFst = foldr1 $ \(a, b) (x, _) -> (a+x, b)
    -- or, importing Data.Biapplicative from bifunctors package:
    --sumFst = foldr1 $ (+) `biliftA2` const

Upvotes: 1

luqui
luqui

Reputation: 60463

This is a "keyed" operation, and can be solved quite easily with a little help from the standard library. 

import qualified Data.Map as M

Data.Map implements finite associative maps -- i.e. M.Map k a has a set of keys of type k, and to each key it associates a value of type a.

The extremely useful function for this kind of problem is fromListWith:

M.fromListWith :: (a -> a -> a) -> [(k,a)] -> M.Map k a

The second argument, the list of (k,a) tuples, are simply associations, assocating a given key to a given value. The first argument is a combining function, which says what to do to the values if duplicate keys appear in the list.

You must also use M.toList :: M.Map k a -> [(k,a)] which gives you back the list of associations stored in the Map. Here's an example:

ghci> M.toList (M.fromListWith (+) [(1,2), (2,3), (1,4), (3,5)])
[(1,6),(2,3),(3,5)]

Note how the keys are the first elements of the tuples, the opposite of how you have stated your problem. We have combined (1,2) and (1,4) into (1,6). We added because we gave the combining function (+).

This one function solves the brunt of your problem -- the rest is just a little plumbing, which I will leave to you.

Upvotes: 7

user2407038
user2407038

Reputation: 14578

From what I understand, you want to take a list of type [[(Int, Int)]] and sum the first element of any tuple that has the same second element. You can completely disregard that it is a list of lists and just concat right away, unless the structure of the lists can help you determine which elements should be added (but I have not seem any evidence that would indicate that). Then you get the minimum snd, sort the list by the snd values, and recurse through the list, calling span :: (a -> Bool) -> [a] -> ([a], [a]) which takes a predicate and splits a list at the last element which satisfies the predicate. Since the list is sorted, this will capture all of the tuples with same snd. Then we fold over that list of tuples.

add :: [[(Int, Int)]] -> [(Int, Int)]
add list = addT (minBound :: Int) $ sortBy sortF (concat list)
    where sortF (_,x) (_,y)
                | x < y  = LT
                | x > y  = GT
                | x == y = EQ
          addT n list = sumFunc $ span (sndIs n) list
              where sndIs n (_,y) = y == n 
                    sumFunc ([],b)= addT (n+1) b
                    sumFunc (a,[])= [(foldr (\(x,y) (w,v) -> (x+w,y)) (0,0) a)]
                    sumFunc (a,b) = (foldr (\(x,y) (w,v) -> (x+w,y)) (0,0) a):(addT (n+1) b)

then :

> add [[(1,2), (3,0)], [(3,1), (7,0)]]
> [(10,0),(3,1),(1,2)]

The only problem is the complexity is very bad (try add [[(43, minBound :: Int), (10, maxBound :: Int)]]). If you want to make it faster, you should get all the snds first and only call addT with those, if you are likely to be using this function on values that differ greatly.

Upvotes: 1

Sebastian Redl
Sebastian Redl

Reputation: 71899

Let's decompose this problem.

So you have a list of lists

[
  [(1, 0), (2, 1), (3, 2)]
  [(2, 0), (3, 2), (4, 2)]
  [(5, 0), (1, 1), (9, 9)]
]

and you want the sum of the vertical first elements if the second elements are all (all? or some?) the same, and the tuple in the first list otherwise (judging by your example, your spec doesn't actually say what happens).

The first thing you should do is transpose this list, to get something more suited for our calculation.

[
  [(1, 0), (2, 0), (5, 0)]
  [(2, 1), (3, 2), (1, 1)]
  [(3, 2), (4, 2), (9, 9)]
]

Now the problem is essentially a fold over each of these sublists. So you write a function that does it for one of these lists:

collapse :: [(Int, Int)] -> (Int, Int)

And then you map this function over the entire transposed list:

add lists = map collapse $ transpose lists
// or point-free
add = map collapse . transpose

Now you only need to write collapse.

Upvotes: 3

Related Questions