Semigroup Resonance FizzBuzz | Hacker News Reader

Semigroup Resonance FizzBuzz

blog.ploeh.dk

86 pointslelf66 comments

Nice idea. Here is the (rough) equivalent in Python.

  from itertools import cycle
  fizz = cycle(['', '', 'Fizz'])
  buzz = cycle(['', '', '', '', 'Buzz'])
  for n in range(1, 100):
      fizzbuzz = next(fizz) + next(buzz)
      print (fizzbuzz if fizzbuzz else n)

And the one in Java, less cool because neither cycle nor zip exist :(

    <T> Iterator<T> cycle(List<T> list) {
      return IntStream.iterate(0, x -> (x + 1) % list.size()).mapToObj(list::get).iterator();
    }
    <T, U, V> Iterator<V> zip(Iterator<T> it1, Iterator<U> it2, BiFunction<T,U,V> merger) {
      return Stream.generate(() -> merger.apply(it1.next(), it2.next())).iterator();
    }

    var fizz = cycle(List.of("Fizz", "", ""));
    var buzz = cycle(List.of("Buzz", "", "", "", ""));
    var ints = IntStream.iterate(0, x -> x + 1).boxed().iterator();
    var fizzbuzz = zip(
       zip(fizz, buzz, String::concat),
       ints, (f, i) -> f.isEmpty()? "" + i: f);
    Stream.generate(fizzbuzz::next).skip(1).limit(100)
          .forEach(System.out::println);

Conditionals are so 2019.

  from itertools import cycle
  fizz = cycle([lambda x: ''] * 2 + [lambda x: 'Fizz'])
  buzz = cycle([lambda x: ''] * 4 + [lambda x: 'Buzz'])
  numb = cycle([lambda x: x] * 2 + [lambda x: '', lambda x: x, lambda x: ''])
  for n in range(1, 100):
      print(next(fizz)(n) + next(buzz)(n) + next(buzz)(n))

tbqh that's a lot less readable and a lot less intuitive

Yeah, not really going for readable. Just an exercise in eliminating the conditional.

So far i rate yours most friendly / maintainable .

"Maintainability" for FizzBuzz is a loose term, but a major disadvantage of this one is that each cycle length is encoded twice: first in fizz/buzz, then in numb.

Oh i just saw that.

That's very nice code and Python is non-functional. I love its generators.

That's my version to make it more "functional":

  from itertools import cycle, islice
  from operator import add

  fizz = cycle(['', '', 'Fizz'])
  buzz = cycle(['', '', '', '', 'Buzz'])
  strings = map(add, fizz, buzz)
  strings_or_nos = (s or i for i, s in enumerate(strings, start=1))
  print(list(islice(strings_or_nos, 100)))

Cool, you just need to join the list with '\n' before printing ;)

This is where I ended up:

    from itertools import islice, cycle
    print("\n".join(islice((
                    f + b if f or b else str(i+1)
                    for i, (f, b) in enumerate(
                        zip(cycle(["", "", "Fizz"]), cycle(["", "", "", "", "Buzz"]))
                    )), 100)))

Here's my somewhat obfuscated version of same.

https://gist.github.com/kbob/f46776fdc950e6a948b04c76bc23e87...

Reminds me of the time I was trying the first problem of Project Euler, “Multiples of 3 and 5” in Joy.

https://projecteuler.net/problem=1

> If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

> Find the sum of all the multiples of 3 or 5 below 1000.

I tried dual iterators at first but it turned out to be more elegant to just generate the multiples directly using the sequence:

    3 2 1 3 1 2 3

It turn out that the differences between successive multiples always form a palindrome.

http://joypy.osdn.io/notebooks/Developing.html

