4 ms·
Apparently this s f g x = f x (g x) k x y = x b f g x = f (g x) c f g x = f x g y f = f (y f) cond p f g x = if p x then f x else g x fac
by infinity0 11y ago
Apparently this
s f g x = f x (g x)
k x y = x
b f g x = f (g x)
c f g x = f x g
y f = f (y f)
cond p f g x = if p x then f x else g x
fac = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))
is faster than this
facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)
fac = facAcc 1
and these are the first and second fastest.
> Interestingly, this is the fastest of all of the implementations, perhaps reflecting the underlying graph reduction mechanisms used in the implementation.
Could anyone elaborate on this a bit more?
- deleted 11y ago[deleted]
- tromp 11y agoThe former is equivalent to fac' f 0 = 1 fac' f n = n * f (n-1) fix f = f (fix f) fac = fix fac' so if the second is indeed faster then explicit fixpoints beat tail recursion
- protomyth 11y agoCan someone explain to the non-Haskell folks how that first example works?
- harveywi 11y agoThe author had (too much) fun using a combination of the SKI combinator calculus [1] and the "B, C, K, W" system [2]. [1] https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus [2] https://en.wikipedia.org/wiki/B,_C,_K,_W_system https://en.wikipedia.org/wiki/B,_C,_K,_W_system
- maweki 11y agoIsn't Haskell internally using a variant of the SKI combinator calculus to represent that all functions are data? This would mean less reduction for an already reduced program.
- lelf 11y agoThat would be true for a toy Haskell compiler. “The standard” Haskell compiler, GHC, can do a whole lot of optimisations and produces really good machine code nowadays.
- ufo 11y agoS,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/SKI_combinator_calculus https://en.wikipedia.org/wiki/Fixed-point_combinator 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_of_the_S-K_basis 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.wikipedia.org/wiki/Graph_reduction https://en.wikibooks.org/wiki/Haskell/Graph_reduction https://en.wikibooks.org/wiki/Haskell/Graph_reduction https://wiki.haskell.org/Super_combinator 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.
- lmm 11y agoTo be clear, Y itself doesn't have to be recursive either. You can express it as an ordinary lambda, and write a recursive program without any named values or functions.
- truncate 11y agoOther people have provided good answers, but I'm just gonna add another link explaining Y Combinator ``Why of Y" by Matthias Felleison[1] , which is so far my favorite explanation. https://xivilization.net/~marek/binaries/Y.pdf https://xivilization.net/~marek/binaries/Y.pdf
- eru 11y agoI am not sure these performance results are true any more.