В качестве упражнения я реализовал функцию карты, используя рекурсию в python, следующим образом:
#map function that applies the function f on every element of list l and returns the new list
def map(l,f):
if l == []:
return []
else:
return [f(l[0])] + map(l[1:],f)
Я знаю, что python не поддерживает оптимизацию хвостовой рекурсии, но как мне написать ту же функцию хвостовой рекурсией?
Пожалуйста, помогите Спасибо
Хвостовая рекурсия означает, что вы должны напрямую возвращать результат рекурсивного вызова без дальнейших манипуляций.
Очевидная рекурсия в map состоит в том, чтобы вычислить функцию для одного элемента списка, а затем использовать рекурсивный вызов для обработки остальной части списка. Однако вам нужно объединить результат обработки одного элемента с результатом обработки остального списка, что требует операции после рекурсивного вызова.
Очень распространенный способ избежать этого — поместить комбинацию внутри рекурсивного вызова; вы передаете обработанный элемент в качестве аргумента и делаете его частью ответственности map за объединение.
def map(l, f):
if l == []:
return []
else:
return map(l[1:], f, f(l[0]))
Теперь это хвостовая рекурсия! Но это тоже явно неправильно. В хвостовом рекурсивном вызове мы передаем 3 аргумента, а map принимает только два аргумента. И тогда возникает вопрос, что нам делать с 3-м значением. В базовом случае (когда список пуст) это очевидно: вернуть список, содержащий переданную информацию. В рекурсивном случае мы вычисляем новое значение, и у нас есть этот дополнительный параметр, переданный сверху, и у нас есть рекурсивный вызов. Новое значение и дополнительный параметр должны быть свернуты вместе, чтобы быть переданными в рекурсивный вызов, чтобы рекурсивный вызов мог быть хвостовым рекурсивным. Все это предполагает следующее:
def map(l, f):
return map_acc(l, f, [])
def map_acc(l, f, a):
if l == []:
return a
else:
b = a + [f(l[0])]
return map_acc(l[1:], f, b)
Что можно выразить более кратко и на языке Python, как показали другие ответы, не прибегая к отдельной вспомогательной функции. Но это показывает общий способ превращения нехвостовых рекурсивных функций в хвостовые рекурсивные функции.
В приведенном выше примере a называется аккумулятором. Общая идея состоит в том, чтобы переместить операции, которые вы обычно выполняете после рекурсивного вызова, в следующий рекурсивный вызов, завершив работу, которую внешние вызовы выполнили "на данный момент", и передав ее в аккумулятор.
Если map можно рассматривать как означающее «вызывать f для каждого элемента l и возвращать список результатов», то map_acc можно понимать как означающее «вызывать f для каждого элемента l, возвращая список результатов в сочетании с a, список уже полученных результатов".
Это будет пример реализации встроенной карты функций в хвостовой рекурсии:
def map(func, ls, res=None):
if res is None:
res = []
if not ls:
return res
res.append(func(ls[0]))
return map(func, ls[1:], res)
Но это не решит проблему python, не поддерживающего TRE, что означает, что стек вызовов каждого вызова функции будет удерживаться все время.
Это кажется хвостовой рекурсией:
def map(l,f,x=[]):
if l == []:
return x
else:
return map(l[1:],f,x+[f(l[0])])
Или в более компактной форме:
def map(l,f,x=[]):
return l and map(l[1:],f,x+[f(l[0])]) or x
my_list = map(empty_list, some_func); my_list.append(5). Теперь каждый последующий пустой список будет отображаться в [5].
- person Ben; 08.08.2011
не совсем ответ, извините, но еще один способ реализовать карту - написать ее в терминах сгиба. если вы попробуете, то обнаружите, что это получается "правильно" только с foldr; использование foldl дает вам обратный список. к сожалению, foldr не хвостовая рекурсия, а foldl. это говорит о том, что в rev_map (карте, которая возвращает перевернутый список) есть что-то более «естественное». к сожалению, я недостаточно образован, чтобы идти дальше (я подозреваю, что вы могли бы обобщить это, чтобы сказать, что нет решения, которое не использует аккумулятор, но я лично не вижу, как привести аргумент) .
