Examples with functional monoids.

[screwyprof]

Hello @genkami,

Thank you for you detailed response and a great example. I also noticed you've updated the repo and added the FizzBuzz example:

func main() {
    monoid := option.DeriveMonoid[string](algebra.DeriveAdditiveSemigroup[string]())
    fizzBuzz := func(i int) string {
        fizz := option.Filter(option.Some[string]("Fizz"), func(_ string) bool { return i%3 == 0 })
        buzz := option.Filter(option.Some[string]("Buzz"), func(_ string) bool { return i%5 == 0 })
        return option.UnwrapOr(monoid.Combine(fizz, buzz), fmt.Sprint(i))
    }
    it := iterator.Map(iterator.Range[int](1, 15), fizzBuzz)
    iterator.ForEach(it, func(s string) { fmt.Println(s) })
}

It looks nice, concise and pretty aligned with idiomatic Golang. What I'm not sure about is whether combining not monoids is ok, because they don't follow the monodic laws. Is it the expected behavior? In the example above you use a monoid to combine options which don't implement the Monoid interface.

Allow me to drive it a little bit further: At the moment we have this Filter function on the option type. But what if (following the ideas from the aforementioned articles) we try to fold over a set of fizz-buzz Rules, where a Rule is function which takes a predicate and the word:

type FizzBuzzPredicate func(num int) bool
type FizzBuzzRule func(n int) option.String

func Rule(p FizzBuzzPredicate, s string) FizzBuzzRule {
    return func(n int) option.String {
        if p(n) {
            return option.Some(s)
        }

        return option.NoneString()
    }
}

func FizzBuz(n int) string {
    fizz := func(n int) bool {
        return n%3 == 0
    }

    buzz := func(n int) bool {
        return n%5 == 0
    }

    // rules should be a foldable of monoids
    rules := []FizzBuzzRule{
        Rule(fizz, "Fizz"),
        Rule(buzz, "Buzz"),
    }

    // ruleSet is a monoid, which is a function by its nature: monoid[FizzBuzzRule]
    // Written in a move verbose way it is the same as: monoid[ func(n int) option.String].
        // see https://blog.ploeh.dk/2017/11/06/function-monoids/
    ruleSet := fold(rules)

    return ruleSet(n).UnwrapOr(strconv.ItoA(i))
}

// fold :: (Foldable t, Monoid m) => t m -> m
func Fold(filters Foldable) monoid[FizzBuzzFilter] {
  // fold over filters and turn them into a monoid
}

An excerpt in Haskell:

fizzbuzz i = fromMaybe (show i) (ruleSet i)
ruleSet = fold rules

The reasoning behind this is is as such:

• Option should probably not have the Filter method, or should it? I've added it for convenience :)
• Monoids could be the functions per sei, so the combine method should be able to join the function together into a single monoid.

Tell me what do you think?

Thank you for your wonderful job and for patience!

PS: I'm writing without an IDE at hand, so forgive me for some inconsistencies.

[screwyprof]

I also would like to ask you another question on implementing my custom API mentioned here:

// Verify identity
m := monoid.SomeString("test")

// There exists an element e in S such that for every element a in S,
// the equations e • a = a and a • e = a hold.
AssertEqual(t, m, m.Append(m.Empty()))
AssertEqual(t, m.Empty().Append(m), m.Append(m.Empty()))

// Verify Associativity
a := monoid.SomeString("foo")
b := monoid.SomeString("bar")
c := monoid.NoneString()

// For all a, b and c in S, the equation (a • b) • c = a • (b • c) holds.
AssertEqual(t, a.Append(b).Append(c), a.Append(b.Append(c)))

Basically I'm following some ideas from here https://blog.ploeh.dk/2017/10/06/monoids/ It seems to me that it's much more eloquent and more Golang-friendly. YMMW.

Just a quick refresher. Previously, I had my simple String Monoid implemented like this:

package monoid

type String string

func ForString(s string) String {
    return String(s)
}

func (m String) Empty() String {
    return ""
}

func (m String) Append(other String) String {
    return m + other
}

func (m String) Unwrap() string {
    return string(m)
}

func (m String) UnwrapOr(s string) string {
    if m == "" {
        return s
    }

    return string(m)
}

The downsides are:

• We need constructors for the underlying type
• We may need an empty constructor for a more complicated structures.
• We have theses ugly Unwrap and UnwrapOr.

So now when we have the generics, in order for the same idea to work we would need an interface which may look like:

type Monoid[T] interface {
    Empty() Monoid[T]
    Append(other Monoid[T]) Monoid[T]
}

The problem is if we use the generic structure to implement this interface we need to get the underlying T to use it inside Append. In my example above I used a constructor to pass the T. But it won't help with another problem.

