스키마에서 powerset 구현

Question

Scheme에서 powerset 함수를 두 가지 방법으로 구현하려고합니다. 한 가지 방법은 꼬리 재귀를 사용하고, 나는 그것을이 맘 않았다 잘 작동

(define (powerset list) 
(if (null? list) '(())         ;; if list is empty, its powerset is a list containing the empty list 
    (let ((rest (powerset (cdr list))))     ;; define "rest" as the result of the recursion over the rest of list 
    (append (map (lambda (x) (cons (car list) x)) rest) ;; add the first element of list to the every element of rest (which is a sublist of rest) 
      rest))))         ;; and append it to rest itself (as we can either use the current element (car list), or not 

합니다.

또 다른 방법은 접는 자을 사용하는 것입니다. 그리고 여기에 몇 가지 문제가 있습니다. 다음과 같이 내 현재의 구현은 다음과 같습니다 가난한 결과를 얻을 수

(define (powerset-fr list) 
(foldr (lambda (element result)  ;; This procedure gets an element (and a result); 
     (if (null? result) ;; if starting with the empty list, there is nothing to "fold over". 
      (cons '() (cons element result)) 
      (foldr (lambda (inner-element inner-result) 
        (append (cons element result) inner-result)) 
        '(()) 
        result))) 
    '()        ;; The result is initialized to the empty list, 
    list))       ;; and the procedure is being applied for every element in the first list (list1) 

합니다.

나는 지금까지이 문제를 접근 않았다 방법 곧 설명하려고합니다 : 지정된 세트의 모든 요소를 ​​통해 실행 foldr

합니다. 이러한 각 요소에 대해 powerset에 몇 가지 새로운 요소를 추가해야합니다. 이들 요소는 무엇이되어야합니까? powerset의 기존 요소에 대한 하나의 새로운 요소. 목록의 현재 요소를 powerset의 기존 요소에 추가합니다. 내가 중첩 된 방법으로 두 번 foldr를 사용한다고 생각하는 이유

이

입니다 - 하나의 주어진 목록에있는 모든 항목을 가서하고, 각 항목에 대해 나는 ("결과"에있는 모든 항목을 가서 현재의 파워 셋을 foldr를 사용).

빈 목록 (powerset에 아무 것도 추가되지 않음)의 문제에 직면하여 "if"섹션이 추가되었지만 (foldr뿐만 아니라) 아주 잘 작동하지 않습니다.

나는 그렇게 생각한다. 가까이 다가 갈 수는 있지만 여전히 도전적이므로 모든 도움을 환영합니다. 감사합니다.

Answer 1

해결책은 간단하다, 이중 foldr를 사용할 필요가 없습니다,이 시도 :

(define (powerset-fr lst) 
    (foldr (lambda (e acc) 
      (let ((rst (powerset-fr (cdr lst)))) 
      (append (map (lambda (x) (cons e x)) 
          rst) 
        rst))) 
     '(()) 
     lst)) 

당신의 인터프리터가 append-map 또는 이에 상응하는 무언가를 정의하는 경우, 그 해결책은 조금 짧은 - 결과가있을 것 다른 순서는, 그러나 그것은 중요하지 않습니다

(define (powerset-fr lst) 
    (foldr (lambda (e acc) 
      (append-map (lambda (x) (list x (cons e x))) 
         (powerset-fr (cdr lst)))) 
     '(()) 
     lst)) 

어느 쪽이든, 그것은 예상대로 작동합니다

(powerset-fr '(1 2 3)) 
=> '((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3)())