抽象リスト関数を使用したリストのべき集合

Nov 24 2020

与えられたリストのべき集合を返すラケット機能を作ることは可能ですか？

制約-

明示的な再帰なし
抽象リスト関数を使用する
2行に含まれるコード（実際の要件）

例： (powerset '(1 2))

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

任意の順序で。

私が見つけた他の質問は、まだ明示的な再帰を使用しています。

私のワークフロー：

服用(powerset '(a b c))例として、
まず、最大の整数のリストを取得します (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
それらをそれぞれのバイナリ形式に変換します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))
'（1 2 3）をバイナリのリストにマップします。例：2->'(0,1,0)->'((0,a) (1,b) (0,c))
結果のリストをラムダでフィルタリングして、要素を1のように保持します'((1,b))。
パワーセットを抽出します

私のアプローチの問題

質問が1行にあるという制約には従いません（関数ヘッダーに追加）。

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

宿題にボーナス質問としてこの質問がありましたが、できませんでした。

抽象リスト関数とは何ですか？

以下のような関数foldl、foldrおよびmap

私のボーナスには3つのサブパートが含まれていました

パート1は、私が望む方法でこの関数を単純に作成するように求めました。だから私はそうするために再帰を使用しました
パート2は私が質問したパートです。これは、コードが2行以内になるという制約が追加されたため、特に困難でした。
パート3は最も厳しいはずでした。

ヘルパー関数を記述したり、明示的な再帰を使用したりしないでください（つまり、関数が名前で自分自身を呼び出すことはできません）。抽象リスト関数は使用しないでください。：実際には、ラケットの関数、定数および特殊な形の唯一の次のリストを使用してcons、first、rest、empty?、empty、lambda、とcond。

しかし、面白いことに、私はY-combinatorこれを研究して解決することができました（6時間のコーディング後）。

回答

2 WillNess Nov 25 2020 at 16:57

ボーナスパート2に答えるには：

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

2行、それぞれ80文字未満、最初の行はdefine（つまり、1行）用に予約されています。

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

（2行目に正確に80文字あります）。

これをコーディングする別の方法は、この回答append-mapからのベースのコード（2番目のスニペット）です。これは、のみで再コーディングすると、次のようになります。foldr