a bunch of lists of numbers

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.

For instance, the following check-expects should be satisfied:

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

Basically, this function produces the power set of a set of numbers, but I'm not sure how it can produce all of the elements, without recursion.

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

Summary: I took the standard definition of powerset from here and curried it. Then I replaced let, append, and map with my-let, my-append, and my-map. I defined the Y combinator as the Y macro and a helper define/rec that makes a function recursive. Then I defined my-append and my-map using the define/rec macro (note that they're curried too). We can substitute everything to get the desired code.