一堆数字列表

Question

I would like to write the Racket function find-subsets. The function produces the list of subsets of a list of numbers w/o helper functions and that only uses lambda, cond, cons, rest, first, and other primitive functions.

例如，应满足以下检查预期：

(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 and curried it. Then I replaced let, append, and map with my-let, my-append, and my-map. I defined the Y combinator 中获取 powerset 的标准定义作为 Y 宏和一个使函数递归的助手 define/rec。然后我使用 define/rec 宏定义了 my-append 和 my-map （请注意它们也是柯里化的）。我们可以替换所有内容以获得所需的代码。

一堆数字列表

a bunch of lists of numbers

abstraction

higher-order-functions

racket