Another problem is that we need a way to access the underlying T. For example, we may want to implement a Functor to fmap over our generic Monoid, so we will need to somehow unwrap the underlying T, if it's not implemented on the Monoid itself...

I my earlier examples I could neglect this problem as the types were simple, and I could easily type cast monoid.String to string. I did have those ugly unwrap methods, but in my case I wasn't forced to use them.

Maybe you could help me with some ideas on how to build this kind of API using your awesome library.

Thanks you!

[genkami]

What I'm not sure about is whether combining not monoids is ok, because they don't follow the monodic laws. Is it the expected behavior? In the example above you use a monoid to combine options which are not monoids.

Semigroup is enough for deriving Monoid[Option[T]] because the identity element of Monoid[Option[T]] is None(), so T itself doesn't need its identity. Note that Some("") is not an identity because Some("") + None() == Some("") != None() and None() + Some("") == Some("") != None().

In fact, Haskell's Maybe has the same constraint:

-- | Lift a semigroup into 'Maybe' forming a 'Monoid' according to
-- <http://en.wikipedia.org/wiki/Monoid>: \"Any semigroup @S@ may be
-- turned into a monoid simply by adjoining an element @e@ not in @S@
-- and defining @e*e = e@ and @e*s = s = s*e@ for all @s ∈ S@.\"
--
-- /Since 4.11.0/: constraint on inner @a@ value generalised from
-- 'Monoid' to 'Semigroup'.
--
-- @since 2.01
instance Semigroup a => Monoid (Maybe a) where
    mempty = Nothing

