3 ms·
A much more concise prime number generator in lambda calculus [1] [2] is λ (λ 1 (1 ((λ 1 1) (λ λ λ 1 (λ λ 1) ((λ 4 4 1 ((λ 1 1) (λ 2 (1 1)))) (λ λ λ λ 1 3
by tromp 4y ago
A much more concise prime number generator in lambda calculus [1] [2] is
λ (λ 1 (1 ((λ 1 1) (λ λ λ 1 (λ λ 1) ((λ 4 4 1 ((λ 1 1) (λ 2 (1 1)))) (λ λ λ λ 1 3 (2 (6 4))))) (λ λ λ 4 (1 3))))) (λ λ 1 (λ λ 2) 2)
or in graphical notation [3]
─────────────────────────────────────────────────
┬─┬───────────────────────────────────┬──── ────┬
│ │ ┬─┬ ────┬─┬────────────────────── ┼───┬ ┬───┼
│ │ └─┤ ────┼─┼───────────────────┬── ┼───┼ │ ┬ │
│ │ │ ┬───┼─┼───────────────────┼── ┼─┬─┼ │ ┼ │
│ │ │ │ ─ ┼─┼─┬─────┬──── ──────┼─┬ │ ├─┘ └─┤ │
│ │ │ │ ┬ └─┤ │ ┬─┬ ┼─┬─┬ ──┬───┼─┼ ├─┘ ├─┘
│ │ │ └─┤ └─┤ └─┤ │ ├─┘ ──┼─┬─┼─┼ │ │
│ │ │ │ │ │ ├─┘ ┬─┼─┼─┼─┼ │ │
│ │ │ │ │ ├─┘ └─┤ │ ├─┘ │ │
│ │ │ │ └───┤ │ ├─┘ │ │
│ │ │ │ │ ├─┘ │ │
│ │ │ │ ├─────────┘ │ │
│ │ │ ├─────────┘ │ │
│ │ └───┤ │ │
│ │ ├───────────────────────────┘ │
│ ├───────┘ │
└─┤ │
└───────────────────────────────────────────┘
which normalizes to an infinite list of booleans. This can also be concisely converted [4] into a list of primes written in decimal.
[1] https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html
[2] https://tromp.github.io/cl/Binary_lambda_calculus.html#Complexity_of_Sets https://tromp.github.io/cl/Binary_lambda_calculus.html#Compl...
[3] https://tromp.github.io/cl/diagrams.html https://tromp.github.io/cl/diagrams.html
[4] https://www.ioccc.org/2012/tromp/hint.html https://www.ioccc.org/2012/tromp/hint.html
- Suskewiet 4y agoJohn, Thanks for the feedback. Really taking it to the limit. Very interesting reads. Bumped into them while doing this exercise, but did not dive in (yet).