7 ms·

Yea, I'm all for overthinking things, but as a solution to fizzbuzz, this article is silly. You don't need any complicated control flow or logic, or functional

Yea, I'm all for overthinking things, but as a solution to fizzbuzz, this article is silly. You don't need any complicated control flow or logic, or functional primitives, for an extensible, readable fizzbuzz.

KirinDave 9y ago
Well, of course you do not "need" solid engineering to express the solution to a trivial problem. The point is not what you need to solve fizzbuzz, it's to give people a taste of what it feels like to do so. And the result is: "oh, it feels normal, but I write less of my own code and reuse existing control flow code." Which is a lot of the point. It's also to point out simple abstractions like Monoid can find uses even in simple problems.
- Veedrac 9y ago
  Less? Even ignoring the glut of imports, it's significantly longer than the straightforward and more extensible attempt where you just chain a few `if`s. (The article did strawman that attempt, but it was transparent enough about it.)
  - KirinDave 9y ago
    Which if my examples is it longer than? It's been awhile since I wrote this so...
    - Veedrac 9y ago
      None of the examples you specifically gave. As I said, it strawman'd the easy method.
      - KirinDave 9y ago
        I don't know what the "easy" method you're referring to is. I did include an else-if chain and did my best to not inflate it. Even though it was 5 years ago I need to revisit this blog to update the pronouns anyways, so please do correct me.
        Veedrac 9y ago
        loop i = 0..100 { out = "" if i % 3 == 0 { out += "Fizz" } if i % 5 == 0 { out += "Fizz" } if i % 7 == 0 { out += "Fizz" } if out == "" { out = str(i) } display out }
        KirinDave 9y ago
        Is this really much shorter than my Haskell example? If we count the import decls it seems to be a bit of a wash.
        Veedrac 9y ago
        It's about 0.7x the length of the final Haskell version, ignoring indentation and imports, but I don't really care about golfing. My point was simply that your statement that you "write less of [your] own code" was not justified.
        KirinDave 9y ago
        > It's about 0.7x the length of the final Haskell version, The final haskell version with the explicit "show" does 2 things your example here does not: offer parameterized final case, and use a rope data structure for the strings. But in a very real sense your code is a special case of the haskell code c_wraith offered. You're using a builtin monoid (strings) and explicit control flow to do it, so your code can't be reused in other contexts. If I tactically asked you for a feature that made the output = '' in some cases, you'd have to refactor pretty significantly. The haskell version not only doesn't have that weakness, but it can even be used to do more abstract things like count the number of times Bar _would_ be printed if we wanted to do that. > but I don't really care about golfing Okay, but for someone that's indifferent you are sorta gut punching c_wraith's code by penalizing haskell for explicit modules and imports for libraries, writing code in a style where I can explain it line-by-line, and comparing a simplified version to my most complicated version. > My point was simply that your statement that you "write less of [your] own code" was not justified. It's a debate I'm willing to have, but I think my blog post defends this point. That code lacks any sense of abstraction over very common patterns, and it ultimately ends up appealing to a builtin monoid and its operations to accomplish the same thing. It's fizzbuzz, so it's hardly a crisis. But the point of this entire discussion here is about how even in these small cases we can see big abstractions appear and be relevant. I'd rather add 4 import lines and lean on code tested till the cows come home than pretend I can't ever have a bad day writing bespoke logic. Edit: it occurs to me that implicitly in this assumption is the notion that we must defend using simple, wide-reaching abstractions. Can you give a good reason why something as trivial as "monoids" isn't exactly the sort of thing we should all be using, as opposed to bespoke logic that on a good day conforms to this pattern? Why _wouldn't_ we?
