Overthinking Fizzbuzz with Monoids

Re:Overthinking Fizzbuzz with Monoids by rbehrends on Thursday September 14, 2017 @05:53AM (#15246360)

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.

[ Parent | on HN ]

Re:Overthinking Fizzbuzz with Monoids by KirinDave on Thursday September 14, 2017 @12:14PM (#15249440)

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.

[ Parent | on HN ]