(In re: catamorphism et. al. see http://joypy.osdn.io/notebooks/Recursion_Combinators.html Cheers!)

Nice article, but I’d point out that “the maybe catamorphism” is fundamentally just an if statement in disguise. You could, if you were feeling particularly extra, use the Foldable instance...

Here’s an okay Clojure version.

Using (clojure.string/join “\n” coll) would be more idiomatic. And there’s probably a concise way to leave the nils in the sequence alone instead of mapping str—that would change the “if” into an “or”, which is closer to the original solution.

  (defn fizzbuzz [n]
   (doall (map 
           #(println (if (seq %1) %1 %2))
           (map str (cycle [nil nil "fizz"])
                    (cycle [nil nil nil nil "buzz"])) 
           (range 1 (inc n))))
   nil)

Its kind of begging the question in a way. The only reason you can conclude this is related to Z3 and Z5 is because the original problem statement said to repeat fizz every 3 numbers, and thus its related to cycluc groups. But the only aspect of group theory used seems to be that Z3 repeats cyclicly (which was the fact we used to invoke group theory in the first place). So it seems rather circular.

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.

They’re only doing it once though, not for every multiple of 3 or 5. So if you didn’t like the line:

    buzzes = cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"]

You could instead write:

    buzzes = cycle $ replicate 4 Nothing <> [Just “buzz”]

It’s not a big difference though. Since everything is lazily evaluated, you’re not precalculating anything.

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.

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.

[1] https://www.sagemath.org/

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.

Another way to put it is that `x % 3 == 0` and `cycle [0,0,1]` are just two forms of shorthand for the same concept.

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.

[1] https://www.amazon.com/Abstract-Algebra-3rd-David-Dummit/dp/...

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:

https://blog.ploeh.dk/2017/10/04/from-design-patterns-to-cat...

> This might give you a good idea of where the author is coming from and trying to accomplish:

I've been telling people that design patterns were algebras glimpsed darkly for years, but it's nice to see someone finally write that up.

A sufficiently smart compiler and a sufficiently smart compressor are dual to one another.

I love these "harder than necessary" solutions to FizzBuzz, it might be useful to take questions about your ability out of the way.

Another interesting way would be to not use any modulo operation, but only do string processing and substitution on the numbers to check their divisibility (easier for mod 5, a bit harder for mod 3 but not impossible)

mod 3 is easy if you process the number in base 3!

Assuming you wanted to keep it in base 10 this is the simplest to follow way I could come up with:

    numberString = "1578465465464570"
    divFive = /[05]$/.test(numberString);
    
    // Check if the digits of the number sum up to 0, 3, 6, or 9. If so it is divisible by 3.
    while(numberString.length > 1)
    {
        total = 0;
    
        for (const digit of numberString) {
            total += parseInt(digit, 10);
        }
    
        numberString = total.toString(10);
    }
    
    divThree = /[0369]/.test(numberString)
    divFifteen = divThree && divFive

Yup, that works, but there's an even "more interesting" way if you're in FizzBuzz number range

Reduce the number using string replacements based on patterns (for example, all digit pairs that sum to 0 mod 3 can be removed). The order of the digits doesn't matter.

That doesn’t satisfy the requirement “only do string processing and substitution on the numbers”.

One can do this as follows (edit: spot the bug; this algorithm is broken, but can be easily fixed):

  - Take the number as a string  : "13565172345474789047"
  - remove all 0s, 3s, 6s, and 9s: “155172454747847”
  - replace all 4s and 7s by 1s  : "155112151111811"
  - replace all 5s and 8s by 2s  : "122112121111211"
  - sort the string’s characters : "111111111122222"
  - replace all ‘111’ by ‘’      : "122222"
  - replace all ‘222’ by ‘’      : "122"
  - replace ’12’ by ’’ repeatedly: "2"
    (you have to do this at most two times)

(proving that none of these steps changes the sum of the digits of the number (mod 3) is easy, as each step changes the sum by a multiple of 3)

⇒ that number is 2 (mod 3)

Not that it will help with this exact situation, but there's actually a trick to find out divisibility of 3 [1]. Basically it states: the sum of the digits of a number, N, are divisible by 3 if an only if the number N itself is divisible by 3.

[1]: https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility...

It is exactly the way I'm thinking. More importantly, the order of the digits doesn't matter, so if 12 is divisible, so is 21, 102, etc.

Though maybe the two approaches can be combined

Sure maybe something like this. It's not very performant, but it uses some math skills:

  console.clear();

  /** naive python like range in JS */
  function* range (beg, end) {
    for(let i = beg; i < end; ++i) {
      // stringify the number
      yield '' + i;
    }
  }
  
  function buzz (stringNum) {
    const lastChar = stringNum.charAt(stringNum.length - 1);
    return lastChar === '5' || lastChar === '0';
  }
  
  const mapping = [0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1];
  
  function fizz (stringNum) {
    return (
      stringNum
        // get each character of the string
        .split('')
        // find out if total digits are divisible by three.
        .reduce((acc, x) => (acc + mapping[x]) % 3, 0) === 0
    );
  }
  
  function fizzBuzz (stringNum) {
    const f = fizz(stringNum), b = buzz(stringNum);
    if(f && b) {
      return 'FizzBuzz';
    } else if (f) {
      return 'Fizz';
    } else if (b) {
      return 'Buzz';
    } else {
      return stringNum;
    }
  }
  
  const nums = [...range(1,1001)];
  
  const result = nums
    // main algo
    .map(fizzBuzz)
  
  console.log(result.join('\n'));

EDIT: sorry I didn't see your other reply below another comment. I now see this does not fulfill the requirements.

Just by doing a few examples and thinking through it a little I think there is also another way to do this in binary with bit shifting using the same principles as the modulo 3 trick. It uses the fact that a bit when it is on modulo three alternates between 1 and 2. Maybe you could then 'unzip' the binary string and then use the string replacement strategy in two alternate ways depending on if it's one of the odd bits or even bits.

EDIT: hmm, unzip is probably the wrong term here.

This is so beautiful.

Not sure I ever understood the haskell folks drive. Is it mathematical poetry? An extreme attempt to simplify? Is this an intellectual equivalent of trying to write poetry?

The words catamorphism, semigroup and monoid barely make sense to most programmers.

As a former Scala dev who dipped their toes a bit too far into Cats/Matryoshka, it came from a combination of DRY + powerful abstractions. If you have powerful abstractions then it's possible to see commonalities between parts of the codebase that others can't see. "Oh that thing that we're doing over here with lists is the same as that part with futures." That's where DRY comes in and turns that observation of duplicity into unification. Less code equals less bugs, right?

Another angle to view it is what if I told you that you could eliminate an entire class of errors by employing this abstraction? Learn Option once and then never have to deal with NPE's. What about errors due to recursion? Would it be appealing to avoid those errors forever? Concurrency, state, error handling, all things that have appealing abstractions.

If the idea of mathematical connections to seemingly unrelated things appeals to you, or you are tired of dealing with the same bugs in different forms then these abstractions seem very appealing. The problem is that it's a technical solution to a human problem. That doesn't inherently make it bad, but it does imply a different set of tradeoffs.

I think there's a bit of a leap between "Option types are useful" and "using terminology to describe simple and common patterns of computation", though.

I think it's not too far from practicality to describe the solution in OP as along the lines of "solving fizzbuzz by combining infinite streams". It's a quirky/cute solution.

I think there's a jump from "knowing these functions / structures can be useful" and "let's use terms like 'semigroup resonance' and 'catamorphism'".

When I'm explaining these concepts, I find myself apologizing for the names, usually by stealing the quip "the math people got here first". Programmers usually take commonplace words and tack on an extra technical definition: list, string, class, object. Semigroup and catamorphism stand out as non-ideomatic names. If they had been called combiner and fold they might have seen more widespread use.

The concepts really aren't that easy (though they are indeed simple). While I disliked the names too at the beginning, I realize now that they are necessary, because it's important to be precise with your words and the concepts are so general that there simply isn't a better word for it. You can try to call a functor a container since both `List a` and `Maybe a` are functors and contain an `a`. But what about `Int -> a`? It is also a functor and doesn't "contain" anything. Perhaps "producer" would be a better word? `data Phantom a = Phantom` doesn't "produce" anything and is still a functor. Eventually you may arrive at a name like "mappable" which is convention just like "functor" and arguably worse because "functor" is more precise and was there first.

Names like StateT and Reader can surely be improved but the names taken directly from mathematics are already the best we can do imo.

I don't know. `Int -> a` is definitely a container in my mind. Imagine a list. What does it contain? Well, it contains the contents of the list, of course! What is it? We don't know until we look inside. What does `Int -> a` contain? It contains an `a`. Which `a` does it contain? We don't know until we look inside (by passing it an `Int`). The only real difference is that in a list I put the value in first and look at it later. With a function, I look at the value first and put the value in later ;-) I'm being silly, but I really do find that treating it as a container makes it much, much easier for me to reason about it.

However, I completely agree that the word "functor" is useful for exactly the reason you imply. It's a kind of special container. It doesn't work exactly the way you imagine containers should work initially. So I guess it's 6 of 1 half a dozen of the other. I just wanted to speak out because I know there are others like me that find reasoning about functors as if they are containers very useful.

> The words catamorphism, semigroup and monoid barely make sense to most programmers.

Over the last few years I have absorbed a lot of these terms via professional Haskell development and have come to the conclusion that it is quite unfortunate that most of us tend to shy away from this unfamiliar vocabulary. It turns out these are very precise (mathematical) terms which describe common things we see every day in programming.

Addition, multiplication, and string concatenation are all monoids (described as: an associative binary operation with an id element). This might not seem useful to know on the surface, however, once you discover that you can write generic functions over any monoid you can start eliminating large classes of errors that tend to turn up in software development due to the DRY principle.

> An extreme attempt to simplify?

It turns out that the more generic you make something, the harder it is to do the wrong operations on it.

    id :: a -> a

If 'a' is a generic type value for all possible types, is it possible to return anything other than the initial value passed in?

Its about learning-fatigue due to needing to function in real life, especially since the learning curve is steep.

A family man might read a book about FP patterns to solve common issues, agile, QS+testing, concurrency, etc (actually seen tgese read by 50yo collegues) - but not a single one has a category theory book on their table.

Its a question of time invested vs benefits to current occupation.

FP terminology is the domain of the young and the driven, who also are of academic age. (Probably winy find any junior-high kids dabbling with semigroups anytime soon)

For what it's worth I'm a 40yo family man who has been in the industry for 20 years :)

