3 ms·
It looks like an equation, but it's really almost a Y combinator, almost in Haskell: y f = f (y f) Though this won't exactly type check, it's a pithy rem
by fusiongyro 10y ago
It looks like an equation, but it's really almost a Y combinator, almost in Haskell:
y f = f (y f)
Though this won't exactly type check, it's a pithy reminder of what I found so powerful about functional programming, which is that _any_ repetition in the code ought to be something you could factor out. The Y combinator shows you that _even the idea of a function calling itself_ can be factored out. It's hard to imagine you would really ever be forced to repeat yourself if this can be factored out.
Of course that isn't the real point of the Y combinator, but this thought, this "equation" completely changed the way I think about programming.
- tel 10y agoThat does typecheck though!
- qubex 10y agoMuch along the same lines, I'm fascinated by Turing's Theta Combinator (another fixed point combinator from lambda calculus).
- harpocrates 10y agoThis works in Haskell just fine, thank you very much! ghci> y f = f (y f) ghci> factorial = y (\f x -> if x == 0 then 1 else x * f (x-1)) ghci> factorial 5 120 However, the Y combinator as defined in a non-recursive form is tougher to implement in Haskell [1][2]. It looks a lot better in Racket (and this is coming from someone who doesn't particularly like Racket). (λ (r) (λ (h) (h h)) (λ (g) (r (λ (x) (g g) x)) [1] http://stackoverflow.com/a/5885270/3072788 http://stackoverflow.com/a/5885270/3072788 [2] http://stackoverflow.com/a/13119751/3072788 http://stackoverflow.com/a/13119751/3072788