추상 목록 기능을 사용하는 목록의 파워 셋

Question

주어진 목록의 powerset을 반환하는 라켓 함수를 만들 수 있습니까?

---

제약-

1. 명시 적 재귀없이
2. 추상 목록 기능 사용
3. 2 줄에 포함 된 코드 (실제 요구 사항)

---

예 : (powerset '(1 2))

'((1 2) (1) (2) ())

어떤 순서로든.

내가 찾은 다른 질문 은 여전히 ​​명시 적 재귀를 사용합니다.

---

내 워크 플로우 :

1. 촬영 (powerset '(a b c))예를 들어,
2. 먼저 최대 정수 목록을 가져옵니다. (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
3. 그것들을 각각의 이진 형식으로 변환합니다 2->(0,1,0). 그래서 우리는'((0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1))
4. '(1 2 3)을 바이너리 목록에 매핑합니다. 예 :2->'(0,1,0)->'((0,a) (1,b) (0,c))
5. 결과 목록을 람다로 필터링하여 '((1,b)).
6. 파워 셋 추출

---

내 접근 방식의 문제

한 줄에있는 질문의 제약을 따르지 않습니다 (함수 헤더에 추가).

(define (powerset list)
  ( ... )) ;; ie the code is contained in 2 lines of 80 characters

---

이 질문은 보너스 질문으로 내 과제에 있었지만 할 수 없었습니다.

1. 추상 목록 함수는 무엇입니까?

• foldl, foldr및 같은 기능map

1. 내 보너스에는 3 개의 하위 파트가 포함되었습니다.

• 파트 1은 내가 원하는 방식으로이 기능을 간단히 만들도록 요청했습니다. 그래서 재귀를 사용했습니다.
• Part 2는 제가 질문 한 부분입니다. 이것은 코드가 2 줄 이내 라는 제약이 추가 되었기 때문에 특히 어려웠습니다.
• 파트 3은 가장 힘들어 야했습니다.

도우미 함수를 작성하지 말고 명시 적 재귀를 사용하지 마십시오 (즉, 함수가 이름으로 자신을 호출 할 수 없음). 추상 목록 기능을 사용하지 마십시오. 사실, 라켓 기능, 상수 및 특수 형태의 다음과 같은 목록을 사용하여 : cons, first, rest, empty?, empty, lambda,와 cond.

그러나 재미있는 것은, 나는 이것을 공부 Y-combinator하고 해결할 수 있었다 (코딩 6 시간 후에).

Answer 1

보너스 파트 2 :

(define (pws l) 
  (foldr (lambda (e a) (append (map (lambda (x) (cons e x)) a) a)) '(()) l))

두 줄, 각각 80 자 미만, 첫 줄은 define(따라서 한 줄) 예약되어 있습니다.

append허용되지 않는 경우 append ... map조합도 다음과 foldr같이 바꿉니다.

(define (pws-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons (cons e x) r))
                  a a))
         '(()) l))

또는 단축,

(define (pws-fr-1 l) 
  (foldr (lambda (e a) (foldr (lambda (x r) (cons (cons e x) r)) a a)) '(()) l))

(두 번째 줄에 정확히 80 자 포함).

이것을 코딩하는 또 다른 방법 append-map은 이 답변 의 기반 코드 (두 번째 스 니펫)로 다시 코딩 foldr하면

(define (pws-am-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons x (cons (cons e x) r)))
                  '() a))
         '(()) l))

또는 단축,

(define (pws-am-fr1 l) (foldr (lambda (e a)
   (foldr (lambda (x r) (cons x (cons (cons e x) r))) '() a)) '(()) l))

요구 사항을 정확히 충족하거나 충족하지 못할 수 있습니다.