I'm going to try to implement the Y combinator without looking! Why? Because I'm procrastinating. I have work to do, but don't want to, and its the weekend, but I can't do pure recreational because I compulsively need to do something that feels legitimized with the veneer of 'learning' in a skill tangentially related to 'my career', so here goes.
This is basically cheating, but off the top of my head I recall that the formula for how the Y combinator looks goes something like this:
Y(f) = f(f . f)(f) yeah no I don't remember at all. It has the messy spaghetti quality of nested function calls that
makes all functional code written without threading macros or a
pipe operator completely impossible to intuitively grasp for
regular humans. So fuck it, let's work from the problem itself and really invent the solution like textbooks say we're
supposed to do.
Imagine the ridiculously improbable circumstance of wanting to use recursion in a dynamically typed language that doesn't support it, but does support anonymous functions. This problem is very unrealistic and improbable, and is only noteworthy because the solution is so interesting. I need to create a function Y that takes another function and makes it recurse.
Presumably the function has to have knowledge of Y since Y is its only mechanism for recursing. Okay, so maybe something like this?
#lang racket
(define ((y func) x)
((func func) x))
(define ((fib func) x [a 0] [b 1])
(if (= x 0)
a
((func func) (- x 1) b (+ a b))))
((y fib) 6)Well, that took a bunch of time. It works, so I guess now I can look at the canonical implementation and see- Oh my god what the heck! Mine looks nothing like the canonical version! You know what, fuck this, if I really want to be comfortable with this I should just formally study combinatory logic. Where does that fall on my priority list? Haha. I think I will continue with math, then physics, then computer science, then oh god where does it end.
I will worry about math for now :)