Generieren eines Powersets in einer Funktion, keine explizite Rekursion und Verwenden nur der einfachsten Grundelemente in Racket

Nov 19 2020

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 defineauf 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) powersetCode 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, lambdada der Y-Kombinator meines Wissens nur mit einer funktioniert Parameter und combineBedürfnisse 2. Vielleicht ist meine Logik oder Herangehensweise an dieses Problem fehlerhaft. Ich habe nur begrenzte Erfahrung damit, lambdadaher könnte mir auch das Wissen fehlen.

Was ich brauche Hilfe mit: Anregungen , wie die nächsten Schritte, mir zu helfen intergrate combinein powerset, Tipps / Hinweise auf korrekte Logik / Ansatz bereitstellt, oder eine Lösung wäre sehr geschätzt.

Danke im Voraus!

Antworten

1 tfb Nov 19 2020 at 23:37

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 /cNamen 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 combineund 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>)))
4 amalloy Nov 19 2020 at 10:44

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.

2 TgPko4FjN2OAEhnZ Nov 30 2020 at 22:59

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