Как написать функцию длины постоянного пространства в 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 может решить, что это нормально для этой функции, но это может и не быть. Определенно, не стоит полагаться на — иногда вы хотите аккумулирующий параметр, который будет оцениваться лениво, и 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

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

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

Answer 3

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

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

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

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

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

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

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