Generieren eines Powersets in einer Funktion, keine explizite Rekursion und Verwenden nur der einfachsten Grundelemente in Racket
Hinweis: Dies ist ein Bonus für Hausaufgaben, aber ich habe viel zu lange damit verbracht, Dinge ohne Erfolg auszuprobieren. Hilfe wird sehr geschätzt, ist aber vermutlich nicht notwendig.
Premise: erzeugt eine Powerset für eine Liste von Zahlen, aber ohne Helfer zu verwenden, explizite Rekursion, Looping oder Funktionen / Konstanten außer cons
, first
, rest
, empty?
, empty
, else
, lambda
, und cond
, bei der Verwendung von nur einer define
auf dem Sprachniveau Intermediate Student with Lambda
. Die Reihenfolge des Powersets spielt keine Rolle.
Was ich bisher versucht habe: Ich habe dank dieses Beitrags den Y-Kombinator und die anonyme Rekursion entdeckt (der Autor hat das gleiche Endziel, aber wir haben unterschiedliche Ansätze, sodass die Informationen in seinem Beitrag mein Problem nicht lösen) powerset
Code in dieser Antwort , und damit habe ich folgendes geschrieben:
(define (powerset aL)
(((lambda (X)
((lambda (proc)
(proc proc))
(lambda (proc)
(X (lambda (arg)
((proc proc) arg))))))
(lambda (subset)
(lambda (lst)
(cond
[(empty? lst) (list empty)]
[else (combine (first aL) (powerset (rest aL)))])))) aL)
(define (combine a r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r)) (cons (first r) (combine a (rest r))))]))
Ich teste diesen Code, indem ich Folgendes ausführe:
(check-expect (powerset '(1 2 3))
(list '(1 2 3) '(2 3) '(1 3) '(3) '(1 2) '(2) '(1) '()))
Dieser Code wird ausgeführt und liefert ein korrektes Ergebnis, aber wie Sie sehen, verlasse ich mich immer noch auf eine externe Hilfsfunktion combine
, und ich habe keine Ahnung, wie ich das in eine umwandeln kann, lambda
da der Y-Kombinator meines Wissens nur mit einer funktioniert Parameter und combine
Bedürfnisse 2. Vielleicht ist meine Logik oder Herangehensweise an dieses Problem fehlerhaft. Ich habe nur begrenzte Erfahrung damit, lambda
daher könnte mir auch das Wissen fehlen.
Was ich brauche Hilfe mit: Anregungen , wie die nächsten Schritte, mir zu helfen intergrate combine
in powerset
, Tipps / Hinweise auf korrekte Logik / Ansatz bereitstellt, oder eine Lösung wäre sehr geschätzt.
Danke im Voraus!
Antworten
Ich finde den Trick unten leichter zu verstehen als Y. Ich denke, er hängt irgendwie mit U zusammen (was ich auch leichter zu verstehen finde als Y).
Es ist möglich, dass dies nicht ausreicht, um die Anforderung zu erfüllen, nicht explizit rekursiv zu sein, obwohl ich denke, dass dies der Fall ist.
Wenn Sie eine Funktion haben, die sich frei verwenden möchte, damit sie wiederkehren kann, wie z.
(define powerset
(λ (set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(powerset (rest set)))])))
Dann können Sie daraus eine Funktion machen, die ein zusätzliches Argument akzeptiert, das sie aufruft:
(define powerset/c
(λ (ps/c set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(ps/c ps/c (rest set)))])))
Die /c
Namen sind, weil ich, als ich diesen Trick entdeckte, über das Argument als Fortsetzung nachdachte, aber ich denke, das liegt daran, dass ich nicht wusste, was Fortsetzungen wirklich sind.
Und jetzt (mit einer Definition für combine
) (powerset/c powerset/c '(x y z))
wird die Potenzmenge von berechnet (x y z)
, und es gibt keine explizite Rekursion.
Nun, das ist hässlich, aber das lässt sich leicht beheben
(define powerset
(λ (set)
((λ (powerset/c)
(powerset/c powerset/c set))
(λ (ps/c set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(ps/c ps/c (rest set)))])))))
Dann besteht der Trick darin, auch so zu schreiben combine
und es dann lokal mit zu verwenden
(define powerset
(λ (set)
((λ (combine)
((λ (powerset/c)
(powerset/c powerset/c set))
(λ (ps/c set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(ps/c ps/c (rest set)))]))))
<combine defn here>)))
Der Y-Kombinator arbeitet nur mit einem Parameter und kombiniert die Anforderungen 2
Jede Funktion mit mehreren Argumenten kann als Funktion mit einem Argument vorgestellt werden, die ein Lambda zurückgibt, das auf das nächste Argument wartet. Dieser Vorgang wird als Currying bezeichnet. Zum Beispiel, wenn wir haben
(define add (x y)
(+ x y))
wir könnten es so nennen
(add 2 2)
Einfach genug. Jetzt lass es uns curry:
(define (add x)
(lambda (y)
(+ x y)))
Das Aufrufen erfordert eine etwas andere Syntax, aber es ist dieselbe Grundidee:
((add 2) 2)
Sie können das gleiche Konzept auf jedes Lambda anwenden, wenn Sie es für den Y-Kombinator geeignet machen möchten.
In der Lambda-Rechnung sind alle Funktionen unäre Curry-Funktionen.
Das heisst
(define (combine a r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r))
(cons (first r)
(combine a (rest r))))]))
würde geschrieben werden als
(λ (combine)
(λ (a)
(λ (r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r))
(cons (first r)
((combine a) (rest r))))]))))
In diesem Sinne ist hier die Lösung:
(define powerset
((λ (y)
((λ (f) (y (λ (x) ((f f) x))))
(λ (f) (y (λ (x) ((f f) x))))))
(λ (ps)
(λ (set)
(cond
[(empty? set) (cons empty empty)]
[else ((((λ (y)
((λ (f) (y (λ (x) ((f f) x))))
(λ (f) (y (λ (x) ((f f) x))))))
(λ (combine)
(λ (a)
(λ (r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r))
(cons (first r)
((combine a) (rest r))))])))))
(first set))
(ps (rest set)))])))))