Если у меня есть выражение, которое можно вычислить частично, стоит ли избегать хвостовой рекурсии?

Рассмотрим haskell-выражение, подобное следующему: (Простой пример, не говорите мне, каков очевидный способ! ;)

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
  x    = y /= 0

Поскольку эта функция не является хвостовой рекурсией, можно также написать:

toBits :: Integral a => a -> [Bool]
toBits = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits (x : l) m where
    (m,y) = n `divMod` 2
     x    = y /= 0

(Надеюсь, в этом выражении нет ничего плохого)

Я хочу спросить, какое из этих решений лучше. Преимущество первого заключается в том, что его можно очень легко вычислить частично (потому что Haskell останавливается на первом : не нужно), а второе решение (очевидно) является хвостовой рекурсией, но, на мой взгляд, оно должно быть полностью оценивается, пока вы не можете получить что-то.

Фоном для этого является мой парсер Brainfuck (см. мой вопрос по оптимизации), который реализован очень уродливо (различные reverse инструкции... ох), но может быть легко реализован в первом - назовем его "полу-хвост-рекурсия" способ.


recursion lazy-evaluation haskell tail-recursion
person fuz    schedule 09.09.2010    source источник
comment
придирка: if y == 0 then False else True можно записать проще как y /= 0.   -  person kennytm    schedule 09.09.2010

Ответы (3)


arrow_upward
1
arrow_downward

Позвольте мне переименовать вторую версию и исправить несколько опечаток, чтобы вы могли протестировать функции.

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
 x     = y /= 0

toBits2 :: Integral a => a -> [Bool]
toBits2 = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits' (x : l) m where
    (m,y) = n `divMod` 2
    x     = y /= 0

Эти функции на самом деле не вычисляют одно и то же; первый создает список, начинающийся с младшего значащего бита, а второй — со старшего значащего бита. Другими словами, toBits2 = reverse . toBits и фактически reverse могут быть реализованы с точно таким же аккумулятором, который вы используете в toBits2.

Если вам нужен список, начинающийся с младшего значащего бита, toBits — хороший стиль Haskell. Это не приведет к переполнению стека, потому что рекурсивный вызов содержится внутри конструктора (:), который является ленивым. (Кроме того, вы не можете создать преобразователь в аргументе toBits, принудительно задав значение позднего элемента списка результатов раньше, потому что аргумент должен быть оценен в первом случае toBits 0 = [], чтобы определить, пуст ли список. )

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

person Reid Barton    schedule 11.09.2010
comment
Я не был уверен в порядке битов в последнем. Спасибо за уведомление. - person fuz; 12.09.2010

arrow_upward
2
arrow_downward

Я думаю, у тебя все правильно. Первая форма в целом лучше, потому что из нее можно получить полезный результат до завершения вычислений. Это означает, что если «toBits» используется в другом вычислении, компилятор, вероятно, может объединить их, и список, который является результатом «toBits», может вообще никогда не существовать или, возможно, только одна cons-ячейка за раз. Приятно, что первая версия еще и понятнее!

person MtnViewMark    schedule 09.09.2010
comment
Вы можете удалить один из повторяющихся ответов. - person kennytm; 09.09.2010
comment
Другой вопрос: как избежать большого количества стека, связанного с первым? - person fuz; 10.09.2010

arrow_upward
2
arrow_downward

В Haskell ваш первый выбор обычно предпочтительнее (я бы сказал «всегда», но вы всегда ошибаетесь, когда используете это слово). Шаблон накопителя подходит для случаев, когда выходные данные не могут потребляться постепенно (например, приращение счетчика).

person Anthony    schedule 09.09.2010