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.


Show source
| haskell   | list   2017-01-05 06:01 2 Answers

Answers to How to transform array with duplicates into array with sum of duplicates? ( 2 )

  1. 2017-01-05 09:01

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

  2. 2017-01-05 14:01

    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

Leave a reply to - How to transform array with duplicates into array with sum of duplicates?

◀ Go back