Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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 hand-substituted everything to get this:
- (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)))])))))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement