Что такое объединение списков?
Прежде всего, я бы хотел отметить, что требования, предъявляемые к вашему учителю, немного расплывчаты. Более того, объединение на мультимножествах (иначе говоря, множества, которые могут иметь дубликаты, такие как списки) имеют два разных определения в математике ( другой источник ). Я не математик, но вот что я смог почерпнуть из разных интернетов. Вот одно определение:
λ> [1,2,2,3,3,3] `unionA` [1,2,2,2,3] --also called multiset sum
[1,1,2,2,2,2,2,3,3,3,3]
Это просто (++), если вы не беспокоитесь о заказе. А вот другой:
λ> [1,2,2,3,3,3] `unionB` [1,2,2,2,3]
[1,2,2,2,3,3,3] --picks out the max number of occurrences from each list
В дополнение к этой путанице Data.List реализует несколько причудливый третий тип объединения, который обрабатывает свой левый ввод иначе, чем его правый ввод. Вот примерно документация, найденная в комментариях исходный код из union из Data.List:
Функция объединения возвращает объединение списков двух списков. Дубликаты и элементы первого списка удаляются из второго списка, но если первый список содержит дубликаты, результат также будет. Например,
λ> "dog" `union` "cow"
"dogcw"
Здесь у вас есть 3 возможных значения «объединения списков» на выбор. Поэтому, если у вас не было примеров ввода и вывода, я не знаю, какой именно ваш учитель хочет, но, поскольку вы, вероятно, хотите узнать о рекурсии, читайте дальше ...
Удаление дубликатов
Удаление дубликатов из неупорядоченных списков в Haskell может быть выполнено за линейное время , но в решениях используются либо структуры данных с произвольным доступом, такие как Array s, либо что-то, называемое «производительный стабильный неупорядоченный». дискриминаторы », как в пакете discrimination . Я не думаю, что это то, что ищет ваш учитель, так как первое также распространено в императивном программировании, а второе слишком сложно для начинающего Haskell курса. Вероятно, ваш учитель имел в виду, что вы должны просматривать каждый список явно только один раз.
Так что теперь для реального кода. Здесь я покажу вам, как реализовать объединение № 3, начиная с того, что вы написали, и все же проходить списки (явно) только один раз. У вас уже есть базовая схема рекурсии c, но вам не нужно выполнять рекурсию в обоих списках, поскольку мы выбрали вариант № 3 и поэтому возвращаем первый список без изменений.
Фактический код
В приведенном ниже коде вы увидите, что первый список используется в качестве «аккумулятора»: при повторном обращении ко второму списку мы проверяем каждый элемент на наличие дубликата в первом списке, и если нет В дубликате мы добавляем его в первый список.
union [] r = r
union l [] = l
unionR ls (r:rs)
| r `elem` ls = unionR ls rs --discard head of second list if already seen
--`elem` traverses its second argument,
--but see discussion above.
| otherwise = unionR (r:ls) rs --append head of second list
В качестве примечания вы можете сделать его более читабельным, используя сгиб:
union xs = foldl step xs where --xs is our first list; no recursion on it,
--we use it right away as the accumulator.
step els x
| x `elem` els = els
| otherwise = x : els