Ответ 1
Проблема в
((((a ++ b) ++ c) ++ d) ++ e) ++ f
это вложение. Приложения (++) оставлены вложенными, и это плохо; правой вложенности
a ++ (b ++ (c ++ (d ++ (e ++f))))
не будет проблемой. Это потому, что (++) определяется как
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
поэтому, чтобы найти, какое уравнение использовать, реализация должна погрузиться в дерево выражений
(++)
/ \
(++) f
/ \
(++) e
/ \
(++) d
/ \
(++) c
/ \
a b
пока он не узнает, является ли левый операнд пустым или нет. Если он не пустой, его голова берется и всплывает вверх, но хвост левого операнда остается нетронутым, поэтому, когда требуется следующий элемент конкатенации, та же самая процедура начинается снова.
Когда конкатенации вложены в правую часть, левый операнд (++) всегда находится сверху, и проверка на пустоту/всплеск вверх - O (1).
Но когда конкатенации являются вложенными слева, n слоев глубиной, чтобы достичь первого элемента, n узлов дерева должны быть пройдены для каждого элемента результата (из первого списка, n-1 для тех, что из второго так далее.).
Давайте рассмотрим a = "hello" в
hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f
и мы хотим оценить take 5 hi. Итак, во-первых, необходимо проверить,
(((a ++ b) ++ c) ++ d) ++ e
пустой. Для этого необходимо проверить,
((a ++ b) ++ c) ++ d
пустой. Для этого необходимо проверить,
(a ++ b) ++ c
пустой. Для этого необходимо проверить,
a ++ b
пустой. Для этого необходимо проверить,
a
пустой. Уф. Это не так, поэтому мы можем снова всплыть, собирая
a ++ b = 'h':("ello" ++ b)
(a ++ b) ++ c = 'h':(("ello" ++ b) ++ c)
((a ++ b) ++ c) ++ d = 'h':((("ello" ++ b) ++ c) ++ d)
(((a ++ b) ++ c) ++ d) ++ e = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e)
((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f)
и для 'e', мы должны повторить, и для 'l' тоже...
Рисуя часть дерева, пузырьки выглядят так:
(++)
/ \
(++) c
/ \
'h':"ello" b
становится первым
(++)
/ \
(:) c
/ \
'h' (++)
/ \
"ello" b
а потом
(:)
/ \
'h' (++)
/ \
(++) c
/ \
"ello" b
вплоть до вершины. Структура дерева, которое становится правым потомком верхнего уровня (:) наконец, точно такая же, как структура исходного дерева, если только крайний левый список не пуст, когда
(++)
/ \
[] b
узлы свернуты до просто b.
Таким образом, если у вас есть вложенные конкатенации с короткими списками, оставленные вложенными, конкатенация становится квадратичной, потому что получить начало конкатенации - операция O (глубина вложения). В общем, конкатенация левостороннего
(...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1
равно O(sum [i * length a_i | я <- [1.. d]]) для полной оценки.
При использовании списков различий (без оболочки нового типа для простоты описания) не важно, являются ли композиции вложенными
((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++)
или право вложенный. После того, как вы пройдете вложение, чтобы достичь (a ++), этот (++) поднимается в верхнюю часть дерева выражений, поэтому получение каждого элемента a снова равно O (1).
На самом деле, вся композиция связана со списками различий, как только вам потребуется первый элемент,
((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f
становится
((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f
(((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f)
((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f))
(a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f)))
a ++ (b ++ (c ++ (d ++ (e ++ f))))
и после этого каждый список является непосредственным левым операндом верхнего уровня (++) после использования предыдущего списка.
Важным в этом является то, что предваряющая функция (a ++) может начать выдавать свой результат без проверки своего аргумента, так что повторная ассоциация из
($)
/ \
(.) f
/ \
(.) (e ++)
/ \
(.) (d ++)
/ \
(.) (c ++)
/ \
(a ++) (b ++)
с помощью
($)---------
/ \
(.) ($)
/ \ / \
(.) (d ++) (e ++) f
/ \
(.) (c ++)
/ \
(a ++) (b ++)
в
($)
/ \
(a ++) ($)
/ \
(b ++) ($)
/ \
(c ++) ($)
/ \
(d ++) ($)
/ \
(e ++) f
не нужно ничего знать о составных функциях окончательного списка f, так что это просто перезапись O(depth). Тогда на высшем уровне
($)
/ \
(a ++) stuff
становится
(++)
/ \
a stuff
и все элементы могут быть получены в одну стадии. a В этом примере, где у нас было чистое левое вложение, необходима только одна перезапись. Если вместо (например) (d ++) функция в этом месте была левой вложенной композицией, (((g++). (h ++)). (i ++)). (j ++) (((g++). (h ++)). (i ++)). (j ++), повторная ассоциация верхнего уровня оставила бы это нетронутым, и это было бы повторно связано, когда оно становится левым операндом верхнего уровня ($) после использования всех предыдущих списков.
Общая работа, необходимая для всех повторных ассоциаций, составляет O(number of lists), поэтому общая стоимость объединения составляет O(number of lists + sum (map length lists)). (Это означает, что вы также можете добиться плохой производительности, вставив много глубоко вложенных ([] ++).)
newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }
instance Monoid (DiffList a) where
mempty = DiffList (\xs -> [] ++ xs)
(DiffList f) 'mappend' (DiffList g) = DiffList (\xs -> f (g xs))
просто оборачивает это так, чтобы с ним было удобнее обращаться абстрактно.
DiffList (a ++) 'mappend' DiffList (b ++) ~> DiffList ((a ++) . (b++))
Обратите внимание, что это эффективно только для функций, которым не нужно проверять свой аргумент, чтобы начать производить вывод, если произвольные функции заключены в DiffList, у вас нет таких гарантий эффективности. В частности, добавление ((++ a), перенос или нет) может создавать левые вложенные деревья (++) при построении с правым вложением, поэтому вы можете создать поведение конкатенации O(n²) с этим, если конструктор DiffList подвергаются.