Haskell define Merge using mapReduce

Question

Я пытаюсь определить merge рекурсивно, используя mapReduce.

mapReduce определяется как

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

Эти соответствия.

turnAroundCond: Условие прекращения остановки.

mapFn: Функция карты принимает входные данные и преобразует их в нечто, которое позднее будет использоваться функцией уменьшения.

wayAheadFn: Функция «вперед-вперед» преобразует входной сигнал в форму, подлежащую передаче на рекурсивный вызов.

reduceFn: Функция уменьшения применяет функцию к (a) тому, что осталось от mapFn, и (a) то, что возвратил рекурсивный вызов.

То, что я сделал до сих пор:

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 

Но когда я бегу merge', это дает мне это:

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

слияние должно дать [1,2,3,4]. сортирует и объединяет два списка

нормальный синтаксис будет

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

Может кто-нибудь помочь мне, пожалуйста? Спасибо заранее.

Answer 1

Предполагая, что отсортированные списки отсортированы, следующая функция совпадает с вашей ванилью 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 

Ваша версия merge' было две вещи неправильно с ним, а именно:

• wayAheadFn: Вы только очищенные от передней части первого списка, а не слезать тот, который был подобран карта уровень.
• turnAroundFn: Это должно возвращать оставшийся список, а не пустой список (это было сделано с (++) для краткости).