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

Question

Каноническая реализация 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) thunks при перемещении по списку?Не должна ли эта функция Haskell использовать O (n) место и привести к переполнению стека?

(если это имеет значение, я использую GHC)

Answer 1

Да, вы столкнулись с общей ловушкой с накоплением параметров. Обычное лекарство состоит в том, чтобы заставить строгую оценку накапливающегося параметра; для этого мне нравится строгий оператор приложения $!. Если вы не применяете строгость, оптимизатор GHC может решить, что все в порядке, если эта функция строгая, но это не так. Определенно не стоит полагаться на & mdash; иногда вы хотите накапливающий параметр, который будет оцениваться лениво, а пространство 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 перед применением функции.

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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