Schema - Map-Funktion für die Anwendung einer Funktion auf die Elemente in einer verschachtelten Liste

Ich versuche zu schreiben, ein mapping-Funktion in Schema wendet eine Funktion auf jeden Wert in eine geschachtelte Liste.

Beispielsweise (map number? '(3 (2 A) 2 Z) zurückkehren sollte (#t (#t #f) #t #f)

Hier ist, was ich habe, so weit:

(define (map fun lst)
    (if (null? lst) '()
        (if (list? (car lst)) 
            (cons (map fun (car lst)) (map fun (cdr lst)))
                 (cons (fun (car lst)) (map fun (cdr lst))))))

Es funktioniert, wenn sich die verschachtelte Liste ist auf der Vorderseite der Liste. Zum Beispiel (map number? '((3 A) 2 Z)) richtig zurück ((#t #f) #t #f)

Das problem tritt auf, wenn sich die verschachtelte Liste tritt auf, nachdem ein weiteres element der ursprünglichen Liste.
Zum Beispiel (map number? '(3 A (2 Z))) falsch zurück (#t #f #f) [Das Ergebnis sollte (#t #f (#t #f))]

Wie kann ich mein Algorithmus, um dies zu korrigieren?

InformationsquelleAutor ben.coffee | 2011-04-18
  1. 4

    Hier ist meine Lösung---es ist ernst Billig, dass es verwendet das eingebaute map mit der Dekorator-Muster. (Ich weiß, das Schema-Programme mit Hilfe von design patterns? :-O)

    (define (deep-map f l)
  (define (deep x)
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x))))
  (map deep l))

    Sein kann "vereinfachte" sogar noch weiter, indem Sie eine benannte let:

    (define (deep-map f l)
  (let deep ((x l))
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x)))))

    (Die zwei code-snippets sind nicht identisch, aber für diese Frage, sind beide die selben, wenn gegeben, eine Liste als Eingabe.)

    Den null? und pair? Prüfungen (beide O(1)) verwendet werden, um zu vermeiden, mit list? (was ist O(n)).

    • "Ernsthaft Billig" hier falsch ist... Zum Beispiel würde ich erwarten, dass viele Implementierungen zu produzieren besseren code für die einfachere version, die nennt sich direkt, da map ist in der Regel schwer genug ist, um nicht inlined. So, während Sie könnte billiger sein, in einigen Fällen, die behaupten, dass es immer billiger ist falsch.
    • ist nicht bezogen auf Leistungen in diesem Zusammenhang, aber das habe ich der cheater ist Weg aus dem problem. 🙂
    • Scheint gut zu funktionieren. Danke!!!
    • CKY: es ist nicht sogar günstiger in Bezug auf die Wiederverwendung von code -- Sie sparen auf (cons (map ...) (map ...)) das ist ein kleiner Vorteil, aber das Ergebnis ist deutlicher aus Pädagogischer POV... (Und in den Prozess Sie etwas bekommen, das ist mehr generisch, aber das ist natürlich irrelevant für die Frage.)
    • Ich reagierte auf IRC. (Dachte, dass es der einfachste Weg, um alle auf der gleichen Seite.) 🙂
    • Beachten Sie, dass pair? bedeutet nicht, dass eine Liste - das wird nicht für (a (b . c) d) mit "(b . c) ist nicht eine richtige Liste". Sie können nicht verhindern, dass die Zahlung O(n) auf list? seit das ist, was map erfordert

    InformationsquelleAutor Chris Jester-Young
  2. 3

    Ihr code korrekt ist, außer, dass es viel zu ausführlich, als es sein könnte. Hinweis: Sie brauchen, um über nur zwei Fälle: ob lst ist ein pair? oder nicht. Das ist alles. In anderen Worten, der code wird davon ausgegangen, dass die Eingabe wird immer eine Liste, aber es vereinfacht werden könnte, alles zu akzeptieren, und tun, die spezielle rekursive Sache, wenn es ein paar.

    Als für das problem, das Sie sehen-meine Vermutung ist, dass Sie mit Schläger, und deshalb läufst du gegen eine seltsame Fall. Ist dies nicht der Fall ist, dann können Sie hier aufhören zu Lesen.

    Die Sache ist, dass Schläger die Funktion selbst kompilieren, bevor die Bindung zu map gemacht, daher die map Anrufe sind nicht wirklich rekursiv, sondern Sie sind nur Anrufe zu den integrierten map. Später map (Rück-)gebunden, um die resultierende Funktion, aber die rekursiven Aufrufe wurden bereits zusammengestellt. Wenn Sie geben die gleiche definition zweimal, du wirst sehen, dass es wieder beginnt. Die Art und Weise, dies zu lösen, ist einfach nicht zu arbeiten an der REPL, und statt immer zu schreiben, die Definitionen in eine Datei, die beginnt mit einigen #lang <something>.

    • Ich bin mit Huhn. Vielen Dank für Ihren Hinweis, ich werde versuchen, es zu beheben.
    • Gut, ich wusste nicht, dass das Huhn nicht, aber ich wäre nicht überrascht, wenn es das gleiche Problem...
    • Sorry, aber könnten Sie klären, was ein paar ist im Rahmen der Regelung? Ich bin immer noch ein Neuling.
    • Listen in Scheme bestehen aus null oder mehr conses (Paare). Zum Beispiel (list 1) ist das gleiche wie (cons 1 '()) (Liste aus ein paar), und (list 1 2 3) ist das gleiche wie (cons 1 (cons 2 (cons 3 '()))) (Liste bestehend aus drei Paaren). In Scheme können Sie testen, für Paare mit pair?.
    InformationsquelleAutor Eli Barzilay
Schreibe einen Kommentar