하나의 함수로 powerset 생성, 명시 적 재귀 없음, Racket에서 가장 단순한 기본 요소 만 사용
참고 : 이것은 숙제에 대한 보너스이지만 아무 소용이없는 일을 시도하는 데 너무 오랜 시간을 보냈습니다. 도움을 주시면 감사하겠습니다.하지만 꼭 필요한 것은 아닙니다.
전제 : 번호 목록에 대한 파워 셋을 생성하지만, 어떤 헬퍼, 명시 적으로 재귀를 사용하여 반복, 또는 이외의 기능 / 상수 않고 cons
, first
, rest
, empty?
, empty
, else
, lambda
, 그리고 cond
단 하나를 사용하면서 define
언어 수준 Intermediate Student with Lambda
. powerset의 순서는 중요하지 않습니다.
지금까지 시도한 것 : 이 게시물 덕분에 Y-combinator와 익명 재귀를 발견했습니다 (저자는 최종 목표가 같지만 접근 방식이 다르기 때문에 그의 게시물의 정보가 내 문제를 해결하지 못합니다). 이 답변의powerset
코드 와 함께 다음과 같이 작성했습니다.
(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))))]))
다음을 실행하여이 코드를 테스트하고 있습니다.
(check-expect (powerset '(1 2 3))
(list '(1 2 3) '(2 3) '(1 3) '(3) '(1 2) '(2) '(1) '()))
이 코드는 실행되고 올바른 결과를 생성하지만, 보시다시피 여전히 외부 도우미 함수에 의존하고 있습니다. 내 지식 combine
으로이를 변환하는 방법을 모르겠습니다 lambda
. Y-combinator는 매개 변수 및 combine
필요 2. 아마도이 문제에 대한 나의 논리 또는 접근 방식에 결함이있을 수 있습니다. 나는 경험이 제한되어 lambda
있기 때문에 지식도 놓칠 수 있습니다.
내가 도움이 필요 : 저를 돕고, 다음 단계에로 제안하는 것은 intergrate 수 combine
에 powerset
올바른 논리 / 접근에 힌트 / 단서를 제공, 또는 용액은 많이 주시면 감사하겠습니다.
미리 감사드립니다!
답변
나는 Y를 사용하는 것보다 아래의 트릭을 이해하기 더 쉽다고 생각합니다. 그것은 일종의 U와 관련이 있다고 생각합니다 (또한 Y보다 이해하기 쉽다고 생각합니다).
이것이 '명시 적으로 재귀 적이 지 않다'는 요구 사항을 충족 시키기에는 충분하지 않을 수도 있지만, 그렇다고 생각합니다.
다음과 같이 재귀 할 수 있도록 자신을 자유롭게 사용할 '원하는'함수가있는 경우 :
(define powerset
(λ (set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(powerset (rest set)))])))
그런 다음 추가 인수를받는 함수로 바꿀 수 있습니다.
(define powerset/c
(λ (ps/c set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(ps/c ps/c (rest set)))])))
/c
나는이 트릭을 발견했을 때 나는 연속으로 인수에 대해 생각했기 때문에 이름은,하지만 난의 난 연속성을 정말 무엇인지 몰라서 생각합니다.
그리고 지금 (정의에로 combine
) (powerset/c powerset/c '(x y z))
의 힘 세트를 계산합니다 (x y z)
및 명시 적 재귀가 없습니다.
글쎄, 그것은 추악하지만 이것은 사용하여 쉽게 고칠 수 있습니다.
(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)))])))))
그런 다음 트릭은 combine
이런 식으로 작성 하고 로컬에서 사용하는 것입니다.
(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>)))
Y-combinator는 하나의 매개 변수로만 작동하며 결합은 2가 필요합니다.
다중 인수 함수는 다음 인수를 기다리는 람다를 반환하는 단일 인수 함수로 상상할 수 있습니다. 이 과정을 카레라고합니다. 예를 들어
(define add (x y)
(+ x y))
우리는 그것을 다음과 같이 부를 수 있습니다.
(add 2 2)
충분히 간단합니다. 이제 카레를합시다 :
(define (add x)
(lambda (y)
(+ x y)))
호출에는 약간 다른 구문이 필요하지만 기본 아이디어는 동일합니다.
((add 2) 2)
Y 컴비 네이터에 적합하게 만들고 싶다면 모든 람다에 동일한 개념을 적용 할 수 있습니다.
람다 미적분에서 모든 함수는 카레 단항 함수입니다.
이것은
(define (combine a r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r))
(cons (first r)
(combine a (rest r))))]))
다음과 같이 쓰여질 것입니다.
(λ (combine)
(λ (a)
(λ (r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r))
(cons (first r)
((combine a) (rest r))))]))))
이를 염두에두고 해결책은 다음과 같습니다.
(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)))])))))