reduzieren, oder explizite Rekursion?

Question

Ich habe vor kurzem begonnen, durch Paul Graham On Lisp mit einem Freund zu lesen, und wir erkannten, dass wir sehr unterschiedliche Meinungen von reduzieren: Ich denke, es drückt eine bestimmte Art von rekursive Form sehr klar und prägnant aus; er zieht es vor, die Rekursion sehr explizit zu schreiben.

Ich vermute, wir sind jeder in einem Kontext richtig und falsch in einem anderen, aber wir wissen nicht, wo die Linie ist. Wann wählst du eine Form gegenüber der anderen aus und was denkst du über diese Entscheidung?

über klar zu sein, was ich damit meine vs. explizite Rekursion reduzieren, ist hier die gleiche Funktion zweimal umgesetzt: (jetzt sind wir Racketeers)

(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)))) 
     '())) 

Ich fürchte, ich ein Schemer begann so Bitte lassen Sie mich wissen, wenn ich die Common-Lisp-Syntax verpfuscht habe. Hoffentlich ist der Punkt klar, auch wenn der Code falsch ist.

Answer 1

Wenn Sie die Wahl haben, sollten Sie Ihre Rechenabsicht immer in den abstraktesten Begriffen ausdrücken. Dies erleichtert es einem Leser, Ihre Absichten herauszufinden, und es erleichtert dem Compiler, Ihren Code zu optimieren. Wenn in Ihrem Beispiel der Compiler weiß, dass Sie aufgrund Ihrer Benennung eine Faltungsoperation ausführen, weiß er auch trivialerweise, dass er möglicherweise die Blattoperationen parallelisieren kann. Es wäre viel schwieriger für einen Compiler, das herauszufinden, wenn Sie extrem niedrige Operationen schreiben.

Answer 2

Ich werde eine leicht subjektive Frage stellen und eine höchst subjektive Antwort geben, da Ira schon eine vollkommen pragmatische und logische gegeben hat. :-)

Ich weiß, Dinge explizit zu schreiben wird in einigen Kreisen sehr geschätzt (die Python-Jungs machen es zu ihrem "Zen"), aber selbst als ich Python schrieb, habe ich es nie verstanden. Ich möchte jederzeit auf höchstem Niveau schreiben. Wenn ich Dinge explizit schreiben möchte, benutze ich die Assemblersprache. Der Zweck der Verwendung eines Computers (und eines HLL) ist es, diese Dinge für mich zu tun!

Für Ihre my-remove-if Beispiel, die reduzieren Sie sieht gut aus mir (abgesehen von den Scheme-Ismen wie fold und lst :-)). Ich bin vertraut mit dem Konzept von reduzieren, so alles, was ich brauche, um es zu verstehen, ist herauszufinden, Ihre f(x,y) -> z. Für die explizite Variante musste ich eine Sekunde darüber nachdenken: Ich muss die Schleife selbst herausfinden. Rekursion ist nicht das schwierigste Konzept, aber ich denke, es ist schwieriger als "eine Funktion von zwei Argumenten".

Ich interessiere mich auch nicht für eine ganze Zeile wird wiederholt - (my-remove-if pred (cdr lst)). Ich denke, ich mag Lisp teilweise, weil ich absolut rücksichtslos bei DRY bin, und Lisp erlaubt mir, auf Achsen, die andere Sprachen nicht tun, DRY zu sein. (Sie könnten eine andere LET an der Spitze, um dies zu vermeiden, aber dann ist es länger und komplexer, was ich denke, ist ein weiterer Grund, die Reduktion zu bevorzugen, obwohl ich an dieser Stelle könnte nur rationalisieren.)

Ich denke vielleicht die Kontexte, in denen die Python Jungs zumindest implizite Funktionalität nicht mögen würde:

• wenn niemand erwarten konnte, das Verhalten zu erraten (wie frobnicate("hello, world", True) - was bedeutet Wahre bedeuten?), Oder:
• Fälle, in denen es sinnvoll ist für die implizite Verhalten (wie zu ändern, wenn das True Argument bewegt wird, oder entfernt wird, oder durch etwas anderes ersetzt werden, da in den meisten dynamischen Sprachen keine Fehler bei der Kompilierung gibt es)

Aber reduce in Lisp scheitert beide dieser Kriterien: Es ist eine gut verstandene Abstraktion, die jeder kennt, und das wird sich nicht ändern, zumindest nicht auf irgendeiner Zeitskala, die mir wichtig ist.

Jetzt glaube ich absolut sind einige Fälle, in denen es für mich einfacher wäre, einen expliziten Funktionsaufruf zu lesen, aber ich denke, dass Sie ziemlich kreativ sein müssen, um mit ihnen zu kommen. Ich kann mir keine Gedanken machen, denn reduce und mapcar und Freunde sind wirklich gut Abstraktionen.

Answer 3

In Common Lisp bevorzugt man die Funktionen höherer Ordnung für Datenstruktur Traversal, Filterung und andere verwandte Operationen über Rekursion. Das sieht man auch von vielen Funktionen wie REDUCE, REMOVE-IF, MAP und anderen.

Tail Rekursion ist a) nicht vom Standard unterstützt, b) möglicherweise mit verschiedenen CL-Compilern unterschiedlich aufgerufen und c) mit Tail-Rekursion kann Nebenwirkungen auf den generierten Maschinencode für umgebenden Code haben.

Oft werden für bestimmte Datenstrukturen viele dieser obigen Operationen mit LOOP oder ITERATE implementiert und als Funktion höherer Ordnung bereitgestellt. Es gibt eine Tendenz, neue Spracherweiterungen (wie LOOP und ITERATE) für iterativen Code gegenüber der Verwendung von Rekursion für Iteration vorzuziehen.

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

Hier ist auch eine Version, die die Common Lisp Funktion REDUCE verwendet:

(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))