Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. #lang racket
  2.  
  3. (define-syntax-rule (my-let ([var val]) body)
  4. ((λ (var) body) val))
  5.  
  6. (define-syntax-rule (Y e)
  7. ((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
  8. (λ (x) (f (λ (y) ((x x) y))))))
  9. e))
  10.  
  11. (define-syntax-rule (define/rec f e)
  12. (define f (Y (λ (f) e))))
  13.  
  14. (define/rec my-append
  15. (λ (l1)
  16. (λ (l2)
  17. (cond [(empty? l1) l2]
  18. [else (cons (first l1) ((my-append (rest l1)) l2))]))))
  19.  
  20. (define/rec my-map
  21. (λ (f)
  22. (λ (l)
  23. (cond [(empty? l) empty]
  24. [else (cons (f (first l)) ((my-map f) (rest l)))]))))
  25.  
  26.  
  27. (define/rec my-power-set
  28. (λ (set)
  29. (cond [(empty? set) (cons empty empty)]
  30. [else (my-let ([rst (my-power-set (rest set))])
  31. ((my-append ((my-map (λ (x) (cons (first set) x))) rst))
  32. rst))])))
  33. 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:
  34.  
  35. (define my-power-set
  36. ((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
  37. (λ (x) (f (λ (y) ((x x) y))))))
  38. (λ (my-power-set)
  39. (λ (set)
  40. (cond [(empty? set) (cons empty empty)]
  41. [else
  42. ((λ (rst)
  43. ((((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
  44. (λ (x) (f (λ (y) ((x x) y))))))
  45. (λ (my-append)
  46. (λ (l1)
  47. (λ (l2)
  48. (cond [(empty? l1) l2]
  49. [else (cons (first l1)
  50. ((my-append (rest l1)) l2))])))))
  51. ((((λ (f) ((λ (x) (f (λ (y) ((x x) y))))
  52. (λ (x) (f (λ (y) ((x x) y))))))
  53. (λ (my-map)
  54. (λ (f)
  55. (λ (l)
  56. (cond [(empty? l) empty]
  57. [else (cons (f (first l))
  58. ((my-map f) (rest l)))])))))
  59. (λ (x) (cons (first set) x))) rst))
  60. rst))
  61. (my-power-set (rest set)))])))))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement