Как мне написать функцию постоянной длины в 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)


lazy-evaluation haskell
person Bill    schedule 06.05.2010    source источник

Ответы (3)


arrow_upward
15
arrow_downward

Да, вы столкнулись с распространенной ошибкой с накоплением параметров. Обычное лекарство - принудительно выполнить строгую оценку параметра накопления; для этого мне нравится строгий оператор приложения $!. Если вы не устанавливаете строгость, оптимизатор GHC может решить, что эта функция должна быть строгой, но может и нет. Определенно, на это нельзя полагаться. Иногда вы хотите, чтобы накапливаемый параметр вычислялся лениво, и пространство O (N) вполне подойдет, спасибо.

Как мне написать функцию постоянной длины в Haskell?

Как отмечалось выше, используйте оператор strict приложения для принудительной оценки параметра накопления:

clength xs = length' xs 0
  where length' []     n = n
        length' (x:xs) n = length' xs $! (n + 1)

Тип $! - (a -> b) -> a -> b, и он заставляет вычислить a перед применением функции.

person Norman Ramsey    schedule 06.05.2010

arrow_upward
12
arrow_downward

Запуск второй версии в GHCi:

> length [1..1000000]
*** Exception: stack overflow

Итак, чтобы ответить на ваш вопрос: да, он действительно страдает от этой проблемы, как вы и ожидаете.

Однако GHC умнее среднего компилятора; если вы компилируете с оптимизацией, это исправит код за вас и заставит его работать в постоянном пространстве.

В более общем смысле, существуют способы принудительного применения строгости в определенных точках кода Haskell, предотвращая создание глубоко вложенных преобразователей. Обычный пример - foldl vs. foldl':

len1 = foldl (\x _ -> x + 1) 0
len2 = foldl' (\x _ -> x + 1) 0

Обе функции являются левыми свертками, которые делают «одно и то же», за исключением того, что foldl является ленивым, а foldl' - строгим. В результате len1 умирает при переполнении стека в GHCi, а len2 работает правильно.

person C. A. McCann    schedule 06.05.2010

arrow_upward
1
arrow_downward

Функция с хвостовой рекурсией не нуждается в поддержке стека, поскольку значение, возвращаемое функцией, просто будет значением, возвращаемым хвостовым вызовом. Таким образом, вместо создания нового кадра стека текущий кадр используется повторно, а локальные переменные перезаписываются новыми значениями, переданными в хвостовой вызов. Таким образом, каждый n+1 записывается в то же место, где был старый n, и вы используете постоянное пространство.

Изменить - на самом деле, как вы это написали, вы правы, это вызовет (n+1)s и вызовет переполнение. Легко протестировать, просто попробуйте length [1..1000000] .. Вы можете исправить это, заставив его сначала оценить: length xs $! (n+1), который затем будет работать, как я сказал выше.

person tzaman    schedule 06.05.2010
comment
Код вопрошающего действительно переполняет стек. Вообще говоря, хвостовая рекурсия в Haskell не делает то, что вы ожидаете, а ленивые хвостовые рекурсивные функции часто являются ошибками. См. Здесь: haskell.org/haskellwiki/Foldr_Foldl_Foldl 'Практическое правило: либо сделайте его строгим, как foldl' или преобразовать его в конструктор типа foldr. - person C. A. McCann; 06.05.2010
comment
Ой, орехи. Очевидно, Markdown не любит апострофы в конце URL-адреса. Попробуем еще раз: haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 - person C. A. McCann; 06.05.2010