- rbehrends 9y ago
  The thing is, you're not only complicating your code by introducing monoids, you're unnecessarily restricting yourself. The only thing you need is higher-order functions to be sufficiently general: let every m s i = if i mod m = 0 then Some s else None let fallback i l = if l = [] then [ string_of_int i ] else l let join l = String.concat "" l let fizzbuzz gens i = List.filter_map (fun f -> f i) gens |> fallback i |> join let main () = let fizzbuzzstd = fizzbuzz [ every 5 "Fizz"; every 3 "Buzz" ] in for i = 1 to 100 do print_endline (fizzbuzzstd i) done I've pulled out `join` and `fallback` as separate functions to show that you can also parameterize the code over these functions. And you can use other patterns instead of "every n-th entry" by using generators other than `every`. This approach can make joining O(n) as opposed to O(n^2) (naive concatenation) or O(n*log(n)) (ropes) worst case and is more general. For example, you can also generate numbered lists for each line ("1. Fizz 2. Buzz"). Yeah, that's silly for FizzBuzz, but we're sort of assuming that this is a placeholder for a real problem that we may want to generalize or tune for performance. And if it's actually a monoid and we know nothing more about it than that, we can just go with `List.fold_left` as the join function. Works for all monoids, too, without mentioning the word.
  - KirinDave 9y ago
    First of all, thanks for your post. I don't think your code is wrong or bad in any way. > The thing is, you're not only complicating your code by introducing monoids, you're unnecessarily restricting yourself. Strictly speaking? I agree. All we need for this problem is semigroups. We never explicitly need a "monoid." But I'm not sure offering the "mempty" case is really over-complicating the code, it just bloats the rhetoric a wee bit. But I think what you're referring to is the conceptual overhead of Monoids? I'll get to that in a sec. > The only thing you need is higher-order functions to be sufficiently general: > code follows For "sufficiently" general code, it certainly seems to be less general than a piece of code relying on monoid or semigroup operators. You've hardwired yourself to strings and arrays. F# actually is doing a natural transformation for you from (Maybe~>Maybe String) implicitly in there, so you're really relying on the fact that F#'s got some monoid logic baked in. > And you can use other patterns instead of "every n-th entry" by using generators other than `every`. Right, the essence of fizzbuzz is in the list of partial applications of every onto a list of prime factors and strings. Everything else is repetitive joining logic. Which is why appealing to a pattern that captures nearly all that logic seems like a good idea, no? > This approach can make joining O(n) as opposed to O(n^2) (naive concatenation) or O(n*log(n)) (ropes) worst case and is more general. I do not see how it's more general unless you demand non-associativity which—while fair to do in an interview question—is quite unheard of in the programming world. In terms of runtime performance, rope concatenation is constant and a full retrieval is O(n + log n), not O(n log n), so I'm not sure what you're getting here. But it's worth noting this code (like a lot of F# code) tends to pin onto exactly one data structure and can't simply imply the data structure from calling types. > Works for all monoids, too, without mentioning the word. There's an implicit value judgement here: that not naming this pattern is better. You mentioned it above with the "you complicate your code by introducing monoids." I'm curious why the default mode is that I need to defend naming a pattern that obviously saves code here, and captures more use cases. I don't mean this to be a contentious discussion, I just want to know why you think it's inherently bad.
whoosh99 9y ago
Whoosh.

KirinDave 9y ago

Well, of course you do not "need" solid engineering to express the solution to a trivial problem. The point is not what you need to solve fizzbuzz, it's to give people a taste of what it feels like to do so. And the result is: "oh, it feels normal, but I write less of my own code and reuse existing control flow code." Which is a lot of the point. It's also to point out simple abstractions like Monoid can find uses even in simple problems.

Veedrac 9y ago
Less? Even ignoring the glut of imports, it's significantly longer than the straightforward and more extensible attempt where you just chain a few `if`s. (The article did strawman that attempt, but it was transparent enough about it.)
- KirinDave 9y ago
  Which if my examples is it longer than? It's been awhile since I wrote this so...
  - Veedrac 9y ago
    None of the examples you specifically gave. As I said, it strawman'd the easy method.
    - KirinDave 9y ago
      I don't know what the "easy" method you're referring to is. I did include an else-if chain and did my best to not inflate it. Even though it was 5 years ago I need to revisit this blog to update the pronouns anyways, so please do correct me.
      - Veedrac 9y ago
        loop i = 0..100 { out = "" if i % 3 == 0 { out += "Fizz" } if i % 5 == 0 { out += "Fizz" } if i % 7 == 0 { out += "Fizz" } if out == "" { out = str(i) } display out }
        KirinDave 9y ago
        Is this really much shorter than my Haskell example? If we count the import decls it seems to be a bit of a wash.
        Veedrac 9y ago
        It's about 0.7x the length of the final Haskell version, ignoring indentation and imports, but I don't really care about golfing. My point was simply that your statement that you "write less of [your] own code" was not justified.
        KirinDave 9y ago
        > It's about 0.7x the length of the final Haskell version, The final haskell version with the explicit "show" does 2 things your example here does not: offer parameterized final case, and use a rope data structure for the strings. But in a very real sense your code is a special case of the haskell code c_wraith offered. You're using a builtin monoid (strings) and explicit control flow to do it, so your code can't be reused in other contexts. If I tactically asked you for a feature that made the output = '' in some cases, you'd have to refactor pretty significantly. The haskell version not only doesn't have that weakness, but it can even be used to do more abstract things like count the number of times Bar _would_ be printed if we wanted to do that. > but I don't really care about golfing Okay, but for someone that's indifferent you are sorta gut punching c_wraith's code by penalizing haskell for explicit modules and imports for libraries, writing code in a style where I can explain it line-by-line, and comparing a simplified version to my most complicated version. > My point was simply that your statement that you "write less of [your] own code" was not justified. It's a debate I'm willing to have, but I think my blog post defends this point. That code lacks any sense of abstraction over very common patterns, and it ultimately ends up appealing to a builtin monoid and its operations to accomplish the same thing. It's fizzbuzz, so it's hardly a crisis. But the point of this entire discussion here is about how even in these small cases we can see big abstractions appear and be relevant. I'd rather add 4 import lines and lean on code tested till the cows come home than pretend I can't ever have a bad day writing bespoke logic. Edit: it occurs to me that implicitly in this assumption is the notion that we must defend using simple, wide-reaching abstractions. Can you give a good reason why something as trivial as "monoids" isn't exactly the sort of thing we should all be using, as opposed to bespoke logic that on a good day conforms to this pattern? Why _wouldn't_ we?
