Алгоритм для объединения двух списков

Question

Я пытаюсь объединить два списка кортежей, x и y. В принципе, у меня есть эти списки:

[("hello", "hi"), ("foo", "baz"), ("this", "that")] 

--and 

[("foo", "bar"), ("hello", "world"), ("goo", "boo")] 

--the result should be 

[("hello", "world"), ("foo", "bar"), ("this", "that")] 

я написал это до сих пор:

merge :: (Eq a) => [(a, b)] -> [(a, b)] -> [(a, b)] 
merge [] _ = [] 
merge _ [] = [] 
merge (x:xs) (y:ys) 
    | fst x == fst y = (fst y, snd y) : merge xs ys 
    | otherwise = (fst x, snd x) : merge xs ys 

Проблема с этим решением является то, что он только сливается, которые тот же индекс. Как я могу эффективно перебирать второй список и объединять его в первый?

Answer 1

Прямо сейчас, если пункт otherwise не совпадает, ваш код отбрасывает и x, и y. Он должен попытаться объединить x с остальной частью ys. Некоторые подсказки: [x] - это список, который вы можете передать merge, и если вы можете подумать о способе разделить и преодолеть проблему, вы можете объединить пару списков с помощью ++.

Правильное решение предполагает объединение результатов различных этапов, и когда вы начнете это делать, эффективным подходом будет хвостовая рекурсия.