(Quoted from https://hackage.haskell.org/package/base-4.15.0.0/docs/src/GHC-Base.html#Monoid)

[genkami]

Option should probably not have the Filter method, or should it? I've added it for convenience :)

I'm not sure about whether it's good or not to let Option[T] have methods like Filter or any other methods that are normally used for collections of data. However, Scala's Option has filter method that does exactly the same thing as our option.Filter. Moreover, it even has methods like fold, min, max, sum, etc.. So I think it's somewhat reasonable for Options to have such methods (but still I'm not sure).

Monoids could be the functions per sei, so the combine method should be able to join the function together into a single monoid.

It's also nice to letting rules (or functions) be Monoid. This can be written like this:

package examples_test

import (
    "fmt"
    "github.com/genkami/dogs/classes/algebra"
    "github.com/genkami/dogs/types/iterator"
    "github.com/genkami/dogs/types/option"
    "github.com/genkami/dogs/types/slice"
)

type FizzBuzzPredicate func(i int) bool
type FizzBuzzRule func(i int) option.Option[string]

func NewFizzBuzzRule(str string, pred FizzBuzzPredicate) FizzBuzzRule {
    return func(i int) option.Option[string] {
        if pred(i) {
            return option.Some(str)
        }
        return option.None[string]()
    }
}

var Rules = slice.Slice[FizzBuzzRule]{
    NewFizzBuzzRule("Fizz", func(i int) bool { return i%3 == 0 }),
    NewFizzBuzzRule("Buzz", func(i int) bool { return i%5 == 0 }),
}

var (
    OptionMonoid algebra.Monoid[option.Option[string]] = option.DeriveMonoid[string](algebra.DeriveAdditiveSemigroup[string]())
    RuleMonoid   algebra.Monoid[FizzBuzzRule]          = &algebra.DefaultMonoid[FizzBuzzRule]{
        Semigroup: &algebra.DefaultSemigroup[FizzBuzzRule]{
            CombineImpl: func(x, y FizzBuzzRule) FizzBuzzRule {
                return func(i int) option.Option[string] {
                    return OptionMonoid.Combine(x(i), y(i))
                }
            },
        },
        EmptyImpl: func() FizzBuzzRule {
            return func(_ int) option.Option[string] {
                return option.None[string]()
            }
        },
    }
)

func FizzBuzz(i int) string {
    ruleSet := slice.Sum(Rules, RuleMonoid)
    return option.UnwrapOr(ruleSet(i), fmt.Sprint(i))
}

func ExampleFizzBuzz_customMonoidImplementation() {
    it := iterator.Map(iterator.Range[int](1, 15), FizzBuzz)
    iterator.ForEach(it, func(s string) { fmt.Println(s) })
}

[screwyprof]

What I'm not sure about is whether combining not monoids is ok, because they don't follow the monodic laws. Is it the expected behavior? In the example above you use a monoid to combine options which are not monoids.

Semigroup is enough for deriving Monoid[Option[T]] because the identity element of Monoid[Option[T]] is None(), so T itself doesn't need its identity. Note that Some("") is not an identity because Some("") + None() == Some("") != None() and None() + Some("") == Some("") != None().

Great, but two questions:

1. how do we make sure the Monodic laws work in our case? (However, in Haskell you may create a broken monoid as well...)
2. how do we get the monoid state? I've managed to combine the functions and got a monoid. but how do I call the resulting function. In Haskell monoid is just an ordinary type, with some methods, that's, why I provided an example with my old string monoid.

I've almost managed my FizzBuzz to work using the library the way I wanted:

func TestFizzBuzz(t *testing.T) {
    t.Parallel()

    fizz := func(n int) bool {
        return n%3 == 0
    }

    buzz := func(n int) bool {
        return n%5 == 0
    }

    filters := []FizzBuzzRuleFn{
        Rule(fizz, "Fizz"),
        Rule(buzz, "Buzz"),
    }

    ruleSet := RuleSet(filters...)

    AssertEqual(t, "Fizz", option.UnwrapOr(ruleSet(7), strconv.Itoa(7)))
    AssertEqual(t, "Buzz", option.UnwrapOr(ruleSet(7), strconv.Itoa(7)))
    AssertEqual(t, "7", option.UnwrapOr(ruleSet(7), strconv.Itoa(7)))
}

type FizzBuzzRuleFn func(n int) option.Option[string]

func Rule(p func(n int) bool, word string) FizzBuzzRuleFn {
    return func(n int) option.Option[string] {
        if p(n) {
            return option.Some(word)
        }

        return option.None[string]()
    }
}

type FizzBuzzRuleSet interface {
    ~func(n int) option.Option[string]
}

func DeriveFizzBuzzRuleSetSemigroup[T FizzBuzzRuleSet]() algebra.Semigroup[T] {
    return fizzBuzzRuleSetSemigroup[T]{}
}

type fizzBuzzRuleSetSemigroup[T FizzBuzzRuleSet] struct{}

func (fizzBuzzRuleSetSemigroup[T]) Combine(x, y T) T {
    return func(n int) option.Option[string] {
        xSome := x(n)
        ySome := y(n)

        switch {
        case !option.IsSome(xSome):
            return ySome
        case !option.IsSome(ySome):
            return xSome
        default:
            return option.Some(option.UnwrapOr(xSome, "") + option.UnwrapOr(ySome, ""))
        }
    }
}

func DeriveMonoid[T any](s algebra.Semigroup[FizzBuzzRuleFn]) algebra.Monoid[FizzBuzzRuleFn] {
    return &algebra.DefaultMonoid[FizzBuzzRuleFn]{
        Semigroup: s,
        EmptyImpl: func() FizzBuzzRuleFn {
            return func(n int) option.Option[string] {
                return option.None[string]()
            }
        },
    }
}

func RuleSet(rule ...FizzBuzzRuleFn) FizzBuzzRuleFn {
    m := DeriveMonoid[FizzBuzzRuleFn](DeriveFizzBuzzRuleSetSemigroup[FizzBuzzRuleFn]())

    it := slice.Slice[FizzBuzzRuleFn](rule).Iter()
    return iterator.Sum[FizzBuzzRuleFn](it, m)
}

All the functions combine just fine, but the last bit RuleSet should return a monoid, but instead the iterator.sum just uses the monoid.Empty() as init state. Was it intended? Why doesn't it return the monoid? And if returned the monoid according to the interface you've defined then how do we get the actual value out of it?

Probably just can get used to the go version after rust/haskel :)

Any advice is welcome. Thanks

[screwyprof]

Haha, we almost came up with a very similar solution. Good :)

[screwyprof]

Thanks @genkami!

The biggest problem is that the functional approach in Golang with generics gets too ugly even in some trivial cases. I'll keep on watching your work. I'm a big supporter of functional programming, so I hope a lot of things will come into play after the generics are released. In the meantime there are still quite a lot of constraints with them.

So basically your very first version with generics or my very first version in the conventional way are the winners in terms of maintainability, readability and complexity.

Have a lovely day. Thanks again for your responses. PS: Feel free to reach out to me if you need some help or would like to discuss any details.

[genkami]

Thank you, too!

Sorry for late reply (because my English skills are not so good 😢 ) but I'll continue to answer your remaining questions on this issue! Please wait for minutes (or maybe hours)!

[screwyprof]

Common @genkami! You're English is really good. I wish my Japanese was like that ;) Take your time. It's 5 am here in London and Its high time I went to bed. Hope to hear from you soon. Cheers!

[genkami]

So now when we have the generics, in order for the same idea to work we would need an interface which may look like:

type Monoid[T] interface {
    Empty() Monoid[T]
    Append(other Monoid[T]) Monoid[T]
}

The problem is if we use the generic structure to implement this interface we need to get the underlying T to use it inside Append. In my example above I used a constructor to pass the T. But it won't help with another problem.

