하나의 함수로 powerset 생성, 명시 적 재귀 없음, Racket에서 가장 단순한 기본 요소 만 사용

Nov 19 2020

참고 : 이것은 숙제에 대한 보너스이지만 아무 소용이없는 일을 시도하는 데 너무 오랜 시간을 보냈습니다. 도움을 주시면 감사하겠습니다.하지만 꼭 필요한 것은 아닙니다.

전제 : 번호 목록에 대한 파워 셋을 생성하지만, 어떤 헬퍼, 명시 적으로 재귀를 사용하여 반복, 또는 이외의 기능 / 상수 않고 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 수 combinepowerset올바른 논리 / 접근에 힌트 / 단서를 제공, 또는 용액은 많이 주시면 감사하겠습니다.

미리 감사드립니다!

답변

1 tfb Nov 19 2020 at 23:37

나는 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>)))
4 amalloy Nov 19 2020 at 10:44

Y-combinator는 하나의 매개 변수로만 작동하며 결합은 2가 필요합니다.

다중 인수 함수는 다음 인수를 기다리는 람다를 반환하는 단일 인수 함수로 상상할 수 있습니다. 이 과정을 카레라고합니다. 예를 들어

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

우리는 그것을 다음과 같이 부를 수 있습니다.

(add 2 2)

충분히 간단합니다. 이제 카레를합시다 :

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

호출에는 약간 다른 구문이 필요하지만 기본 아이디어는 동일합니다.

((add 2) 2)

Y 컴비 네이터에 적합하게 만들고 싶다면 모든 람다에 동일한 개념을 적용 할 수 있습니다.

2 TgPko4FjN2OAEhnZ Nov 30 2020 at 22:59

람다 미적분에서 모든 함수는 카레 단항 함수입니다.

이것은

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