I'd rather describe it as mathematical code golfing.

I dont think this answer should be downvoted.

The linguistics issue here is real and should be addressed or we will end up into two camps, and one will eventually give way to the other.

And math-hardcorers be warned, Life prefers the simple.

Depends on what you're doing. Scott Wlaschin did the best modern take on that here: https://fsharpforfunandprofit.com/posts/13-ways-of-looking-a.... It shows incrementally going from a purely (haha) procedural implementation all the way up to brain-exploding free monads, all doing essentially the same thing: a basic implementation of the old turtle game.

My take is you should know all these, and choose the appropriate level for what you're doing. You don't need to crank it up to 13 everywhere just because it's there. I spend most of my time (web apis, business logic) around level 7. If you dial the abstraction level too far up, not only does the code seem confusing, but it's also easy to paint yourself into an abstraction corner, where a new requirement comes in that breaks the abstraction, so you end up either tearing it down and rebuilding it completely, or building up a terrible "spaghetti abstraction" which is the worst kind of spaghetti. It's a bit ironic to think that abstractions are exactly what's supposed to prevent you from being painted into a corner, but it can happen easily. (https://www.sandimetz.com/blog/2016/1/20/the-wrong-abstracti... is a good reference).

When writing things like compilers, the abstraction level can comfortably go higher. In fact it should. It makes challenging logic far easier to reason about and more consistent to specify and implement when you can think about it mathematically. Other things like rules engines and such can live comfortably in between the two. Conversely when writing timing-critical device code then the appropriate level of abstraction is much lower. A good reference for this style is the k8s PV code. Note the comments starting on line 55 (tldr: DO NOT SIMPLIFY THIS CODE) https://github.com/kubernetes/kubernetes/blob/ec2e767e593953...

So as developers we have to determine what the appropriate level of abstraction should be for our use cases. In fact I'd offer that's one of the most important parts of software design. But it's important to know all of them so we can choose accordingly.

keep in mind that that last statement is relative to your education, etc.

The haskell model is much more intuitive and productive for me than the weird oo-esque models of “usual” languages like python, c++, and java.

May i ask what is your background?

I studied math for a couple years in university and have been a professional python programmer for a while.

I’m familiar with the theory behind popular styles like OO and have used them professionally but ultimately I find Haskells incredibly simple and constrained type system (closed data types, no subtyping, essentially total inference, purity, etc) easier to think in than the Wild West of python or java, say, since there are fewer modeling choices to make.

I did haskell for a while and mathematical poetry is actually a very fitting term.

It's a desire to be lazy ;)

The gist is - by having many simple-but-powerful tools along with many simple-but-powerful ways of composing such tools, it makes programming real problems way less intense. The cost of course is the learning curve. So I think of it has shifting variable cost of development to fixed costs upfront.

The end result in my experience is being able to handle more complexity than otherwise (good for side-projects.) Or to handle the same complexity with less time and effort (good for FT engineering...to make room for said side-projects.)

(Those terms actually have very general and simple definitions that I've seen interns learn in one teaching session. But they are infinitely useful problem solving techniques that I use all the time.)

Reply on news.ycombinator.com