В this answer on CodeReview вопрос и ответчик, похоже, проявляют презрение к оператору (++). Это связано с его скоростью (заставляя алгоритм явно работать в O (n^2), где n - длина списка iirc)? Является ли эта предварительная оптимизация, если она не проверена иным образом, так как известно, что Haskell трудно объяснить временную сложность? Должны ли другие избегать оператора (++) в своих программах?Избегание ++ в Haskell
Это зависит.
Рассмотрим выражение
foldl (++) [] list
Это выражение присоединяет список списков в один список, но имеет вышеупомянутую квадратичную сложность. Это происходит потому, что реализация (++) проходит весь левый список и добавляет каждый элемент в правый список (при сохранении правильного порядка, конечно).
Используя правую свертку, мы получаем линейную сложность:
foldr (++) [] list
Это связано с реализацией (++) оператора, который проходит только левый аргумент и подставляет его вправо.
[1,2] ++ [3,4] ++ [5,6]
равно
-- Example as created by foldr
[1,2] ++ ([3,4] ++ [5,6])
== [1,2] ++ [3,4,5,6]
== [1,2,3,4,5,6] -- all good, no element traversed more than once
который только пересекает каждый элемент списка один раз.
Теперь переключение круглых скобок вокруг первых двух списков является более дорогостоящим, так как теперь некоторые элементы пересекаются несколько раз, что неэффективно.
-- Example as created by foldl
([1,2] ++ [3,4]) ++ [5,6]
== [1,2,3,4] ++ [5,6]
== [1,2,3,4,5,6] -- the sublist [1,2] was traversed twice due to the ordering of the appends
В целом, следите за такими случаями, и все должно быть в порядке.
Можно ли это обобщить так, что foldl следует использовать с лево-ассоциативными операторами все время? Что мы делаем с foldl '? EDIT: Если операция является как левой, так и правой ассоциативной, означает ли это, что foldl
@JackBrandt Нет, по крайней мере, не как правило. Представьте себе '(^)' (или '(-)'): Эти операторы дают разные результаты при использовании в левой и правой складках соответственно. Это зависит от того, что вы хотите. 'foldl'' - совсем другое дело, это строгая версия стандартного' foldl' и почти всегда должна быть предпочтительнее, чем 'foldl', за исключением случаев, когда вы явно хотите создать thunks. – ThreeFx
Можете ли вы рассказать о том, почему кто-то захочет создать грозди? Это кажется довольно противоречащим популярному пониманию. Кроме того, математические примеры были действительно полезны для понимания разности b/t сгибов. –
Списки Haskell являются связанными списками, а список добавлений - это операция O (* n *) на строгих языках. Однако в Haskell это не так просто: ленивость позволяет отложить работу до тех пор, пока список не будет использован, эффективно распределяя затраты по длине списка. Как вы заметили, эта лента может затруднить временные и пространственные сложности в Haskell, но я думаю, что тот же совет для других языков относится и к Haskell: сначала пишите для ясности и оптимизируйте скорость, если и только если вам нужно он должен идти быстрее * и * вы профилировали, чтобы найти узкое место. –
это и то, и другое - сложнее рассуждать о вашем коде, это обычно замедляет ваш код совсем немного, и вы можете очень часто работать с ним, но все зависит от обстоятельств и ИМО, ваши вопросы неспецифичны, чтобы быть в хорошей форме для SO – Carsten
@ Карстен: Я немного запутался в вашем замечании относительно «это обычно замедляет ваш код». Хотя это, безусловно, верно в каноническом хвосто-рекурсивном факториальном примере, действительно ли это распространено среди повседневных программ? Я думал, что преимущество в чем-то вроде Haskell над одним из наиболее популярных аутсайдеров, таких как Ruby и Python, - это оптимизация, предоставляемая богатой системой набора текста. Если вы действительно считаете, что мои вопросы не являются достаточно конкретными, как насчет в примере, который я предоставил, сохраните только последний вопрос (это было мое намерение, и я думаю, что ThreeFx выяснил это. –