I guess i dont see what the fuss is. Instead of looping through the numbers, they precalculate the answers and loop through that instead. Personally this seems about equivalent of replacing all instances of 2+2 in your program with just 4, and then claiming the program doesnt use addition.
Both solutions seem to deal with group theory to basically the same extent.
They actually don't precalculate, since Haskell is lazy. This kind of construction of the infinite data structure and relying on laziness is a really typical trick in Haskell. For example:
fib = 0 : 1 : zipWith (+) fib (tail fib)
Indeed, the way the author has written it would seem a little strange to most Haskell programmers, I think, who would just write (in this idiom):
mapIdx f xs = map (uncurry f) $ zip [1..] xs
fizz = ["", "", "Fizz"] ++ fizz
buzz = ["", "", "", "", "Buzz"] ++ buzz
fizzBuzz = mapIdx f fbs
where f n "" = show n
f _ v = v
fbs = zipWith (++) fizz buzz
main = mapM_ putStrLn $ take 100 $ fizzBuzz
Though usually you would just write it a more typical way
f :: Int -> String
f x | x `mod` 3 == 0 && x `mod` 5 == 0 = "FizzBuzz"
| x `mod` 3 == 0 = "Fizz"
| x `mod` 5 == 0 = "Buzz"
| otherwise = show x
main :: IO ()
main = mapM_ (putStrLn . f) [1..100]
But, yes, I don't find the semigroup connection particularly illuminating.
> They actually don't precalculate, since Haskell is lazy.
I mean they ditectly put into the source code that the pattern is "", "", "fizz", etc..., and repeat (in a lazy fashion), instead of having the computer calculate which integers give a fizz/buzz. So the programmer is in a sense precalculating at the time of writing the program, instead of having the computer calculate the result of the if statements at runtime.
I think you misunderstand what i mean by "precalculated". I just mean the answer is embeded in the source code and not calculated at runtime. It doesnt matter how you embed it in the source code, whether that is a list literal or constructed via functions or whatever
Edit: for clarity, the reason i think this is kind of a cop out, is that in the article the author seems to call out not using if-then-else as a benefit of this solution, compared to the normal version that takes a list of integers and transforms it using if/then/else and mod operations. But i dont really think it counts as not using if/then/else if you literally do the same operation in your head and then just write down the transformed list explicitly, to save the computer the effort of transforming the list at runtime for you.
I think what you are trying to say is that it's not using the modulo operator to derive the pattern from the integers, instead it is simply encoding the pattern directly in the program as a pattern (false, false, true, ...).
Your objection is confusing everyone else because these are both equally "calculations", and the meaning of the "divided evenly by three" calculation and the meaning of the FFTFFTFFT... sequence are the same, so it just two ways of expressing the same thing. Either way is just as "precalculated" as the other.
Yes, exactly. In group theory when we speak of a quotient group modulo one of its normal subgroups, we’re referring to exactly this. Z3, the integers mod 3, is isomorphic to (actually equal to) Z/3Z, the integers quotiented by all the multiples of 3.
People who haven’t studied abstract algebra aren’t used to thinking of it this way though. To most people, the modulus operator is specifically an operator that returns the remainder of Euclidean division. To think of it as a bunch of equivalence classes that split up the integers is not something most people think of right away.
Do you have a good resource for an intro to group theory and abstract algebra? I’ve never had a chance to study it in a course but it pops up a lot in physics and other interesting phenomena.
The best resource I know of is the textbook I bought for the course I took on group theory and ring theory [1]. It’s pretty expensive and the exercises are very challenging but if you’re a self-motivated student, you can learn a TON of abstract algebra from this one book. You may want to review some linear algebra before you dive in, if you haven’t done so in a while. You can find solutions to many of the exercises online though I can’t vouch for their accuracy.
Well yes, if these things represented different things, then the output of the program would be incorrect.
To put it another way, the original version was explicitly calculating the function ℤ -> { "", "fizz" }. The new version had the results of this function directly embeded in the source code (and hence precalculated as opposed to calculated at runtime). I just don't see the two of these approaches really being all that different
I don't think the point of the post was that it was a radically new approach, but rather that it is an application of concepts that are considerably more general. The hope in using such concepts is that, being so general, you will start to see them everywhere, and using higher-level abstractions lets you see connections that you would otherwise miss. It's a kind of compression of the conceptual space that one works in. Category theory is all about trying to recognize and catalog these connections.
> I just mean the answer is embeded in the source code and not calculated at runtime.
i mod 3 and i mod 5 are just as much embedding the answer in the source code. Saying that the unrolled sequence embeds the answer more than the modulus is the same as saying that
for (i = 0; i < 10; i++)
does not embed the answer to iterating over the integers 0 to 9, but
for (auto i : views::iota(0, 10))
does embed it. I don't think anyone would regard those as anything but equivalent, though.
A lot of folks are giving you reasonable flack around “well both of these encode it”, because encode can mean lots of things, but I think the specific feature you are referring to is that the amount of source code used to indicate the fizz buzz cycle is linear in the length of the cycle; basically a unary representation. Is that accurate?
My objection is that the author presents it as a totally different approach, but to me it looks like the same approach as the original but with constant propagation applied. (With a little time away from this discussion, i guess tbf i must admit determining the order of the group is a bit more than constant propagation)
Also with a little more sympathetic eye, i suppose the new version is more evocative of the underlying group and such representations are much more in line with the mores of functional programming. At the same time, i cant help but think its a bit pretentious to talk about being isomorphic to a cyclic group and otherwise evoke high level math, just to say, you know this program whose output by definition repeats in a very obvious pattern, well guess what, its output is cyclic.
To a sufficiently advanced compiler, any correct implementation is equivalent to any other. The difference is how we think about it.
If you look at it as taking something simple and making it needlessly complicated, then it seems pretentious, but if you look at it as taking very abstract concepts and making them more understandable with a concrete, well-known example, it's not.
This might give you a good idea of where the author is coming from and trying to accomplish:
It would be pretty straightforward to parametrize those functions so you could fizz buzz on any numbers, not just 3 and 5. Or is that not what you meant? You want a system that can solve any problem? Then you’re looking at a computer algebra system. SageMath [1] is a nice one.
Both solutions seem to deal with group theory to basically the same extent.