уменьшить или явную рекурсию?

Question

Недавно я начал читать книгу Пола Грэма «О Лиспе» с другом, и мы поняли, что у нас совершенно разные мнения о редуцировании: я думаю, что он выражает определенный вид рекурсивной формы очень четко и кратко; он предпочитает писать рекурсию очень явно.

Я подозреваю, что мы все правы в одном контексте и не правы в другом, но мы не знаем, где находится черта. Когда вы выбираете одну форму поверх другой, и о чем вы думаете, делая такой выбор?

Чтобы понять, что я подразумеваю под редукцией и явной рекурсией, вот одна и та же функция, реализованная дважды:

(defun my-remove-if (pred lst)
    (fold (lambda (left right)
                  (if (funcall pred left) 
                      right 
                      (cons left right)))
          lst :from-end t))

(defun my-remove-if (pred lst)
    (if lst
        (if (funcall pred (car lst))
            (my-remove-if pred (cdr lst))
            (cons (car lst) (my-remove-if pred (cdr lst))))
        '()))

Боюсь, я создал Schemer (теперь мы Racketeers?), Поэтому, пожалуйста, дайте мне знать, если я испортил синтаксис Common Lisp. Надеюсь, суть будет ясна, даже если код неправильный.

Answer 1

Если у вас есть выбор, вы всегда должны выражать свои вычислительные намерения в максимально абстрактных терминах. Это помогает читателю понять ваши намерения, а компилятору - оптимизировать ваш код. В вашем примере, когда компилятор тривиально знает, что вы выполняете операцию свертывания, благодаря названию, он также тривиально знает, что он может распараллелить конечные операции. Компилятору будет гораздо сложнее понять это, когда вы пишете операции крайне низкого уровня.

Answer 2

В Common Lisp предпочитают функции высшего порядка для обхода структуры данных, фильтрации и других связанных операций над рекурсией.Это также видно из многих предоставляемых функций, таких как REDUCE, REMOVE-IF, MAP и др.

Рекурсия Tail - это а) не поддерживается стандартом, б) может вызываться по-разному с разными компиляторами CL и в) с использованием хвостарекурсия может иметь побочные эффекты на сгенерированный машинный код для окружающего кода.

Часто для некоторых структур данных многие из этих выше операций реализуются с помощью LOOP или ITERATE и предоставляются как функция более высокого порядка.Существует тенденция предпочитать новые языковые расширения (например, LOOP и ITERATE) для итеративного кода, а не использовать рекурсию для итерации.

(defun my-remove-if (pred list)
   (loop for item in list
         unless (funcall pred item)
         collect item))

Вот также версия, в которой используется функция Common Lisp REDUCE:

(defun my-remove-if (pred list)
  (reduce (lambda (left right)
            (if (funcall pred left) 
                right 
              (cons left right)))
          list
          :from-end t
          :initial-value nil))

Answer 3

Я собираюсь взять слегка субъективный вопрос и дать очень субъективный ответ, поскольку Ира уже дала совершенно прагматичный и логичный ответ.: -)

Я знаю, что написание вещей явно высоко ценится в некоторых кругах (ребята из Python делают это частью своего "дзен"), но даже когда я писал Python, я никогда не понимал этого.Я хочу писать на максимально высоком уровне, все время.Когда я хочу написать вещи явно, я использую язык ассемблера.Смысл использования компьютера (и HLL) состоит в том, чтобы заставить его делать эти вещи для меня!

Для вашего my-remove-if примера, редуктор выглядит хорошо для меня (кроме таких схем, какfold и lst :-)).Я знаком с понятием уменьшения, поэтому все, что мне нужно понять, это выяснить ваш f(x,y) -> z.Что касается явного варианта, мне пришлось задуматься на секунду: я должен сам разобраться в цикле.Рекурсия не самая сложная концепция, но я думаю, что она сложнее, чем «функция двух аргументов».

Мне также все равно, что вся строка повторяется - (my-remove-if pred (cdr lst)).Я думаю, что мне нравится Lisp отчасти потому, что я абсолютно безжалостен в DRY, и Lisp позволяет мне быть DRY на осях, которых нет в других языках.(Вы можете добавить еще один LET вверху, чтобы избежать этого, но тогда он будет длиннее и сложнее, что, я думаю, является еще одной причиной, чтобы предпочесть сокращение, хотя в этот момент я мог бы просто рационализировать.)

Я думаю, что, возможно, контексты, в которых ребята из Python, по крайней мере, не любят неявную функциональность, будут:

• , когда никто не может угадать поведение (например, frobnicate("hello, world", True) - чтоИстина означает?), или:
• случаи, когда неявное поведение целесообразно изменить (например, когда аргумент True перемещается, удаляется или заменяется чем-то другим, поскольку нет ошибки времени компиляциив большинстве динамических языков)

Но reduce в Лиспе не справляется с обоими этими критериями: это хорошо понятная абстракция, которую все знают, и которая не изменится, по крайней мере, ни для одноговремя, которое меня волнует.

Теперь я абсолютно уверен, что есть некоторые случаи, когда мне было бы проще прочитать явный вызов функции, но яЯ думаю, вы должны быть очень изобретательны, чтобы придумать их.Я не могу придумать ничего лишнего, потому что reduce и mapcar и друзья действительно хороши абстракций.