rbehrends 9y ago
The thing is, you're not only complicating your code by introducing monoids, you're unnecessarily restricting yourself. The only thing you need is higher-order functions to be sufficiently general: let every m s i = if i mod m = 0 then Some s else None let fallback i l = if l = [] then [ string_of_int i ] else l let join l = String.concat "" l let fizzbuzz gens i = List.filter_map (fun f -> f i) gens |> fallback i |> join let main () = let fizzbuzzstd = fizzbuzz [ every 5 "Fizz"; every 3 "Buzz" ] in for i = 1 to 100 do print_endline (fizzbuzzstd i) done I've pulled out `join` and `fallback` as separate functions to show that you can also parameterize the code over these functions. And you can use other patterns instead of "every n-th entry" by using generators other than `every`. This approach can make joining O(n) as opposed to O(n^2) (naive concatenation) or O(n*log(n)) (ropes) worst case and is more general. For example, you can also generate numbered lists for each line ("1. Fizz 2. Buzz"). Yeah, that's silly for FizzBuzz, but we're sort of assuming that this is a placeholder for a real problem that we may want to generalize or tune for performance. And if it's actually a monoid and we know nothing more about it than that, we can just go with `List.fold_left` as the join function. Works for all monoids, too, without mentioning the word.
- KirinDave 9y ago
  First of all, thanks for your post. I don't think your code is wrong or bad in any way. > The thing is, you're not only complicating your code by introducing monoids, you're unnecessarily restricting yourself. Strictly speaking? I agree. All we need for this problem is semigroups. We never explicitly need a "monoid." But I'm not sure offering the "mempty" case is really over-complicating the code, it just bloats the rhetoric a wee bit. But I think what you're referring to is the conceptual overhead of Monoids? I'll get to that in a sec. > The only thing you need is higher-order functions to be sufficiently general: > code follows For "sufficiently" general code, it certainly seems to be less general than a piece of code relying on monoid or semigroup operators. You've hardwired yourself to strings and arrays. F# actually is doing a natural transformation for you from (Maybe~>Maybe String) implicitly in there, so you're really relying on the fact that F#'s got some monoid logic baked in. > And you can use other patterns instead of "every n-th entry" by using generators other than `every`. Right, the essence of fizzbuzz is in the list of partial applications of every onto a list of prime factors and strings. Everything else is repetitive joining logic. Which is why appealing to a pattern that captures nearly all that logic seems like a good idea, no? > This approach can make joining O(n) as opposed to O(n^2) (naive concatenation) or O(n*log(n)) (ropes) worst case and is more general. I do not see how it's more general unless you demand non-associativity which—while fair to do in an interview question—is quite unheard of in the programming world. In terms of runtime performance, rope concatenation is constant and a full retrieval is O(n + log n), not O(n log n), so I'm not sure what you're getting here. But it's worth noting this code (like a lot of F# code) tends to pin onto exactly one data structure and can't simply imply the data structure from calling types. > Works for all monoids, too, without mentioning the word. There's an implicit value judgement here: that not naming this pattern is better. You mentioned it above with the "you complicate your code by introducing monoids." I'm curious why the default mode is that I need to defend naming a pattern that obviously saves code here, and captures more use cases. I don't mean this to be a contentious discussion, I just want to know why you think it's inherently bad.

whoosh99 9y ago

Whoosh.