11 ms·

Semigroup Resonance FizzBuzz

86 points by lelf 7y ago

moomin 7y ago
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...
- deleted 7y ago
  [deleted]
united893 7y ago
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.
- aaron-santos 7y ago
  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.
  - rgoulter 7y ago
    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'".
    - aaron-santos 7y ago
      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.
    - tsss 7y ago
      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.
      - mikekchar 7y ago
        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.
- bojo 7y ago
  > 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?
  - idclip 7y ago
    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)
    - bojo 7y ago
      For what it's worth I'm a 40yo family man who has been in the industry for 20 years :)
- zozbot234 7y ago
  I'd rather describe it as mathematical code golfing.
  - idclip 7y ago
    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.
- daxfohl 7y ago
  Depends on what you're doing. Scott Wlaschin did the best modern take on that here: https://fsharpforfunandprofit.com/posts/13-ways-of-looking-at-a-turtle/ 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-abstraction 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/ec2e767e59395376fa191d7c56a74f53936b7653/pkg/controller/volume/persistentvolume/pv_controller.go 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.
- ves 7y ago
  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.
  - idclip 7y ago
    May i ask what is your background?
    - ves 7y ago
      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.
- idclip 7y ago
  I did haskell for a while and mathematical poetry is actually a very fitting term.
- whateveracct 7y ago
  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.)
raverbashing 7y ago
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)
- saghm 7y ago
  mod 3 is easy if you process the number in base 3!
- deleted 7y ago
  [deleted]
- zamadatix 7y ago
  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
  - raverbashing 7y ago
    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.
  - Someone 7y ago
    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)
jamesdhutton 7y ago
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)
- _old_dude_ 7y ago
  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);
- deleted 7y ago
  [deleted]
- kortilla 7y ago
  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))
  - inetknght 7y ago
    tbqh that's a lot less readable and a lot less intuitive
    - kortilla 7y ago
      Yeah, not really going for readable. Just an exercise in eliminating the conditional.
bawolff 7y ago
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.
- madhadron 7y ago
  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.
  - bawolff 7y ago
    > 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.
    - chongli 7y ago
      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.
carapace 7y ago
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 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 http://joypy.osdn.io/notebooks/Developing.html (In re: catamorphism et. al. see http://joypy.osdn.io/notebooks/Recursion_Combinators.html http://joypy.osdn.io/notebooks/Recursion_Combinators.html Cheers!)
egypturnash 7y ago
This is so beautiful.
crispyambulance 7y ago
> You can implement the FizzBuzz kata using the fundamental concepts catamorphism, semigroup and monoid. No if-then-else instructions or pattern matching is required. Instead, you use the string concatenation semigroup to enable resonance between two pulses, and the maybe catamorphism to combine with the list of numbers. Are you f-ing kidding me? Way to turn people on to Haskell! Aside from being described in gratuitously obscure language (to the point of self-parody), this solution seems so brittle that it would make me question the taste of someone presenting it. What if the condition for printing fizz or buzz were more complex than just divisible by n=3 or n=5? What if the number sequence is changed to start with a number other than 1? Does the "maybe catamorphism" go out the window?
- idclip 7y ago
  You shouldnt be downvoted. I find the language very highschooler-unfriendly too, so teaching the youth will be difficult. I love FP ... but the terminology excludes smaller children, and non-mathy people who can still program. Its a shame. The best case scenario is when these concepts simply become compiler specific or core libraries.
  - crispyambulance 7y ago
    There's nothing wrong with haskell itself. Some really cool stuff has been written in it (Pandoc comes to mind). I am objecting to obscurantist presentation. It doesn't have to be THAT opaque for such a simple modulo arithmetic problem. I object to the implementation given in the article. It's ugly and brittle because of how specific it is.
    - idclip 7y ago
      I agree with you, i love haskell’s syntax and function first m style, guards, do’s, types first .. Id call a maybe monad a “safe container type” rather than a monad, where applicatives id call “mappables” ... maybe should write a book about it someday. I understand how criticism is tiring as-well, math people mean well and i honestly don't mean ti take away their toy.
