Haskell define Merge using mapReduce

Question

I am trying to define merge in recursive way using mapReduce.

mapReduce is defined as

mapReduce mapFn wayAheadFn turnAroundCond turnAroundFn reduceFn xin   
  | (turnAroundCond xin) = turnAroundFn xin
  | otherwise = 
      reduceFn 
        (mapFn xin) 
        (mapReduce mapFn wayAheadFn turnAroundCond turnAroundFn reduceFn (wayAheadFn xin))

These are the correspondences.

turnAroundCond: The termination condition is to stop.

mapFn: The map function takes the input and converts it to something to be used later by the reduce function.

wayAheadFn: The way-ahead function converts the input into the form to be passed to the recursive call.

reduceFn: The reduce function applies a function to (a) what the mapFn left and (a) what the recursive call returned.

What I did so far is :

merge' xs ys =
   mapReduce
      (\(x:_, y:_) -> if x <= y then x else y)        -- mapFn. 
      (\(x:xs, y:ys) -> (xs, y:ys))    -- wayAheadFn. 
      (\(x, y) -> null x || null y)  -- turnAroundCond. 
      (\_ -> [])                     -- turnAroundFn. 
      (:)                            -- reduceFn.
      (xs, ys)                       --input

But when I run merge', it gives me this:

merge' [1,2] [3,4]
[1,2]

merge should give [1,2,3,4]. it sorts and merges two list

normal syntax would be

merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) 
  | x <= y = x : (merge xs (y:ys))
  | otherwise = y : (merge (x:xs) ys)

Can anyone help me, please? Thanks in advance.

Answer 1

Assuming that the lists that are passed in are sorted, the following function is the same as your vanilla merge.

merge' xs ys = 
    mapReduce
        (\(x:_, y:_) -> if x <= y then x else y)                        -- mapFn. 
        (\(x:xs, y:ys) -> if x <= y then (xs, y:ys) else (x:xs, ys))    -- wayAheadFn. 
        (\(x, y) -> null x || null y)                                   -- turnAroundCond. 
        (\(x, y) -> x ++ y)                                             -- turnAroundFn. 
        (:)                                                             -- reduceFn.
        (xs, ys)                                                        -- input

Your version of merge' had two things wrong with it, namely:

• wayAheadFn: You only peeled off the front of the first list, instead of peeling off the one that was picked by the map step.
• turnAroundFn: This should return the list that is left over, and not the empty list (this was done with (++) for brevity).