| S,K,B,C and Y are some famous operators that should be familiar to lambda-calculus nerds. https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/Fixed-point_combinator The Y combinator (which is behind the name for this website) lets you define recursive functions without actually using recursion (the only recursive definition is Y itself, which is often available as a language primitive) A less obfuscated version of the factorial using the y combinator would be this one: fac' f n = if n == 0 then 1 else f (n - 1)
fac = y fac'
note how fac' is not recursive and instead calls its "f" parameter when it wants to do a recursive call. The y combinator then ties everything together by passing fac' to itself.The other obfuscating factor in that program are the S,K,B and C combinators. The purpose of these one is to let you write a program without any variable definitions or lambdas. Notice that when that program finally defines `fact`, it has the form fact = y {some big expression}
where the big expression only has function applications and references to the previously-defined combinators. There are no mentions to the "f" and "n" variables that we had before. The neat thing about the SK family of combinators is that you can use them to build any function, not just the factorial:https://en.wikipedia.org/wiki/Combinatory_logic#Completeness... As for the speed comment, one way to implement lazy evaluation, as found in Haskell, is to compile programs down to those SK combinators and then use graph reduction to evaluate the result. I would expect a reasonable Haskell implementation to be able to automatically generate the unreadable combinator version of the program from the usual definition of factorial that we all know and love but maybe there was a Haskell implementation back in 2001 that wasn't as reasonable? https://en.wikipedia.org/wiki/Graph_reduction https://en.wikibooks.org/wiki/Haskell/Graph_reduction https://wiki.haskell.org/Super_combinator That said, dunno how the more recent Haskell compiler handle things. Hopefully some other helpful HN-er can enlighten us here. |