Generowanie powerset w jednej funkcji, bez jawnej rekursji i używanie tylko najprostszych prymitywów w Rackecie

Nov 19 2020

Uwaga: to premia za pracę domową, ale zbyt długo próbowałem różnych rzeczy bezskutecznie. Pomoc jest bardzo ceniona, ale myślę, że nie jest konieczna.

Pomieszczenie: wygenerowania PowerSet do listy numerów, ale bez użycia żadnych pomocników, wyraźny rekursji, pętle, funkcje / lub inne niż stałe cons, first, rest, empty?, empty, else, lambda, i cond, z wykorzystaniem tylko jednego definena poziomie języka Intermediate Student with Lambda. Kolejność poweretów nie ma znaczenia.

Czego próbowałem do tej pory: dzięki temu postowi odkryłem kombinator Y i anonimową rekursję (autor ma ten sam cel końcowy, ale mamy inne podejście, więc informacje w jego poście nie rozwiązują mojego problemu), a powersetkod w tej odpowiedzi i napisałem, co następuje:

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

Testuję ten kod uruchamiając:

(check-expect (powerset '(1 2 3)) 
(list '(1 2 3) '(2 3) '(1 3) '(3) '(1 2) '(2) '(1) '()))

Ten kod działa i daje poprawny wynik, ale, jak widać, nadal polegam na zewnętrznej funkcji pomocniczej combinei nie mam pojęcia, jak przekonwertować to na a, lambdaponieważ według mojej wiedzy kombinator Y działa tylko z jednym parametr i combinepotrzeby 2. Być może moja logika lub podejście do tego problemu jest błędne. Mam ograniczone doświadczenie, lambdawięc mogę również brakować wiedzy.

Co muszę pomóc: wszelkie sugestie co do kolejnych kroków, pomagając mi Intergrate combinesię powerset, dostarczając wskazówek / wskazówki do prawidłowego podejścia logicznego / lub rozwiązanie byłoby bardzo mile widziane.

Z góry dziękuję!

Odpowiedzi

1 tfb Nov 19 2020 at 23:37

Poniższa sztuczka jest dla mnie łatwiejsza do zrozumienia niż użycie Y. Myślę, że jest to trochę związane z U (które również wydaje mi się łatwiejsze do zrozumienia niż Y).

Możliwe, że to nie wystarczy, aby spełnić wymóg „nie jest jawnie rekurencyjny”, chociaż myślę, że tak.

Jeśli masz jakąś funkcję, która `` chce '' swobodnie korzystać z siebie, aby mogła się powtarzać, na przykład:

(define powerset
  (λ (set)
    (cond [(empty? set)
           (list empty)]
          [else
           (combine (first set)
                    (powerset (rest set)))])))

Następnie możesz przekształcić to w funkcję, która przyjmuje dodatkowy argument, który wywołuje:

(define powerset/c
  (λ (ps/c set)
    (cond [(empty? set)
           (list empty)]
          [else
           (combine (first set)
                    (ps/c ps/c (rest set)))])))

Te /cnazwy są, bo kiedy odkryłem ten trick Myślałam o argumencie jako kontynuację, ale myślę, że to dlatego, że nie wiedział, co kontynuacje były naprawdę.

A teraz (z definicją dla combine) (powerset/c powerset/c '(x y z))obliczy zestaw potęgi (x y z)i nie ma jawnej rekursji.

Cóż, to brzydkie, ale łatwo to naprawić za pomocą

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

Wtedy cała sztuka polega na combinetym, żeby pisać w ten sposób, a potem używać tego lokalnie, z

(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

Kombinator Y działa tylko z jednym parametrem i wymaga łączenia 2

Dowolną funkcję wieloparametrową można sobie wyobrazić jako funkcję jednoargumentową, zwracającą lambdę oczekującą na następny argument. Ten proces nazywa się curry. Na przykład, jeśli mamy

(define add (x y)
  (+ x y))

moglibyśmy to tak nazwać

(add 2 2)

Wystarczająco proste. Teraz zróbmy curry:

(define (add x)
  (lambda (y)
    (+ x y)))

Wywołanie go wymaga nieco innej składni, ale to ta sama podstawowa idea:

((add 2) 2)

Możesz zastosować tę samą koncepcję do dowolnej lambdy, jeśli chcesz, aby była odpowiednia dla kombinatora Y.

2 TgPko4FjN2OAEhnZ Nov 30 2020 at 22:59

W rachunku lambda wszystkie funkcje są funkcjami jednoargumentowymi.

To znaczy

(define (combine a r)
  (cond
    [(empty? r)  empty]
    [else (cons (cons a (first r))
                (cons (first r) 
                      (combine a (rest r))))]))

zostanie zapisane jako

(λ (combine)
  (λ (a)
    (λ (r)
      (cond
        [(empty? r) empty]
        [else (cons (cons a (first r))
                    (cons (first r) 
                          ((combine a) (rest r))))]))))

Mając to na uwadze, oto rozwiązanie:

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