How to transform array with duplicates into array with sum of duplicates?

Question

So I've been struggling with this for a few hours now. I have this array [[[4,2]],[[1,2],[1,1]]] and I'd like to transform this array into [[[4,2]],[[1,3]]].

So a function with type f :: [[[Integer]]] -> [[[Integer]]]

Problem

I have a 2d array with inner arrays of length 2: [[x,y] .. ] An inner array is a duplicate if its head element is repeated: [[1,2],[1,1]] If there are duplicates I want to take the sum of all the tails and create a new array with the head as the duplicate value and the sum of duplicates as the tail value: [[1,2],[1,1]] becomes [[[1,3]]

What I have

dup [x,_] [y,_] = x == y

sample = [[[3,5],[2,3],[1,1]],
          [[3,5],[2,3],[4,2],[1,2]],
          [[3,5],[2,3],[4,2],[1,2]],
          [[4,2],[1,2],[1,1]]]

ifDuplicateGroup = map (groupBy dup) sample

getSumOfDups n = map sum [concat $ map tail y | y <- n, (length y) > 1]

sumOfSample = map getSumOfDups sample

Returns:

sumOfSample = [[],[],[],[3]]

Desired Result:

sumOfSample = 
[[[3,5],[2,3],[1,1]],
 [[3,5],[2,3],[4,2],[1,2]],
 [[3,5],[2,3],[4,2],[1,2]],
 [[4,2],[1,3]]]`

this is the best I could work through. Please help! I cant figure out how to get the desired result.

Clarifying a detail: what is supposed to happen if one of your inner lists is something like `[[1,2],[3,4]]`? — duplode, Jan 05 '17 at 07:33
The type should be one list less deep, so `f :: [[[Integer]]] -> [[[Integer]]]`. — Julia Path, Jan 05 '17 at 08:27

score 4 · Answer 1 · edited May 23 '17 at 12:33

(Preliminary note: if your innermost lists always have two elements, you should consider using pairs instead, as in [[(4,2)],[(1,2),(1,1)]]. That would make it unnecessary to deal with impossible cases or to worry about getting lists with wrong lengths that your function can't handle. That said, in what follows I will use the types you originally proposed.)

Though you didn't use it in sumOfSample, you were on the right track with ifDuplicateGroup:

-- I have specialised the functions to Integer; they could be more general.
-- Also note that dup is partial; it only works with lists of two elements.
-- That is the sort of issue you might avoid by using pairs.
dup :: [Integer] -> [Integer] -> Bool
dup [x,_] [y,_] = x == y

-- Making it a function by not supplying 'sample'.
ifDuplicateGroup :: [[[Integer]]] -> [[[[Integer]]]]
ifDuplicateGroup = map (groupBy dup)

ifDuplicateGroup will give you a quadryply nested list -- a list of grouped two-element lists. The next step is changing that back into a triply nested list by squashing the groups and thus removing the duplicates. That can be done through a fold, applied through two layers of mapping (so that the lists being folded are the groups of innermost lists):

-- Combining function for the fold. Note that, just like dup, it is partial.
dedup :: [Integer] -> [Integer] -> [Integer]
dedup [x, acc] [_, y] = [x, acc + y]

-- foldl1' doesn't work with empty lists. That is not a problem here, given
-- that group does not produce empty (inner) lists.
sumOfSample :: [[[[Integer]]]] -> [[[Integer]]]
sumOfSample = map (map (foldl1' dedup)) . ifDuplicateGroup
-- Or, equivalently:
-- sumOfSample = map (map (foldl1' dedup) . groupBy dup)

One caveat is that groupBy only groups adjacent elements, and so you have e.g.:

GHCi> sumOfSample [[[4,2],[4,4]],[[1,2],[2,1],[1,1]]]
[[[4,6]],[[1,2],[2,1],[1,1]]]

If that is not acceptable, working around that is possible, though it may be quite annoying and/or require a somewhat different approach. (Unless you don't care about the order in the "middle layer" inner lists, in case you can simply use ifDuplicateGroup = map (groupBy dup . sort) sample, as Renezee points out in the comments.)

You can work around `groupBy` with `sort` (or the generic `sortBy`), like `map (map (foldl1' dedup) . groupBy dup . sort)`. In this case, `sort` works fine, as it sorts `[[a]]` on elements from head to tail. — Renzeee, Jan 05 '17 at 10:46
@Renzeee Indeed. I considered mentioning that, but given the phrasing used in the question I suspect the order in the "middle layer" inner lists matters for the OP. In any case, I guess it doesn't hurt to add that as a footnote. — duplode, Jan 05 '17 at 17:19

wizzup · Accepted Answer · 2017-01-05T13:49:09.427

Deep list make code hard to understand. Does using type alias help?

This is my ad hoc solution.

import Data.List

type Pair = [Int]

type PairList = [Pair]

sample :: [PairList]
sample = [[[3,5],[2,3],[1,1]],
          [[3,5],[2,3],[4,2],[1,2]],
          [[3,5],[2,3],[4,2],[1,2]],
          [[4,2],[1,2],[1,1]]]

dupList :: PairList -> PairList
dupList xs = ss
  where gs = groupBy dup xs
        ss = map sumGroup gs

sumGroup :: PairList -> Pair
sumGroup xs = [h,t]
  where h = head $ head xs
        t = sum $ concatMap tail xs

dup :: Pair -> Pair -> Bool
dup xs ys = head xs == head ys

main :: IO ()
main = do
  putStrLn "input"
  mapM_ print sample

  putStrLn "output"
  let output = map dupList sample
  mapM_ print output

yeild

>runhaskell listlist.hs  

input                    
[[3,5],[2,3],[1,1]]      
[[3,5],[2,3],[4,2],[1,2]]
[[3,5],[2,3],[4,2],[1,2]]
[[4,2],[1,2],[1,1]]      
output                   
[[3,5],[2,3],[1,1]]      
[[3,5],[2,3],[4,2],[1,2]]
[[3,5],[2,3],[4,2],[1,2]]
[[4,2],[1,3]]

If Pair only have 2 members, eg. [a,b], you should use tuple (a,b) and use fst,snd instead of head,tail

How to transform array with duplicates into array with sum of duplicates?

Problem

What I have

2 Answers2