CODEWITHSUNDEEP
listhaskellrecursionmerge
David Leites
David Leites

Reputation: 83

Merging Two Lists of Tuples

I need to create a recursive function that merges two lists of tuples together and it starts with a known tuple. The function receives three parameters:

I've tried this:

mergePoints l1 l2 o = o ++ [f | (a, b) <- zip l1 l2, 
                                let f if a < b then f = a, b else f = b, a]

I know I'm not doing it right, but I really don't know how to do it.

The example input and output for the exercise is:

ghci> mergePoints [(1, 3), (1, 4), (5, 5)] [(1, 1), (4, 4)] (0, 0)
[(0.0, 0.0), (1.0, 1.0), (1.0, 3.0), (1.0, 4.0), (4.0, 4.0), (5.0, 5.0)]

Upvotes: 1

Views: 379

Answers (1)

Will Ness
Will Ness

Reputation: 71119

According to your example,

ghci> mergePoints [(1, 3), (1, 4), (5, 5)] [(1, 1), (4, 4)] 
      (0, 0)
[    (0.0, 0.0),                          (1.0, 1.0), 
               (1.0, 3.0), (1.0, 4.0),            (4.0, 4.0), 
                                  (5.0, 5.0)]

each of the two lists is consumed at its own pace, so zip won't fit here, as it consumes its argument lists at the same pace.

The simplest way to code this is with a directly recursive definition with pattern matching that will compare the two head elements and use one or the other, depending on the result of the comparison.

Perhaps you will also need to compare them with the supplied third point, in case it's not the smallest.

So, about your code.

Judging from the example input and output, the points are supposed to come out in order. We can just compare the tuples as they define a lexicographical ordering. You already are doing that. With a small syntactical fix your code is:

mergePoints1 l1 l2 o  =  o ++ [f | (a, b) <- zip l1 l2, 
                                   let f if a < b then f = [a, b] 
                                                  else f = [b, a]]

This is not a valid Haskell. There is no assignment in Haskell, only definition:

mergePoints2 l1 l2 o  =  o ++ [f | (a, b) <- zip l1 l2, 
                                   let f = if a < b then [a, b] else [b, a]]

But this list comprehension creates a list of lists of tuples, as we're creating them as either f = [a,b] or f = [b,a]. Using the points one by one we need to "draw" them from those short lists, one by one, with

mergePoints3 l1 l2 o  =  o ++ [r | (a, b) <- zip l1 l2, 
                                   r <- if a < b then [a, b] else [b, a]]

(using r for "result", instead of f). The last error is that ++ concatenates two lists, but o isn't one. So then it must be

mergePoints4 l1 l2 o  =  [o] ++ merge1 l1 l2

merge1 l1 l2  =  [r | (a, b) <- zip l1 l2, 
                      r <- if a < b then [a, b] else [b, a]]

Now it works, but doesn't do what it's supposed to. And in fact, since its output is still not guaranteed to be ordered, we could even just write this as

merge2 l1 l2  =  l1 ++ l2
  where                     -- the definition of the built-in `++`:
  []     ++ l2  =  l2
  l1     ++ []  =  l1
  (x:t1) ++ l2  =  x : (t1 ++ l2)

or we could pull the elements from both lists with 

merge3 l1 l2  =  l1 ++ l2
  where
  []     ++ l2      =  l2
  l1     ++ []      =  l1
  (x:t1) ++ (y:t2)  =  x : y : (t1 ++ t2)   -- or:
               --   =  x : ((y:t2) ++ t1)

Of course taking out the elements one by one positionally scrambles up their ordering, potentially. Your attempt to rectify this with the merge1 can be re-written as

merge1b l1 l2  =  l1 ++ l2
  where
  []     ++ l2  =  l2
  l1     ++ []  =  l1
  (x:t1) ++ (y:t2)  =  if  x < y  then  x : y : (t1 ++ t2)
                       else             y : x : (t1 ++ t2)

but it still can scramble up the order. We assume our two inputs to be ordered, increasing lists where each element is smaller then the one that follows it in the list. So we just need to use that knowledge, carefully pulling just one of the elements:

merge4 l1 l2  =  l1 ++ l2
  where
  []     ++ l2      =  l2
  l1     ++ []      =  l1
  (x:t1) ++ (y:t2)  =  if   x < y  then  x : (_ ++ (y:t2))
                       else              _ : _

You need to complete this definition by replacing the _s with the actual code.

Bonus question: the usual definition of merge in Haskell prefers its "left" argument over the "right" one, in case of equality of the two elements. Make a one-character edit to the code, to achieve this.

Upvotes: 1

Related Questions