Mapping in einen Baum von verschachtelten Sequenzen

Question

ich eine Funktion codiert haben, die in einem beliebigen Baum von verschachtelten richtigen Listen abzubilden soll, etwa analog zu der Common Lisp Funktion map-into:

(defun map-into-tree (fn tree) 
    "Destructive mapping into a proper tree." 
    (cond ((null tree) nil) 
     ((atom (car tree)) 
     (setf (car tree) (funcall fn (car tree))) 
     (map-into-tree fn (cdr tree))) 
     (t (map-into-tree fn (car tree)) 
      (map-into-tree fn (cdr tree))))) 

(defparameter *tree* '(1 (2) ((3)) (4 5) (6 ((7))))) 
*TREE* 

(map-into-tree #'1+ *tree*) 
NIL 

*tree* 
(2 (3) ((4)) (5 6) (7 ((8)))) 

Aber ich bin nicht sicher, wie man es für beliebige verschachtelte Sequenzen verallgemeinern soll (wie map-into für Sequenzen). Jede Hilfe wird geschätzt. Hier

Answer 1

könnten Sie rufen map-into ;-)

(defun map-into-tree (function tree) 
    (labels 
     ((recurse (tree) 
     (typecase tree 
      (sequence (map-into tree #'recurse tree)) 
      (t (funcall function tree))))) 
    (recurse tree))) 

... oder äquivalent:

(defun map-into-tree (function tree) 
    (typecase tree 
    (sequence (map-into tree (lambda (u) (map-into-tree function u)) tree)) 
    (t (funcall function tree)))) 

Test:

(map-into-tree #'1+ (copy-tree '((9 10) (8 9 10 11 (12 13)() (11)() 13)))) 
=> ((10 11) (9 10 11 12 (13 14) NIL (12) NIL 14)) 

Ich bin nicht sicher, was mit einem Baum geschehen soll welches Strings enthält: Wollen wir wirklich über jedes Zeichen iterieren? In der Tat ist das, was hier oben getan wird.

Ich stelle auch fest, dass map-in mit Sequenzen arbeitet, die Cons-Zellen enthalten, aber der entsprechende Map-in-Tree nicht, obwohl Map-In verwendet wird.

(1 (2 . 3)) ist eine richtige Liste mit zwei Elementen, nämlich 1 und (2 . 3). Da map-into nicht in Elemente rekurriert, wird nur die Funktion für diese beiden Elemente aufgerufen. In Ihrem Kommentar war dies print, die unsaubere Listen ohne Probleme drucken können.

Das zweite Element ist eine Sequenz: Wenn Sie map-into-tree aufrufen, ruft die Funktion rekursiv map-into mit dieser Sequenz auf, die zufällig eine falsche Liste ist. map-into erwartet eine richtige Sequenz und schlägt daher mit falschen Listen fehl.

Bitte beachten Sie, dass in Ihrer Frage, Sie haben gesagt:

eine Funktion, die in einen beliebigen Baum von verschachtelten richtigen Listen zur Karte soll

Ein Baum mit dem falschen Listen ist kein gültiger Eingang .

Schließlich merke ich, Sie destruktiven Funktionen auf wörtliche Daten aufrufen, etwa so:

(map-into #'print '(1 2)) 

Die angegebene Liste ist eine Konstante, es zur Laufzeit modifizieren ist nicht definiertes Verhalten. Deshalb habe ich zuerst copy-tree in meinem Beispiel verwendet.

würde also diese Arbeit alle Sonderfälle zu handhaben [...]

Da es bereits ein Setzkasten vorhanden ist, genügt es, den Sonderfall der cons zu behandeln; das funktioniert unabhängig von der Art der Wert im cdr Steckplatz gehalten:

(defun map-into-tree (function tree) 
    (labels 
     ((walk (tree) 
     (typecase tree 
      (cons 
      (prog1 tree 
       (setf (car tree) (walk (car tree))) 
       (setf (cdr tree) (walk (cdr tree))))) 
      (sequence (map-into tree #'walk tree)) 
      (t (funcall function tree))))) 
    (walk tree))) 

Answer 2

ist eine mögliche Lösung:

(defun map-into-nested-list (fn nested-list) 
    "Destructive mapping into a nested-list." 
    (cond ((null nested-list) nil) 
     ((atom (car nested-list)) 
     (when (car nested-list) (setf (car nested-list) (funcall fn (car nested-list)))) 
     (map-into-nested-list fn (cdr nested-list))) 
     ((atom (cdr nested-list)) 
     (when (cdr nested-list) (setf (cdr nested-list) (funcall fn (cdr nested-list)))) 
     (map-into-nested-list fn (car nested-list))) 
     (t (map-into-nested-list fn (car nested-list)) 
      (map-into-nested-list fn (cdr nested-list))))) 

(defvar *a* (copy-tree '((9 10) (8 9 10 11 (12 13)() (11)() 13)))) 
;; => *A* 
(map-into-nested-list #'1+ *a*) 
;; => NIL 
*a* 
;; => ((10 11) (9 10 11 12 (13 14) NIL (12) NIL 14)) 

Die Funktion ist ähnlich map-into-tree: Die Hauptunterschiede sind, dass es eine neue, symmetrisch, Niederlassung in den bedingten für den Fall, in dem die cdr ein Atom , und der Test für die "atomaren" Fälle, um die Funktion fn nur anzuwenden, wenn die Atome von NIL abweichen.