Эффективно объединить два списка

Question

В настоящее время я изучаю Haskell и работаю с List.

Согласно HaskellWiki , если бы я хотел объединить два списка, я бы написал:

list1 ++ list2 

Однако, согласно этому ответу, использование ++ в большом списке было бы неэффективным.

Из исследования я наткнулся на эту страницу SO , но этот вопрос требует особого требования для вывода List.

Что я пытался:

Предположим, если бы у меня было два списка чисел (для этого примера предположим, что оба списка достаточно велики, чтобы использование ++ было бы неэффективно, как описано в ответе SO):

 oldNumbers = [1,5,14,22,37]
 newNumbers = [3,10,17,27,34,69]
 allNumbers = oldNumbers:newNumbers

Как вы можете видеть, я пытался добавить oldNumbers к заголовку newNumbers с намерением отменить его позже (не обращая внимания на то, что allNumbers пока будет неупорядоченным, это упражнение для другого дня).

Как вы, наверное, догадались, он выдал ошибку

error:
    * Non type-variable argument in the constraint: Num [a]
      (Use FlexibleContexts to permit this)
    * When checking the inferred type
        allNumbers :: forall a. (Num a, Num [a]) => [[a]]

Итак, как указано в заголовке, как мне эффективно объединить два списка?

Answer 1

Согласно HaskellWiki , если бы я хотел объединить два списка, Я бы написал:

list1 ++ list2 

Однако, согласно этому ответу , использование ++ в большом списке будет неэффективен.

Я думаю, вам нужно учитывать контекст в этом ответе. Если мы добавим два списка a и b с (++), то он добавит два списка в O (m) (с m длиной списка). Так что это с точки зрения сложности времени эффективно. Нельзя построить такой односвязный список более эффективным, чем этот.

@ melpomene фактически указывает на популярную ошибку, которую совершают люди, незнакомые с Haskell: они добавляют single элемент в конец списка. Опять же, если вы хотите добавить только один элемент в список, это не проблема. Это проблема, если вы хотите добавить n элементов таким образом в список, поэтому, если вы каждый раз добавляете один элемент в список, и вы делаете это n раз, тогда алгоритм будет O (n ² ) .

Короче говоря, с точки зрения сложности времени, (++) не медленный, когда вы добавляете два списка вместе, и не медленный, когда вы добавляете к нему одноэлементный список. Однако, с точки зрения асимптотического поведения, обычно более эффективны способы, чем повторное добавление списка с одним элементом в список, поскольку тогда первый операнд обычно становится больше, и для каждой итерации требуется O (n) . время только для добавления одного элемента в список. Как правило, в этом случае можно использовать рекурсию для хвостового элемента списка или, например, построить список в обратном порядке.

(++), таким образом, не является «внутренне» неэффективным, используя его способами, для которых он не предназначен, вы можете получить неэффективное поведение.

Примером, где ++ будет довольно медленным, является следующая функция, которая выполняет «отображение»:

badmap :: (a -> b) -> [a] -> [b]
badmap f = go []
    where go temp [] = temp
          go temp (x:xs) = go (temp ++ [f x]) xs

Здесь есть две проблемы:

1. это не ленивый, он требует, чтобы оценить весь список, прежде чем это сможет испустить первый элемент; и
2. он будет работать за квадратичное время, поскольку для каждого элемента в списке ввода потребуется все больше и больше времени для добавления этого элемента.

Более эффективный способ реализации карты:

goodmap :: (a -> b) -> [a] -> [b]
goodmap f = go
    where go (x:xs) = f x : go xs
          go [] = []

Answer 2

Если вы хотите эффективно добавлять произвольные списки, используйте другую структуру данных! Например, Data.Seq оптимизирован для эффективного добавления.

https://www.stackage.org/haddock/lts-12.19/containers-0.5.11.0/Data-Sequence.html#v:-62--60-

Answer 3

Нет ничего плохого в добавлении двух списков с одноразово ++, какими бы длинными они ни были.

Ответ, который вы цитируете, (по праву) говорит о повторном добавлении одноэлементных списков с ++ [x], являющимися "плохими".