filoeleven 7y ago
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)
bawolff 7y ago
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.

86 points by lelf 7y ago

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...

deleted 7y ago
[deleted]

united893 7y ago

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.

aaron-santos 7y ago
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.
- rgoulter 7y ago
  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'".
  - aaron-santos 7y ago
    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.
  - tsss 7y ago
    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.
    - mikekchar 7y ago
      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.
bojo 7y ago
> 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?
- idclip 7y ago
  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)
  - bojo 7y ago
    For what it's worth I'm a 40yo family man who has been in the industry for 20 years :)
zozbot234 7y ago
I'd rather describe it as mathematical code golfing.
- idclip 7y ago
  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.
daxfohl 7y ago
Depends on what you're doing. Scott Wlaschin did the best modern take on that here: https://fsharpforfunandprofit.com/posts/13-ways-of-looking-at-a-turtle/ 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-abstraction 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/ec2e767e59395376fa191d7c56a74f53936b7653/pkg/controller/volume/persistentvolume/pv_controller.go 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.
ves 7y ago
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.
- idclip 7y ago
  May i ask what is your background?
  - ves 7y ago
    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.
idclip 7y ago
I did haskell for a while and mathematical poetry is actually a very fitting term.
whateveracct 7y ago
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.)

raverbashing 7y ago

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)

saghm 7y ago
mod 3 is easy if you process the number in base 3!
deleted 7y ago
[deleted]
zamadatix 7y ago
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
- raverbashing 7y ago
  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.
- Someone 7y ago
  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)

jamesdhutton 7y ago

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)

_old_dude_ 7y ago
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);
deleted 7y ago
[deleted]
kortilla 7y ago
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))
- inetknght 7y ago
  tbqh that's a lot less readable and a lot less intuitive
  - kortilla 7y ago
    Yeah, not really going for readable. Just an exercise in eliminating the conditional.

bawolff 7y ago

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.

madhadron 7y ago
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.
- bawolff 7y ago
  > 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.
  - chongli 7y ago
    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.

carapace 7y ago

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 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 http://joypy.osdn.io/notebooks/Developing.html (In re: catamorphism et. al. see http://joypy.osdn.io/notebooks/Recursion_Combinators.html http://joypy.osdn.io/notebooks/Recursion_Combinators.html Cheers!)

egypturnash 7y ago

This is so beautiful.

crispyambulance 7y ago

> You can implement the FizzBuzz kata using the fundamental concepts catamorphism, semigroup and monoid. No if-then-else instructions or pattern matching is required. Instead, you use the string concatenation semigroup to enable resonance between two pulses, and the maybe catamorphism to combine with the list of numbers. Are you f-ing kidding me? Way to turn people on to Haskell! Aside from being described in gratuitously obscure language (to the point of self-parody), this solution seems so brittle that it would make me question the taste of someone presenting it. What if the condition for printing fizz or buzz were more complex than just divisible by n=3 or n=5? What if the number sequence is changed to start with a number other than 1? Does the "maybe catamorphism" go out the window?

idclip 7y ago
You shouldnt be downvoted. I find the language very highschooler-unfriendly too, so teaching the youth will be difficult. I love FP ... but the terminology excludes smaller children, and non-mathy people who can still program. Its a shame. The best case scenario is when these concepts simply become compiler specific or core libraries.
- crispyambulance 7y ago
  There's nothing wrong with haskell itself. Some really cool stuff has been written in it (Pandoc comes to mind). I am objecting to obscurantist presentation. It doesn't have to be THAT opaque for such a simple modulo arithmetic problem. I object to the implementation given in the article. It's ugly and brittle because of how specific it is.
  - idclip 7y ago
    I agree with you, i love haskell’s syntax and function first m style, guards, do’s, types first .. Id call a maybe monad a “safe container type” rather than a monad, where applicatives id call “mappables” ... maybe should write a book about it someday. I understand how criticism is tiring as-well, math people mean well and i honestly don't mean ti take away their toy.

filoeleven 7y ago

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)

bawolff 7y ago

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.