Мне было интересно об этом много, и я не нашел удовлетворительных ответов.
Почему (++) "дорогой"? При ленивой оценке мы не будем оценивать выражение типа
xs ++ ys
до необходимости, и даже тогда мы будем оценивать только нужную нам часть, когда мы в ней нуждаемся.
Может кто-нибудь объяснить, что мне не хватает?
Если вы получите доступ ко всему результирующему списку, ленивая оценка не сохранит никаких вычислений. Он будет только задерживать его, пока вам не понадобится каждый конкретный элемент, но в конце вы должны вычислить то же самое.
Если вы пройдете конкатенированный список xs ++ ys, доступ к каждому элементу первой части (xs) добавляет немного постоянных накладных расходов, проверяя, было ли проведено xs или нет.
Итак, это имеет большое значение, если вы связываете ++ влево или вправо.
Если вы сопоставляете n списки длины k с слева, например (..(xs1 ++ xs2) ... ) ++ xsn, то доступ к каждому из первых элементов k займет время O(n), обращаясь к каждый из следующих k будет принимать O(n-1) и т.д. Таким образом, перемещение всего списка займет O(k n^2). Вы можете проверить, что
sum $ foldl (++) [] (replicate 100000 [1])
занимает очень много времени.
Если вы сопоставляете n списки длины k с справа, например xs1 ++ ( ..(xsn_1 ++ xsn) .. ), то вы получите только постоянные накладные расходы для каждого элемента, поэтому перемещение всего списка будет быть только O(k n). Вы можете проверить, что
sum $ foldr (++) [] (replicate 100000 [1])
вполне разумно.
Изменить: Это просто волшебство, скрытое за ShowS. Если вы преобразуете каждую строку xs в showString xs :: String -> String (showString - это просто псевдоним для (++)) и составьте эти функции, то независимо от того, как вы связываете их состав, в конце они будут применяться справа налево - именно то, что нам нужно, чтобы получить линейную сложность времени. (Это просто потому, что (f . g) x есть f (g x).)
Вы можете проверить, что оба
length $ (foldl (.) id (replicate 1000000 (showString "x"))) ""
и
length $ (foldr (.) id (replicate 1000000 (showString "x"))) ""
запустится в разумные сроки (foldr немного быстрее, потому что он имеет меньше накладных расходов при составлении функций справа, но оба являются линейными по количеству элементов).
Это не слишком дорого для себя, проблема возникает, когда вы начинаете комбинировать много ++ слева направо: такая цепочка оценивается как
( ([1,2] ++ [3,4]) ++ [5,6] ) ++ [7,8]
≡ let a = ([1,2] ++ [3,4]) ++ [5,6]
≡ let b = [1,2] ++ [3,4]
≡ let c = [1,2]
in head c : tail c ++ [3,4]
≡ 1 : [2] ++ [3,4]
≡ 1 : 2 : [] ++ [3,4]
≡ 1 : 2 : [3,4]
≡ [1,2,3,4]
in head b : tail b ++ [5,6]
≡ 1 : [2,3,4] ++ [5,6]
≡ 1:2 : [3,4] ++ [5,6]
≡ 1:2:3 : [4] ++ [5,6]
≡ 1:2:3:4 : [] ++ [5,6]
≡ 1:2:3:4:[5,6]
≡ [1,2,3,4,5,6]
in head a : tail a ++ [7,8]
≡ 1 : [2,3,4,5,6] ++ [7,8]
≡ 1:2 : [3,4,5,6] ++ [7,8]
≡ 1:2:3 : [4,5,6] ++ [7,8]
≡ 1:2:3:4 : [5,6] ++ [7,8]
≡ 1:2:3:4:5 : [6] ++ [7,8]
≡ 1:2:3:4:5:6 : [] ++ [7,8]
≡ 1:2:3:4:5:6 : [7,8]
≡ [1,2,3,4,5,6,7,8]
где вы четко видите квадратичную сложность. Даже если вы хотите оценить только до n-го элемента, вам все равно придется пробираться через все те let s. Поэтому ++ infixr, для [1,2] ++ ( [3,4] ++ ([5,6] ++ [7,8]) ) фактически намного эффективнее. Но если вы не будете осторожны при разработке, скажем, простого сериализатора, вы можете легко получить цепочку, подобную той, что указана выше. Это основная причина, по которой начинающих предупреждают о ++.
В стороне, Prelude.++ медленнее по сравнению с, например, Bytestring по той простой причине, что он работает путем перемещения связанных списков, которые всегда имеют субоптимальное использование кэша и т.д., но это не так проблематично; это препятствует достижению C-подобной производительности, но правильно написанные программы, использующие только простые списки, и ++ могут все еще легко конкурировать с аналогичными программами, написанными, например, Python.
Я хотел бы добавить одну или две ответа Петру.
Как он отметил, многократно добавляя списки в начале, довольно дешево, а добавление к дну - нет. Это верно, если вы используете списки haskell. Тем не менее, есть определенные обстоятельства, в которых вы ДОЛЖНЫ добавить к концу (например, вы создаете строку для распечатки). С регулярными списками вы должны иметь дело с квадратичной сложностью, упомянутой в его ответе, но там есть лучшее решение в этих случаях: списки различий (см. также мой вопрос по теме).
Короче говоря, описывая списки как композиции функций вместо конкатенации более коротких списков, вы можете добавлять списки или отдельные элементы в начале или в конце вашего разностного списка, составляя функции в постоянное время. Как только вы закончите, вы можете извлечь обычный список в линейном времени (в количестве элементов).