(++) оператор и (:) оператор и ленивая оценка

Question

Глава 8 The RealWorldHaskell

globToRegex' (c:cs) = escape c ++ globToRegex' cs

Эта функция не является хвостовой рекурсивной, и в ней говорится, что ответ основан на нестрогой (ленивой) стратегии оценки Haskell.Простое определение оператора (++) заключается в следующем и не является хвостовой рекурсией.

(++) :: [a] -> [a] -> [a]

(x:xs) ++ ys = x : (xs ++ ys)
[]     ++ ys = ys

На строгом языке, если мы оценим "foo" ++ "bar", весь список создается, а затем возвращается.Нестрогая оценка откладывает большую часть работы до тех пор, пока она не понадобится.

Если мы требуем элемент выражения "foo" ++ "bar", первый шаблон определения функции совпадает, и мы возвращаем выражение x : (xs ++ ys). Поскольку конструктор (:) не является строгим, вычисление xs ++ ys может быть отложено: мы генерируем больше элементов результата с любой требуемой скоростью.Когда мы сгенерируем больше результата, мы больше не будем использовать x, поэтому сборщик мусора сможет вернуть его.Поскольку мы генерируем элементы результата по требованию и не держимся за части, с которыми мы закончили, компилятор может оценивать наш код в постоянном пространстве .

(Акцент добавлен.)

Вышеприведенное выделение жирным шрифтом является чем-то важным для Хаскелла, но

1. Как мы можем это понять?
2. Что произошло в базовом файле?
3. "x:(xs ++ ys) будет оцениваться в постоянном пространстве", как?Звучит, что делает хвостовая рекурсия!

Answer 1

Помните, что "foo" это просто синтаксический сахар для 'f':'o':'o':[].

То есть String это просто псевдоним для [Char], который представляет собой просто связанный список символов.

Когда клиентский код потребляет связанный список, он разлагает его обратно на голову и хвост (например, x:xs), что-то делает с головой (при желании), а затем рекурсивно обращается к хвосту.

Когда ваш код создает связанный список, из-за ленивых вычислений все, что ему нужно сделать, это вернуть thunk или пообещать, что он вернет связанный списоккогда попросили.Когда разыменовывается голова, она предоставляется по требованию, а хвост остается в качестве обещания для остальной части списка.

Это должно быть легко увидеть, если список не скопирован или иным образомсохраненный, каждый блок будет использован один раз, а затем отброшен, так что общее пространство хранения будет постоянным.

Многие строгие языки предоставляют механизм (часто называемый generator ) для достижения того же видагенерации ленивых списков, но с ленивой оценкой такие функции «бесплатны» как часть языка - по сути, все списки на Haskell являются генераторами!

Answer 2

Для Haskell характерно полагаться на ленивую оценку, а не на хвостовую рекурсию по сравнению с другими языками FP.Эти два играют связанные роли с точки зрения ограничения использования памяти;какой из них является подходящим механизмом, зависит от создаваемых данных.

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

Если ваш вывод не может быть использован постепенно - возможно, вы вычисляете Int - тогда лень может оставить вас с нежелательной кучкой громов, оценка которых взорвет ваш стек.В этом случае требуется строгий накопитель и хвостовая рекурсия.

Так что, если вы хотите, вы можете тратить кучу на построение большой структуры данных.Если вы ленивый, вы можете отложить упрощение (например, уменьшить 1 + 1 до 2) до кучи только для того, чтобы в конечном итоге испачкать свой стек при выплате пайпера.

Играть сОбе стороны медали, обдумайте foldl' и foldr.

Answer 3

Хвостовая рекурсия будет поддерживать стек постоянным, но на строгом языке куча будет расти при вычислении x : (xs ++ ys).В Haskell, поскольку он не является строгим, x будет освобожден до того, как будет вычислено следующее значение (если только вызывающая сторона не содержит ссылки на x без необходимости), поэтому куча также будет постоянной.