Как я пишу функцию длины постоянного пространства в Haskell?
Каноническая реализация length :: [a] -> Int :
length [] = 0
length (x:xs) = 1 + length xs
который очень красив, но страдает от переполнения стека, поскольку оно использует линейное пространство.
Рекурсивная хвостом версия:
length xs = length' xs 0
where length' [] n = n
length' (x:xs) n = length xs (n + 1)
не страдает от этой проблемы, но я не понимаю, как это может работать в постоянном пространстве на ленивом языке.
Не время выполнения, накапливающееся многочисленный (n + 1) преобразователи, поскольку это перемещается через список? Разве это не должно функционировать Haskell, чтобы использовать O (n) пространство и привести к переполнению стека?
(если это имеет значение, я использую GHC),
3 ответа
Да, вы столкнулись с распространенной ошибкой, связанной с накоплением параметров.Обычное лекарство - принудительно выполнить строгую оценку параметра накопления; для этого мне нравится строгий оператор приложения $! . Если вы не устанавливаете строгость, оптимизатор GHC может решить, что эта функция должна быть строгой, но может и нет. Определенно, на это нельзя полагаться - иногда вы хотите, чтобы накопительный параметр вычислялся лениво, и пространство O (N) вполне подойдет, спасибо.
Как мне написать функцию постоянной длины в Haskell?
Как отмечалось выше, используйте строгий оператор приложения для принудительного вычисления параметра накопления:
clength xs = length' xs 0
where length' [] n = n
length' (x:xs) n = length' xs $! (n + 1)
Тип $! равно (a -> b) -> a -> b , и он заставляет вычислять a перед применением функции.
Запускаю вторую версию в GHCi:
> length [1..1000000]
*** Exception: stack overflow
Итак, чтобы ответить на ваш вопрос: Да, она действительно страдает от этой проблемы, как вы и ожидали.
Однако GHC умнее, чем средний компилятор; если вы компилируете с выключенными оптимизациями, он исправит код за вас и заставит его работать в постоянном пространстве.
В более общем смысле, существуют способы принудительного strictness в определенных точках кода Haskell, предотвращающие построение глубоко вложенных бандлов. Обычный пример - foldl против foldl':
len1 = foldl (\x _ -> x + 1) 0
len2 = foldl' (\x _ -> x + 1) 0
Обе функции являются левыми складками, которые делают "одно и то же", за исключением того, что foldl - ленивая, а foldl' - строгая. В результате len1 умирает с переполнением стека в GHCi, а len2 работает корректно.
Функция с хвостовой рекурсией не нуждается в поддержке стека, поскольку значение, возвращаемое функцией, просто будет значением, возвращаемым хвостовым вызовом. Таким образом, вместо создания нового кадра стека текущий кадр используется повторно, а локальные переменные перезаписываются новыми значениями, переданными в хвостовой вызов. Таким образом, каждый n + 1 записывается в то же место, где был старый n , и вы используете постоянное пространство.
Правка - На самом деле, как вы это написали, вы правы, это вызовет переполнение (n + 1) . Легко проверить, просто попробуйте length [1..1000000] .. Вы можете исправить это, заставив его сначала оценить: length xs $! (n + 1) , который будет работать, как я сказал выше.