I think the type definition for this Monoid should be:

type Monoid[T] interface {
    Empty() T
    Append(other T) T
}

then your String.Empty and String.Append just work as you expected. There's no "underlying type" anymore.

However, this approach has severe downside: generic types cannot have conditional methods. There's no such things as:

instance (Semigroup a) => Monoid (Maybe a)

or

impl <T> Monoid<Option<T>> for Option<T>
where T: Semigroup[T]

because generic methods can't have additional constraints. If we implement type classes with this approach and we want Option[T] to be instance of Monoid[Option[T]], we have to do something like this:

type Option[T any] ...

func (o Option[T]) Empty() Option[T] { return None() }

func (o Option[T]) Append(other Option[T]) Option[T] {
    // We can't expect T to be Monoid[T] or even Semigroup[T] because the constraint on T is any.
}

What we can do here is to give up implementing Monoid[Option[T]], or to add extra constraint on T like type Option[T Monoid[T]].

So I implemented type classes as just a set of functions like:

type Semigroup[T] interface {
    Combine(T, T) T
}

in order to avoid adding unnecessary constraints on type parameters.

[screwyprof]

Hello @genkami,

Thanks for getting back to me. I see your point and it makes sense to me. In other words if we would like to have a generic Monoid[Option[T]] we would have to implement it manually or use some kind of a code generator to respect the interface I suggested.

In the meantime I pushed some FizzBuzz related stuff into the experimental func branch.

The most surprising thing to me are the benchmarks:

❯ make test-bench
==> Running benchmarks
goos: darwin
goarch: amd64
pkg: github.com/screwyprof/gofizzbuzz
cpu: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
PASS
benchmark                                    iter        time/iter   bytes alloc          allocs
---------                                    ----        ---------   -----------          ------
BenchmarkFizzBuzz/FizzBuzz-8             57863870      19.25 ns/op        4 B/op     0 allocs/op
BenchmarkFizzBuzz/FizzBuzzFunctional-8    1804785     662.60 ns/op      480 B/op    17 allocs/op
BenchmarkPrintFizzBuzzFunctional-8          51546   30317.00 ns/op     8090 B/op   273 allocs/op
BenchmarkPrintFizzBuzz-8                   126994   11868.00 ns/op      960 B/op    30 allocs/op

If we optimise it a bit to calculate some values at compile time such as:

package gofizzbuzz

import (
    "strconv"

    "github.com/genkami/dogs/classes/algebra"
    "github.com/genkami/dogs/types/option"
    "github.com/genkami/dogs/types/slice"
)

var (
    fizz = func(n int) bool {
        return n%3 == 0
    }

    buzz = func(n int) bool {
        return n%5 == 0
    }
)

var (
    rules = slice.Slice[FizzBuzzRule]{
        Rule(fizz, "Fizz"),
        Rule(buzz, "Buzz"),
    }

    ruleSet = slice.Sum(rules, NewRuleSetMonoid())
)

func FizzBuzzFunctional(n int) string {
    return option.UnwrapOr(ruleSet(n), strconv.FormatInt(int64(n), 10))
}

We will get the following results:

❯ make test-bench
==> Running benchmarks
goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
PASS
benchmark                                    iter        time/iter   bytes alloc         allocs
---------                                    ----        ---------   -----------         ------
BenchmarkFizzBuzz/FizzBuzz-8             64880266      18.99 ns/op        4 B/op    0 allocs/op
BenchmarkFizzBuzz/FizzBuzzFunctional-8   15378289      65.88 ns/op        8 B/op    1 allocs/op
BenchmarkPrintFizzBuzzFunctional-8         113386   11900.00 ns/op     1008 B/op   33 allocs/op
BenchmarkPrintFizzBuzz-8                   118827   13036.00 ns/op      960 B/op   30 allocs/op

Which is kind of nice, given that the library is not yet optimised and generics are still in development.

The best I could get out of all the fizz-buzzes for today:

❯ make test-bench
==> Running benchmarks
goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
PASS
benchmark                                    iter        time/iter   bytes alloc         allocs
---------                                    ----        ---------   -----------         ------
BenchmarkFizzBuzz/FizzBuzz-8             67540668      18.66 ns/op        4 B/op    0 allocs/op
BenchmarkFizzBuzz/FizzBuzzFunctional-8   21838344      58.37 ns/op        8 B/op    1 allocs/op
BenchmarkPrintFizzBuzzFunctional-8         112123   10592.00 ns/op     1008 B/op   33 allocs/op
BenchmarkPrintFizzBuzz-8                   124335    9863.00 ns/op      960 B/op   30 allocs/op

Once again thank you very much for your answers and your work.