2mo ago

Use monoids for construction, what does it do?

I consider myself to be learning haskell. I am proficient enough to solve Advent of Code and do some small projects using it. I love doing it but I always feel like there's more to it. Apparently there is: this blog post from Reasonably Polymorphic caught me, I was probably exactly the intended audience.

What's in the blog post?

They visualize the Builder Pattern, where an Object is created through repeated mutation, which, when transferred to Haskell, should be replaced by creating objects through Monoids and the corresponding Semigroup function <>.

I parse a programming language using parsec and I did exactly what was proposed to enhance my structure creation.

Before, my code was this

Now my code is this

I love the new construction method using Semigroup and Monoid. However, I don't understand them in depth anymore. I have written my own instance of Semigroup and Monoid, and I assume these deriving clauses do something similar.

I also have a dump of the generated class instances using -ddump-deriv -dsuppress-all:

In the documentation it says that there is an instance (Generic a, Monoid (Rep a ())) => Monoid (Generically a) which is defined exactly like the generated instance ghc dumped (source) which uses the Monoid of (Rep a ()) which isn't defined anywhere.

Where does the monoid come from? This is the generated type Rep ::: spoiler Generated

 haskell

    
Derived type family instances:
  type Rep StructBody = D1
                          ('MetaData "StructBody" "Ubc.Parse.Syntax.Struct" "main" 'False)
                          (C1
                             ('MetaCons "StructBody" 'PrefixI 'True)
                             (S1
                                ('MetaSel
                                   ('Just "variables")
                                   'NoSourceUnpackedness
                                   'NoSourceStrictness
                                   'DecidedLazy)
                                (Rec0 [(VariableName, VariableType)])
                              :*: S1
                                    ('MetaSel
                                       ('Just "functions")
                                       'NoSourceUnpackedness
                                       'NoSourceStrictness
                                       'DecidedLazy)
                                    (Rec0 [Function])))

::: but I cannot find a Monoid instance. Do you know where I could learn about this?

Thank you for your time and attention

Edit: fixed a problem with a deriving clause, added a missing code block

2 comments

Reading between the lines, the documentation has the key:
Generic instances … correspond to Semigroup and Monoid instances defined by pointwise lifting.
In more words: each generic type can be broken up into a tuple-like row of components, and the generic type admits a monoid/semigroup whenever every component in the row admits a monoid/semigroup. In your handwritten Semigroup instance, the given code is agnostic as to the types of variables and functions; all that matters is that they already have Semigroup instances of their own.
Let me answer the other question: where's the monoid in the generated Rep? Well, there isn't one! The Rep merely has a struct-like product of component types. If a monoid exists for each component, then a monoid for the entire struct exists (and is built from the obvious pointwise lifting!) but otherwise there isn't a monoid derived from the struct itself. This should be a notable contrast from generic instances for e.g. Functor, where every Rep has exactly zero or one Functor due to the algebra of the semiring of types (there is an underlying algebraic equation with at most one possible solution.)
- Thank you for the detailed answer, especially the explanation 'in more words' and the link helped me understand what happens in this Monoid instance.