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

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

1 голос
/ 09 сентября 2010

Рассмотрим выражение 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 инструкции ... ох), номожет быть легко реализовано в первом случае - назовем это «полу-хвостовой рекурсией».

Ответы [ 3 ]

2 голосов
/ 09 сентября 2010

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

2 голосов
/ 09 сентября 2010

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

1 голос
/ 11 сентября 2010

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

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.Это не приведет к переполнению стека, потому что рекурсивный вызов содержится внутри конструктора (:), который является ленивым.(Кроме того, вы не можете вызвать наращивание thunk в аргументе toBits, принудительно задав значение более позднего элемента списка результатов раньше, потому что в первом случае toBits 0 = [] необходимо оценить аргумент, чтобы определить, является лисписок пуст.)

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

...