Haskell define Merge using mapReduce

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 <=开发者_JAVA百科 y = x : (merge xs (y:ys))
  | otherwise = y : (merge (x:xs) ys)

Can anyone help me, please? Thanks in advance.

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