4 ms·
Took this as an excuse to write it in pure lambda calculus https://gist.github.com/Tarmean/65da65b8da37bd66d48e96d2aa73662b https://gist.github.com/Tarmean/65da
by Tarean 8y ago
Took this as an excuse to write it in pure lambda calculus https://gist.github.com/Tarmean/65da65b8da37bd66d48e96d2aa73662b https://gist.github.com/Tarmean/65da65b8da37bd66d48e96d2aa73...
I always enjoy how lambda calculus suddenly becomes a readable language after the prelude:
let (\n.
let (\m. isZero (mod n m)) \divisibleBy.
if (and (divisibleBy 3) (divisibleBy 5))
then FizzBuzz
else
(if (divisibleBy 3)
then Fizz
else
(if (divisibleBy 5)
then Buzz
else (intToStr n))))
\fizzBuzzStep.
(loop \recurse. \n.
if (equals n 100)
then nil
else (cons (fizzBuzzStep n) (recurse (n+1)))
) 1)
(\letArg letBody. letBody letArg)
let, if, then, else, loop, and even the numbers are all functions.
- crispyambulance 8y agoThe whole point of fizzbuzz is to filter for people that can just solve a tiny problem in a reasonably short time-- that's it. Most interviewers will even give some slack if the person has to look up the modulo operator or even do with out it. If someone can't do it at all there's some kind of serious issue with the way they're approaching the problem, or perhaps they're just not capable of doing it. But another common way for people to fail or at least get red-flagged is to over-think it and come up with a turgid solution-- like using lambda calculus! Simple problem. Simple solution. Nothing fancy. Going against that is asking for failure.
- wz1000 8y agoLambda calculus isn't a "solution" to fizz buzz, it's just another language you can implement fizz buzz in, which is what the parent poster was likely intending to demonstrate.
- tonyedgecombe 8y agoIt's just a bit of fun, nobody is suggesting you do this in an interview.
- austincheney 8y agoThe lambda calculus approach provides an answer that is a theoretical solution for multiple programming languages. With very minor changes the same answer can apply to C Lang or JavaScript.
- leifmetcalf 8y agoI'm a bit confused, how did you implement let, if, else etc.? I don't really know much about the lambda calculus except for what I learned from a short youtube video.
- Tarean 8y agoYou can name things like (\id. ...) (\x. x) This names the identity function id. You can make this slightly prettier like (\let. ...) (\def body. body def) Which lets you do let (\x. x) \id. ... Booleans are also functions let (\t f. t) \true. let (\t f. f) \false. let (\x. x) \then. let (\x. x) \else. let (\b thenLit ift elseLit iff. b ift iff) \if. Which lets you write if true then foo else bar Where then and else are thrown away, without them it is basically lisp syntax. You could make this slightly fancier - translate into cps to support `else if` and require `end` at the end. Tl;dr: with hacks
- stan_rogers 8y agoThere's a good elaboration of it in Tom Stuart's "Programming With Nothing" talk[0], in which he does a lambda calculus implementation of FizzBuzz in what's left of Ruby if you leave everything out except the things strictly necessary to do lambda calculus - with the exception of what you could call C-style macros (basically text search-and-replace, so you can call a section of code FOO and just type FOO everywhere you would have typed that section of code). There's also the little matter of output - you need to translate the resulting Church numerals into readable form for those who can't see that you've obviously produced correct FizzBuzz. There's a good enough explanation that what needs to be sort of hand-waved for brevity (things that are shown but not really explained in detail) aren't entirely opaque - you will be able to figure it out. Keep in mind, too, that the lambda calculus is a lot like machine language in one respect - the same little bit of "code" can have more than one meaning to the programmer even if the "machine" is doing exactly the same thing. [0] https://www.youtube.com/watch?v=VUhlNx_-wYk https://www.youtube.com/watch?v=VUhlNx_-wYk