数字列表

Question

我想编写Racket函数的find-subsets。该函数将生成不带辅助函数的数字列表的子集列表，并且仅使用lambda，cond，cons，rest，rest，first和其他原始函数。

例如，应满足以下检查要求：

(check-expect (find-subsets '(2 2 3 3)) '(() (2) (3) (2 2) (2 3) (3 3) (2 2 3) (2 3 3)
    (2 2 3 3)))
(check-expect (find-subsets '(1 2 3)) '(() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)))

[基本上，此函数产生一组数字的幂集，但是我不确定它如何产生所有元素，而无需递归。

Answer 1

#lang racket

(define-syntax-rule (my-let ([var val]) body)
  ((λ (var) body) val))

(define-syntax-rule (Y e)
  ((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
           (λ (x) (f (λ (y) ((x x) y))))))
   e))

(define-syntax-rule (define/rec f e)
  (define f (Y (λ (f) e))))

(define/rec my-append
  (λ (l1)
    (λ (l2)
      (cond [(empty? l1) l2]
            [else (cons (first l1) ((my-append (rest l1)) l2))]))))

(define/rec my-map
  (λ (f)
    (λ (l)
      (cond [(empty? l) empty]
            [else (cons (f (first l)) ((my-map f) (rest l)))]))))


(define/rec my-power-set
  (λ (set)
    (cond [(empty? set) (cons empty empty)]
          [else (my-let ([rst (my-power-set (rest set))])
                        ((my-append ((my-map (λ (x) (cons (first set) x))) rst))
                         rst))])))

摘要：我从here和curried中获得了幂集的标准定义。然后，我将let，append和map替换为my-let，my-append和my-map。我将Y combinator定义为Y宏，并将帮助器define/rec定义为递归函数。然后，我使用define/rec宏定义了my-append和my-map（请注意，它们也被管理）。我们可以手动替换所有内容以获得此信息：

(define my-power-set
  ((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
           (λ (x) (f (λ (y) ((x x) y))))))
   (λ (my-power-set)
     (λ (set)
       (cond [(empty? set) (cons empty empty)]
             [else
              ((λ (rst)
                 ((((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
                            (λ (x) (f (λ (y) ((x x) y))))))
                    (λ (my-append)
                      (λ (l1)
                        (λ (l2)
                          (cond [(empty? l1) l2]
                                [else (cons (first l1)
                                            ((my-append (rest l1)) l2))])))))
                   ((((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
                              (λ (x) (f (λ (y) ((x x) y))))))
                      (λ (my-map)
                        (λ (f)
                          (λ (l)
                            (cond [(empty? l) empty]
                                  [else (cons (f (first l))
                                              ((my-map f) (rest l)))])))))
                     (λ (x) (cons (first set) x))) rst))
                  rst))
               (my-power-set (rest set)))])))))

Answer 2

我不明白您的要求。我认为您已经使用了递归和辅助函数。

不使用辅助函数，显式递归或抽象列表函数。

（（定义（给定子集给定的len lon len）...

（定义（find-subsets2 ... [否则（cons（find-subsets2 ...

请检查您是否有矛盾。

#lang racket
; if we can use "recursion"(not really recursion process) and "auxiliary function"
; use "cond function" define basic "append" and "map" and "foldr" is pretty easy

(define (connect n lst)
  (append (map (λ (x) (cons n x)) lst) lst))

(define (powerset lst) (foldr connect '(()) lst))

;;; TEST
(powerset '(1 2 3 4))

; If written like this. We still need to define our own map append foldr
; so we need to use auxiliary function
(define (powerset lst) (foldr (lambda (n lst) (append (map (λ (x) (cons n x)) lst) lst))'(()) lst))