CODEWITHSUNDEEP
haskell
Xui
Xui

Reputation: 31

Merging lists on matching element

I wrote a function to merge two pair lists, in this case each element containing a character and a number. 

mergeTupleList [] blist = blist
mergeTupleList alist [] = []
mergeTupleList (a:ab:as) (b:bn:bs) =
    if ab == b
        then a:[] ++ bn:[] ++ mergeTupleList (a:ab:as) (bs)
        else [] ++ mergeTupleList (as) (b:bn:bs)

listA = [('a',1),('b',1),('a',2),('b',1)] 
listZ = [('b',1),('z',1),('b',1),('z',2)]

It seems that in the 'else' case (b:bn:bs) is not the whole pair list loaded in the beginning, but the short version (bs) because it has been filtered by the 'then' condition. I'm looking for a way to transmit the original (b:bn:bs) list to this function.

input and output:

*Main> mergeTupleList ListA ListZ
[('a',1),('z',1),('a',1),('z',2)]

expected output:

[('a',1),('z',1),('a',1),('z',2),('a',2),('z',1),('a',2),('z',2)]

For clarification :

Perhaps merging is not the adequate word. For every (second) element in ListA existing in the original ListZ write the element following it.

Another example:

ListA = [1,0,3,0]
ListZ = [0,8,0,9]

*Main> mergeTupleList listA listZ 
[1,8,1,9]

expected output: [1,8,1,9,3,8,3,9]

Upvotes: 0

Views: 105

Answers (2)

Xui
Xui

Reputation: 31

This question has already been answered but here is what I figured out, with help from the comments. First we create a groupByTwo function to break listA in lists containing each two elements.

groupByTwo [] = []
groupByTwo list = 
 (take 2 list) : (groupByTwo (drop 2 list))

Then we create a mergeTupleList' function to run the simple mergeTupleList on each element of the list of lists.

mergeTupleList' [] _ = []
mergeTupleList' (a:as) list2 =
  mergeTupleList a list2 ++ mergeTupleList' as list2

Finally a third function called groupTupleMerge to make life easier.

groupTupleMerge list1 list2 =
    mergeTupleList' (groupByTwo list1) list2

Upvotes: 0

trevor cook
trevor cook

Reputation: 1600

I have a series of solutions for you. First, the following produces the desired output. I think this is as specified, but note that mergeTupleList' no longer returns the bList in it's first line. That wasn't performing as expected, although your description leads me to believe that you do want that.

The secret to this solution is the inclusion of the subfunction tupleAB, which does all the tupling for the first a:ab, consuming the entire bs list before evaluating the next ab pair for the whole bs list.

mergeTupleList' [] _ = []
mergeTupleList' alist [] = []
mergeTupleList' (a:ab:as) bbnbs =
  let
    tupleAB (b:bn:bs) = 
      if ab == b
         then a:[] ++ bn:[] ++ tupleAB bs 
         else [] ++ tupleAB bs 
    tupleAB _ = []
  in tupleAB bbnbs ++ mergeTupleList' as bbnbs

Next is a slight cleanup of all those naughty :[] ++

mergeTupleList'' [] _ = []
mergeTupleList'' alist [] = []
mergeTupleList'' (a:ab:as) bbnbs =
  let
    tupleAB (b:bn:bs) = 
      if ab == b
         then a : bn : tupleAB bs 
         else tupleAB bs 
    tupleAB _ = []
  in tupleAB bbnbs ++ mergeTupleList'' as bbnbs

The above solutions have some dangling case expressions. What do we do in the case where one of the lists isn't even numbered? If we instead turn each first two terms into a pair, we have lists of pairs (of pairs). This conversion function changes your lists.

pairListCvt :: [a] -> [(a,a)]
pairListCvt (a:b:cs) = (a,b) : pairListCvt cs
pairListCvt (a:[]) = [] --maybe should be error?
pairListCvt _ = []

listACvt = pairListCvt listA 
listZCvt = pairListCvt listZ

Now, rewritten again, we have less unmatched patterns, and so probably less chance for error. This is an example of selecting a type to provide a bit of safety; type safety.

mergeTupleList''' [] _ = []
mergeTupleList''' alist [] = []
mergeTupleList''' ((a,ab):as) bbnbs =
  let
    tupleAB ((b,bn):bs) = 
      if ab == b
         then (a , bn) : tupleAB bs 
         else mergeTupleList''' as ((b,bn):bs)
    tupleAB _ = []
  in tupleAB bbnbs ++ mergeTupleList''' as bbnbs

Next, since we are using each term in alist to create terms from blist, I use a map here.

mergeTupleList'''' as bbns = 
  let
    tupleAB ((b,bn):bs) (a,ab) = 
      if ab == b
         then (a, bn) : tupleAB bs (a,ab)
         else tupleAB bs (a,ab)
    tupleAB [] _ = []
  in concat $ map (tupleAB bbns) as

Finally, the inner tupleAB can be formulated as a fold; something that incrementally builds a data structure through an element-by-element decomposition of the list. The core logic of that fold is now held in f.

mergeTupleList''''' as bbns = 
  let
    tupleAB bs aab = foldr (f aab) [] bs
    f (a,ab) (b,bn) acc
       | ab == b        = (a,bn) : acc
       | otherwise      = acc
  in concat $ map (tupleAB bbns) as

I prefer where bindings to let bindings, stylistically. Alghouth there are memory performance issues I don't understand concerning the choice.

mergeTupleListW as bbns = concat $ map (tupleAB bbns) as
  where
    tupleAB bs aab = foldr (f aab) [] bs
    f (a,ab) (b,bn) acc
       | ab == b        = (a,bn) : acc
       | otherwise      = acc

Extra Credit. He is the function written as a List monad.

mergeTupleListM as bbns = 
  do a <- as
     tupleAB bbns a
  where
    tupleAB bs aab = foldr (f aab) [] bs
    f (a,ab) (b,bn) acc
       | ab == b        = (a,bn) : acc
       | otherwise      = acc

Upvotes: 1

Related Questions