Generowanie powerset w jednej funkcji, bez jawnej rekursji i używanie tylko najprostszych prymitywów w Rackecie
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 define
na 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 powerset
kod 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 combine
i nie mam pojęcia, jak przekonwertować to na a, lambda
ponieważ według mojej wiedzy kombinator Y działa tylko z jednym parametr i combine
potrzeby 2. Być może moja logika lub podejście do tego problemu jest błędne. Mam ograniczone doświadczenie, lambda
więc mogę również brakować wiedzy.
Co muszę pomóc: wszelkie sugestie co do kolejnych kroków, pomagając mi Intergrate combine
się 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
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 /c
nazwy 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 combine
tym, ż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>)))
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.
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)))])))))